链表LinkedList(Java)

心已赠人 2023-07-01 07:27 2阅读 0赞

# 链表LinkedList #

**定义**  
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。  
**优点**  
真正的动态，不需要处理固定容量问题  
**缺点**  
丧失了随机访问的能力  
**LinkedList.java**  
设置了虚拟头节点，让在链表头添加元素不在特殊，使得链表添加元素都是使用同一种方式

public class LinkedList<E> {
        
    	private class Node {
        // 内部类将节点设为私有 隐藏实现细节
    		public E e;// 元素
    		public Node next;// next指针
    
    		public Node(E e, Node next) {
        
    			this.e = e;
    			this.next = next;
    		}
    
    		public Node(E e) {
        
    			this(e, null);
    		}
    
    		public Node() {
        
    			this(null, null);
    		}
    
    		@Override
    		public String toString() {
        
    			return e.toString();
    		}
    	}
    
    	private Node dummyhead; // 设置虚拟头节点
    	int size;// 链表中元素个数
    
    	public LinkedList() {
        
    		// TODO Auto-generated constructor stub
    		dummyhead = new Node(null, null);
    		size = 0;
    	}
    
    	// 获取链表中的元素个数
    	public int getSize() {
        
    		return size;
    	}
    
    	// 返回链表是否为空
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return size == 0;
    	}
    
    	// 在链表的index位置添加一个元素
    	public void add(int index, E e) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    
    		Node prev = dummyhead;// 创建一个索引与dummyhead指向一致
    		for (int i = 0; i < index; i++) // 需要找到索引的前一个位置
    			prev = prev.next;// prev在链表中移动
    		// Node node = new Node(e);//创建一个node
    		// node.next = prev.next;//node.next指向prev.next
    		// prev.next = node;//prev.next指向node
    		prev.next = new Node(e, prev.next);// 等于 上面3行代码
    		size++;
    
    	}
    
    	// 在链表尾部添加元素
    	public void addLast(E e) {
        
    		add(size, e);
    	}
    
    	// 在链表头添加元素
    	public void addFirst(E e) {
        
    		// TODO Auto-generated method stub
    		add(0, e);
    	}
    
    	// 获得链表的第index个元素
    	public E get(int index) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		Node cur = dummyhead.next;// 寻找第index个元素
    		for (int i = 0; i < index; i++)
    			cur = cur.next;
    		return cur.e;// 返回cur.e就是第index个元素
    	}
    
    	// 获得第一个元素
    	public E getFirst() {
        
    		return get(0);
    	}
    
    	// 获得最后一个元素
    	public E getLast() {
        
    		return get(size - 1);
    	}
    
    	// 修改链表的第index个元素
    	public void set(int index, E e) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		Node cur = dummyhead.next;// 寻找第index个元素
    		for (int i = 0; i < index; i++)
    			cur.e = e;
    	}
    
    	// 查找链表中是否有元素e
    	public boolean contains(E e) {
        
    		Node cur = dummyhead.next;
    		while (cur != null) {
        
    			if (cur.e.equals(e)) // 判断cur.e是否等于用户传来的e
    				return true;
    			cur = cur.next;// 依次遍历
    		}
    		return false;
    	}
    
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		// Node cur = dummyhead.next;
    		// while (cur != null) {
        
    		// res.append(cur + "->");
    		// cur = cur.next;
    		// }
    		for (Node cur = dummyhead.next; cur != null; cur = cur.next)
    			res.append(cur + "->");
    		res.append("NULL");
    		return res.toString();
    	}
    
    	// 删除链表中第index个元素，并返回删除的元素
    	public E remove(int index) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		Node prev = dummyhead;
    		for (int i = 0; i < index; i++)
    			prev = prev.next;
    		Node retNode = prev.next;// prev.next所指的元素就是要删除的节点retNode
    		prev.next = retNode.next;// prev.next跳过retNode直接指向retNode.next
    		retNode.next = null;// 垃圾回收retNode.next
    		size--;
    		return retNode.e;
    	}
    
    	// 删除链表中第一个元素，返回删除的元素
    	public E removeFirst() {
        
    		return remove(0);
    	}
    
    	// 删除链表中最后一个元素，返回删除的元素
    	public E removeLast() {
        
    		return remove(size - 1);
    	}
    }

**测试**

public class LinkedListText {
        
    	public static void main(String[] args) {
        
    		LinkedList<Integer> linkedlist = new LinkedList<>();
    		for (int i = 0; i < 5; i++) {
        
    			linkedlist.addFirst(i);//这里使用的是头插法，使用尾插法则使用linkedlist.addLast(i);
    			System.out.println(linkedlist);
    		}
    		linkedlist.add(2, 24);
    		System.out.println(linkedlist);
    		
    		linkedlist.remove(2);
    		System.out.println(linkedlist);
    		
    		linkedlist.removeFirst();
    		System.out.println(linkedlist);
    		
    		linkedlist.removeLast();
    		System.out.println(linkedlist);
    	}
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]  
**- 头插法相对简便，但插入的数据与插入的顺序相反；**  
**- 尾插法操作相对复杂，但插入的数据与插入顺序相同。**

## 链表的时间复杂度 ##

**增加：O(n)  
删除：O(n)  
修改：O(n)  
查询：O(n)**  
  
**如果只对链表头进行增加、删除操作：O(1);  
如果只查询链表头的元素：O(1)**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020011918123074.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200119181342374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70