Java源码分析——Linkedlist（个人笔记）

一、

本篇介绍的是Java的链表——Linkedlist，当然，Java中常用的队列Queue，也是Linkedlist实现的。由于个人水平有限，只分析其中的部分源码，分析有误的地方，还请各位大佬多多指出，咱们共同学习。另外，我使用的是jdk1.8版本。

二、成员变量分析

三个基本的成员变量，由于Linkedlist是使用双向链表实现的，所以有一个first结点和一个last结点 transient int size = 0; transient Node<E> first; transient Node<E> last; 这里还需要介绍一下Linkedlist里的基本结构——结点，代码很清晰，一目了然，很好理解 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

三、常用函数分析

1.构造函数

public LinkedList()函数：默认构造函数，没什么好说的 public LinkedList() { } public LinkedList(Collection<? extends E> c)函数：通过集合c来构造链表，代码很简单，至于代码里提到的addAll函数，后面再讲。 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

2. 常用的操作函数

和Arraylist的分析一样，先从add系列函数说起

1.add系列函数

public boolean add(E e)函数：目的是将元素插入到链表的末尾 public boolean add(E e) { linkLast(e); return true; }

这里直接调用了linkLast函数，具体如下：代码上很容易理解。先将last指向的对象设置为新结点newNode的前缀结点，然后再进行判断，根据判断结果，对first的值进行委派，最后，链表中元素数据加1。

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 //说明前面还有非空结点，那么把前面非空结点的next进行改变 l.next = newNode; size++; modCount++; } public void add(int index, E element)函数：将元素插入到具体的某个索引index位置上去 public void add(int index, E element) { checkPositionIndex(index); //索引合法性检查 if (index == size) //直接加到最后 linkLast(element); else linkBefore(element, node(index)); //加到具体的索引位置 }

这里，如果索引值小于链表中数据元素数据，说明，要插入的地方不是链表的末尾，那么就要调用linkBefore函数，这里还需要调用node函数先找到index位置的元素，node函数如下：

Node<E> node(int index) { // 因为是双向链表，所以在查找元素是，可以根据索引来判断，是从first开始找，还是从last开始找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

linkBefore函数如下：找到index索引对应的元素之后，剩下的就是常规的链表插入操作了。无非是几个指针的来回改变，不做赘述了。

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++; } public boolean addAll(Collection<? extends E> c)函数：将集合中的元素加入到链表的末尾，具体实现是调用了addAll(size, c)方法 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c)函数：之前的构造函数调用了这个函数。这个函数的目的是将集合中的所有元素插入都指定索引的后面 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //检测索引合法性 Object[] a = c.toArray(); //转换成数组 int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { //这种情况下，相当于插入到链表末尾 succ = null; pred = last; } else { succ = node(index); //找到具体index对应位置的结点 pred = succ.prev; //找到该元素的前缀结点 } for (Object o : a) { //遍历集合c，执行链表的插入操作 @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) //对pred进行特殊考虑，这种情况出现在index=0的时候 first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { //对succ进行分类考虑 last = pred; } else { //完成最后的指针委派 pred.next = succ; succ.prev = pred; } size += numNew; //链表的元素数据更新 modCount++; return true; } public void addFirst(E e)函数：从名字就可以看出来，目的是将元素插入链表头部 public void addFirst(E e) { linkFirst(e); }

调用了linkFirst函数，这个函数和之前介绍的linkLast(E e)函数很类似，只不过一个负责插入到头部，一个负责插入到尾部。代码如下：

private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } public void addLast(E e)函数：负责将元素插入到链表尾部，里面调用了linkLast函数，不做赘述 public void addLast(E e) { linkLast(e); }

小总结： 至此，add系列函数全部介绍完了，里面的函数逻辑和链表的一些操作逻辑是一致的，并不难。不过，乍一看，add系列函数好像有冗余，比如addLast和addFirst函数，有没有都行。其实这是因为Linkedlist继承了Deque接口，要完成队列的一些功能，所以函数的实现上显得有冗余。

2.remove系列函数

public E remove()函数：负责删除链表中第一个元素 public E remove() { return removeFirst(); }

调用了removeFirst函数，代码如下：

public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }

里面调用了unlinkFirst函数，代码如下：逻辑很简单，就是将first结点对应的各种指针置为null，方便垃圾回收，同时更新后面结点的指针，最后完成链表数量的更新。

private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } public E remove(int index)函数：负责删除链表中指定位置元素 public E remove(int index) { checkElementIndex(index);//首先检查index合法性 return unlink(node(index));//先找到index对应的结点，然后调用unlink函数 }

调用了unlink函数，代码如下：

E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; //找到要删除结点的前驱结点和后继结点 final Node<E> prev = x.prev; //对前驱结点的指针进行更改 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //对后继结点的指针进行更改 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //将元素置为null x.item = null; size--; modCount++; return element; } public boolean remove(Object o)函数：删除链表中与元素o相等的第一个元素。首先找到含有相同元素的结点，然后调用unlink函数进行删除。 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E removeFirst()函数：删除第一个元素，调用unlinkFirst函数，很简单 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public boolean removeFirstOccurrence(Object o)函数：删除链表中与元素o相等的第一个元素，直接调用remove函数就完事了 public boolean removeFirstOccurrence(Object o) { return remove(o); } public E removeLast()函数：删除最后一个元素，调用unlinkLast函数，很简单 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } public boolean removeLastOccurrence(Object o)函数：删除链表中与元素o相等的最后一个元素。方法是倒着找，从last结点开始找，找到的第一个与o相等的结点，然后调用unlink方法就可以了 public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }

小总结： remove系列函数中也存在一些功能冗余的函数，本质还是因为继承了Deque接口，要完成队列的一些功能，所以函数的实现上显得有冗余。

四、总结