java linkedlist 源码剖析-mile米乐体育

总体介绍

linkedlist同时实现了list接口和deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（queue），同时又可以看作一个栈（stack）。这样看来，linkedlist简直就是个全能冠军。当你需要使用栈或者队列的时候，首先应该考虑的就是linkedlist。因为java官方已经声明不建议使用stack类，推荐使用linkedlist，更遗憾的是，java里根本没有一个叫做queue的类（它是个接口名字）。

linkedlist底层通过双向链表实现，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间解跟list接口相关的函数，而将queue和stack以及deque相关的知识放在下一节讲。双向链表的每个节点用内部类node表示。linkedlist通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。

//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的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率linkedlist没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用collections.synchronizedlist()方法对其进行包装。

方法剖析

add()

add()方法有两个版本，一个是add(e e)，该方法在linkedlist的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, e element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

结合上图，可以看出add(e e)的逻辑非常简单。

//add(e e) public boolean add(e e) {     final node l = last;     final node newnode = new node<>(l, e, null);     last = newnode;     if (l == null)         first = newnode;//原来链表为空，这是插入的第一个元素     else         l.next = newnode;     size  ;     return true; }

add(int index, e element)的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, e element) public void add(int index, e element) {     checkpositionindex(index);//index >= 0 && index <= size;     if (index == size)//插入位置是末尾，包括列表为空的情况         add(element);     else{         node succ = node(index);//1.先根据index找到要插入的位置         //2.修改引用，完成插入操作。         final node pred = succ.prev;         final node newnode = new node<>(pred, e, succ);         succ.prev = newnode;         if (pred == null)//插入位置为0             first = newnode;         else             pred.next = newnode;         size  ;     } }

上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index < (size >> 1)，也即是index是靠近前端还是后端。

remove()

remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(object o)，另一个是删除指定下标处的元素remove(int index)。

两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个revome()方法都是通过unlink(node x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(node x)，删除一个node e unlink(node x) {     final e element = x.item;     final node next = x.next;     final node 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;     }     x.item = null;//let gc work     size--;     return element; }

get()

get(int index)得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。

public e get(int index) {     checkelementindex(index);//index >= 0 && index < size;     return node(index).item; }

set()

set(int index, e element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改node中item的值。

public e set(int index, e element) {     checkelementindex(index);     node x = node(index);     e oldval = x.item;     x.item = element;//替换新值     return oldval; }