java linkedlist 源码分析-亚博电竞手机版

简介

linkedlist 是一个常用的集合类，用于顺序存储元素。 linkedlist 经常和 arraylist 一起被提及。大部分人应该都知道 arraylist 内部采用数组保存元素，适合用于随机访问比较多的场景，而随机插入、删除等操作因为要移动元素而比较慢。 linkedlist 内部采用链表的形式存储元素，随机访问比较慢，但是插入、删除元素比较快，一般认为时间复杂都是 o(1) (需要查找元素时就不是了，下面会说明)。本文分析 linkedlist 的具体实现。

继承关系

public class linkedlist extends abstractsequentiallist implements list, deque, cloneable, java.io.serializable

linkedlist 继承了一个抽象类 abstractsequentiallist ，这个类就是用调用 listiterator 实现了元素的增删查改，比如 add 方法：

public void add(int index, e element) {     try {         listiterator(index).add(element);     } catch (nosuchelementexception exc) {         throw new indexoutofboundsexception("index: " index);     } }

不过这些方法在 linkedlist 中被复写了。

linkedlist 实现了 list 、 deque 、 cloneable 以及 serializable 接口。其中 deque 是双端队列接口，所以 linkedlist 可以当作是栈、队列或者双端队队列。

内部变量

transient int size = 0; transient node first; transient node last;

总共就三个内部变量， size 是元素个数， first 是指向第一个元素的指针， last 则指向最后一个。元素在内部被封装成 node 对象，这是一个内部类，看一下它的代码：

private static class node {     e item;     node next;     node prev;      node(node prev, e element, node next) {         this.item = element;         this.next = next;         this.prev = prev;     } }

可以看到这是一个双向链表的结构，每个节点保存它的前驱节点和后继节点。

私有方法

linkedlist 内部有几个关键的私有方法，它们实现了链表的插入、删除等操作。比如在表头插入：

private void linkfirst(e e) {     final node f = first;    //先保存当前头节点     //创建一个新节点，节点值为e，前驱节点为空，后继节点为当前头节点     final node newnode = new node<>(null, e, f);     first = newnode;    //让first指向新节点     if (f == null)    //如果链表原来为空，把last指向这个唯一的节点         last = newnode;     else    ·        //否则原来的头节点的前驱指向新的头节点         f.prev = newnode;     size  ;     modcount  ; }

其实就是双向链表的插入操作，调整指针的指向，时间复杂度为 o(1) ，学过数据结构的应该很容易看懂。其它还有几个类似的方法：

//尾部插入 void linklast(e e) {     final node l = last;     final node newnode = new node<>(l, e, null);     last = newnode;     if (l == null)    //如果链表原来为空，让first指向这个唯一的节点         first = newnode;     else         l.next = newnode;     size  ;     modcount  ; } //中间插入 void linkbefore(e e, node succ) {     // assert succ != null;     final node pred = succ.prev;     final node newnode = new node<>(pred, e, succ);     succ.prev = newnode;     if (pred == null)         first = newnode;     else         pred.next = newnode;     size  ;     modcount  ; } //删除头节点 private e unlinkfirst(node f) {     // assert f == first && f != null;     final e element = f.item;     final node next = f.next; //先保存下一个节点     f.item = null;         f.next = null; // help gc     first = next;    //让first指向下一个节点     if (next == null)    //如果下一个节点为空，说明链表原来只有一个节点，现在成空链表了，要把last指向null         last = null;     else        //否则下一个节点的前驱节点要置为null         next.prev = null;     size--;     modcount  ;     return element; } //删除尾节点  private e unlinklast(node l) {     // assert l == last && l != null;     final e element = l.item;     final node prev = l.prev;  //保存前一个节点     l.item = null;     l.prev = null; // help gc     last = prev;    //last指向前一个节点     if (prev == null)    //与头节点删除一样，判断是否为空         first = null;     else         prev.next = null;     size--;     modcount  ;     return element; } //从链表中间删除节点  e unlink(node x) {     // assert x != null;     final e element = x.item;     final node next = x.next;    //保存前驱节点     final node prev = x.prev;    //保存后继节点      if (prev == null) {    //前驱为空，说明删除的是头节点，first要指向下一个节点         first = next;     } else {                //否则前驱节点的后继节点变为当前删除节点的下一个节点         prev.next = next;         x.prev = null;     }      if (next == null) {       //判断后继是否为空，与前驱节点是否为空的逻辑类似         last = prev;     } else {         next.prev = prev;         x.next = null;     }      x.item = null;     size--;     modcount  ;     return element; }

公开方法

公开的方法几乎都是调用上面几个方法实现的，例如 add 方法：

public boolean add(e e) {     linklast(e);     return true; } public boolean add(e e) {     linklast(e);     return true; } public void add(int index, e element) {     checkpositionindex(index);      if (index == size)         linklast(element);     else         linkbefore(element, node(index)); }

这些方法的实现都很简单。注意最后一个方法 add(int index, e element) ，这个方法是在指定的位置插入元素。首先判断位置是否越界，然后判断是不是最后一个位置。如果是就直接插入链表末尾，否则调用 linkbefore(element, node(index) 方法。这里在传参数的时候又调用了 node(index) ，这个方法的目的是找到这个位置的节点对象，代码如下：

node node(int index) {     // assert iselementindex(index);     if (index < (size >> 1)) {         node x = first;         for (int i = 0; i < index; i  )             x = x.next;         return x;     } else {         node x = last;         for (int i = size - 1; i > index; i--)             x = x.prev;         return x;     } }

这里有个小技巧是先判断位置是在链表的前半段还是后半段，然后决定从链表的头还是尾去寻找节点。要注意的是 遍历链表寻找节点的时间复杂度是 o(n) ,即使做了位置的判断，最坏情况下也要遍历链表中一半的元素。所以此时插入操作的时间复杂度就不是 o(1) ,而是 o(n/2) o(1) 。用于查找指定位置元素的 get(int index) 方法便是调用 node 实现的：

public e get(int index) {     checkelementindex(index);     return node(index).item; }

再看一下 remove 方法：

public e remove(int index) {     checkelementindex(index);     return unlink(node(index)); }  public boolean remove(object o) {     if (o == null) {         for (node x = first; x != null; x = x.next) {             if (x.item == null) {                 unlink(x);                 return true;             }         }     } else {         for (node x = first; x != null; x = x.next) {             if (o.equals(x.item)) {                 unlink(x);                 return true;             }         }     }     return false; }

第一个 remove(int index) 方法同样要调用 node(index) 寻找节点。而第二个方法 remove(object o) 是删除指定元素，这个方法要依次遍历节点进行元素的比较，最坏情况下要比较到最后一个元素，比调用 node 方法更慢，时间复杂度为 o(n) 。另外从这个方法可以看出 linkedlist 的元素可以是 null 。

总结

• linkedlist 基于双向链表实现，元素可以为 null 。
• linkedlist 插入、删除元素比较快，如果只要调整指针的指向那么时间复杂度是 o(1) ,但是如果针对特定位置需要遍历时，时间复杂度是 o(n) 。