一. 初始化

1.1 底层数据结构

1.1.1 数据结构

LinkedList底层数据结构是一个双端链表，每个节点不仅持有自己数据的值，还持有前节点和后节点的引用LinkedList详解 - 图1

1.1.2 节点代码

每个节点都持有前后节点的引用和本节点应该存储的数据

  1.     private static class Node<E> {
  2.         E item;
  3.         Node<E> next;
  4.         Node<E> prev;
  6.         Node(Node<E> prev, E element, Node<E> next) {
  7.             this.item = element;
  8.             this.next = next;
  9.             this.prev = prev;
  10.         }
  11.     }

链表还维护着首尾节点的应用，方便进行首尾元素的增删

  1.     /**
  2.      * Pointer to first node.
  3.      * Invariant: (first == null && last == null) ||
  4.      *            (first.prev == null && first.item != null)
  5.      */
  6.     transient Node<E> first;
  8.     /**
  9.      * Pointer to last node.
  10.      * Invariant: (first == null && last == null) ||
  11.      *            (last.next == null && last.item != null)
  12.      */
  13.     transient Node<E> last;

二. 添加元素

2.1 头部添加元素

模拟在链表头部添加元素。

  1. 首先把原先的头元素first记录下来，记为f
  2. 然后根据创建出来的节点新建出一个新的节点，这个新节点的next指向原先的头元素f。 此时状态如下

newNode

  • first: null
  • element: e
  • next: f
    1. 把新节点赋值给原先的头部节点引用first（因为是头部插入）此时的状态如下

newNode/first

  • first: null
  • element: e
  • next: f
    1. 判断f（即原先的头部节点）是不是空
  1. 如果为空，那么时在空链表中插入了一个元素，那么头部元素、尾部元素都时newNode
  2. 如果不为空，那么原先头部节点的前指针（因为已经时头部节点，所以前指针为空）需要指向新节点newNode，来完成节点的链接。

这个节点的链接，不能单方面的链接，必须两个节点双向链接才OK
29319a065d3e25c6f390bf5dbe43231.jpg

  1.     /**
  2.      * Links e as first element.
  3.      */
  4.     private void linkFirst(E e) {
  5.         final Node<E> f = first;
  6.         final Node<E> newNode = new Node<>(null, e, f);
  7.         first = newNode;
  8.         if (f == null)
  9.             last = newNode;
  10.         else
  11.             f.prev = newNode;
  12.         size++;
  13.         modCount++;
  14.     }

2.2 尾部插入

实现原理和头部差不多

  1.     /**
  2.      * Links e as last element.
  3.      */
  4.     void linkLast(E e) {
  5.         final Node<E> l = last;
  6.         final Node<E> newNode = new Node<>(l, e, null);
  7.         last = newNode;
  8.         if (l == null)
  9.             first = newNode;
  10.         else
  11.             l.next = newNode;
  12.         size++;
  13.         modCount++;
  14.     }

2.3 插在某个节点之前

image.png

  1.     /**
  2.      * Inserts element e before non-null Node succ.
  3.      */
  4.     void linkBefore(E e, Node<E> succ) {
  5.         // assert succ != null;
  6.         final Node<E> pred = succ.prev;
  7.         final Node<E> newNode = new Node<>(pred, e, succ);
  8.         succ.prev = newNode;
  9.         if (pred == null)
  10.             first = newNode;
  11.         else
  12.             pred.next = newNode;
  13.         size++;
  14.         modCount++;
  15.     }