链表

链表通过指针将零散的数据块连接在一起，这些内存块被称为节点（Node）。通常每个节点除了储存数据之外还记录下一个节点的地址。

//Node类是LinkedList类的内部类，泛型E定义在LinkedList上
class Node {
    E e;        //数据域
    Node next;  //下一个节点
    
    Node() {
        this(null, null);
    }
    
    Node(E e) {
        this(e, null);
    }
    
    Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }
}

与数组相比，数组的存储空间是连续的。因此为了保证数组的存储空间的连续性，需要搬移节点。而链表的各个节点是由指针串联起来的，插入和删除时只需维护指针即可，这样的时间复杂度为O(1)。

单链表LinkedList

设置虚拟头结点（哨兵）方便实现统一的逻辑代码，哨兵节点不存储数据。无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。下面是LinkedList的两个成员变量

private Node dummyHead;     //哨兵
private int size;

//构造器初始化
public LinkedList() {
    dummyHead = new Node();
    size = 0;
}

链表的重要操作

1. add(int index, E e):在index位置插入元素e

   public viod add(int index, E e) {
       Node prev = dummyHead;
       
       //指针移动到目标节点的前一个节点上
       for(int i = 0; i < index; i ++) {
           prev = prev.next;
       }
       
       //修改指针的指向
       //Node newNode = new Node(e);
       //newNode.next = prev.next;
       //prev.next = newNode;
       
       //上面的三行合并成一行
       prev.next = new Node(e, prev.next);
       
       size ++;
   }
   

2. removeElement(E e)：移除指定的元素e

   public void removeElement(E e) {
       Node prev = dummyHead;
       
       while(prev.next != null) {
           if(prev.next.e.equals(e)) {
               //在找到目标元素的前一个节点处停止
               break;
           }
           prev = prev.next;
       }
       if(prev.next != null) {
           prev.next = prev.next.next;
       }
   }
   

3. remove(int index)：移除指定位置上的元素，并返回该元素

   public E remove(int index) {
       Node prev = dummyHead;
       
       //在找到目标元素的前一个节点处停止
       for(int i = 0; i < index; i ++) {
           prev = prev.next;
       }
       
       //记录节点，用于返回
       Node retNode = prev.next;
       //修改指针
       prev.next = retNode.next;
       //销毁被删元素
       retNode.next = null;
      
       size --;
       
       return retNode.e;
   }