Java 容器源码分析之 LinkedList（2）

look_w

双向链表操作LinkedList 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在 双向链表的两端进行操作，也是基于对头和尾部元素的操作。总的来说，双向链表的操作并不复杂，下面简单地进行解析，大部分操作都是对以下几种操作的封装。
向头部添加元素

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

//将一个元素加入双向链表的头部 private void linkFirst(E e) {     final Node<E> f = first;     //新节点的前驱节点为null，后继节点为原来的头节点     final Node<E> newNode = new Node<>(null, e, f);     first = newNode;     if (f == null) //原来的头节点为空         //新加入的节点是第一个也是最后一个         last = newNode;     else         //修改原来头节点的前驱指向         f.prev = newNode;     //调整链表大小     size++;     //修改计数器     modCount++; }

向尾部添加元素

1 2 3 4 5 6 7 8 9 10 11

void linkLast(E e) {     final Node<E> l = last;     final Node<E> newNode = new Node<>(l, e, null);     last = newNode;     if (l == null)         first = newNode;     else         l.next = newNode;     size++;     modCount++; }

从中间插入元素

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

//在一个非空节点前插入元素 void linkBefore(E e, Node<E> succ) {     // assert succ != null;     final Node<E> pred = succ.prev; //获取前驱     //注意新建节点的前驱与后继     final Node<E> newNode = new Node<>(pred, e, succ);     //调整相关节点的前驱与后继关系     succ.prev = newNode;     if (pred == null)         first = newNode;     else         pred.next = newNode;     //修改大小     size++;     modCount++; }

移除头部节点

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

//将头节点从链表移除 private E unlinkFirst(Node<E> f) {     // assert f == first && f != null;     final E element = f.item;     final Node<E> next = f.next;     //引用修改为null，方便GC     f.item = null;     f.next = null; // help GC     //调整头节点     first = next;     if (next == null) //移除后链表为空         last = null;     else         next.prev = null;     size--;     modCount++;     return element; }