前言
上周末我们一起分析了arraylist的源码并进行了一些总结，因为最近在看collection这一块的东西，下面的图也是大致的总结了collection里面重要的接口和类，如果没有意外的话后面基本上每一个都会和大家一起学习学习，所以今天也就和大家一起来看看linkedlist吧！
2，记得首次接触linkedlist还是在大学java的时候，当时说起linkedlist的特性和应用场景：linkedlist基于双向链表适用于增删频繁且查询不频繁的场景，线程不安全的且适用于单线程（这点和arraylist很像）。然后还记得一个很深刻的是可以用linkedlist来实现栈和队列，那让我们一起看一看源码到底是怎么来实现这些特点的
2.1 构造函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
public class linkedlist<e> extends abstractsequentiallist<e> implements list<e>, deque<e>, cloneable, java.io.serializable { transient int size = 0 ; transient node<e> first; transient node<e> last;
public linkedlist() { }
public linkedlist(collection<? extends e> c) { this (); addall(c); }
public boolean addall(collection<? extends e> c) { return addall(size, 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); pred = succ.prev; }
for (object o : a) { @suppresswarnings ( "unchecked" ) e e = (e) o; node<e> newnode = new node<>(pred, e, null ); if (pred == null ) first = newnode; else pred.next = newnode; pred = newnode; }
if (succ == null ) { last = pred; } else { pred.next = succ; succ.prev = pred; }
size += numnew; modcount++; return true ; }
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; } }
node<e> node( int index) { // assert iselementindex(index);
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; } }
} |
首先我们知道常见的构造是linkedlist()和linkedlist(collection<? extends e> c)两种，然后再来看看我们继承的类和实现的接口
linkedlist 集成abstractsequentiallist抽象类，内部使用listiterator迭代器来实现重要的方法
linkedlist 实现 list 接口，能对它进行队列操作。
linkedlist 实现 deque 接口，即能将linkedlist当作双端队列使用。
linkedlist 实现了cloneable接口，即覆盖了函数clone()，能克隆。
linkedlist 实现java.io.serializable接口，这意味着linkedlist支持序列化，能通过序列化去传输。
可以看到，相对于arraylist，linkedlist多实现了deque接口而少实现了randomaccess接口，且linkedlist继承的是abstractsequentiallist类，而arraylist继承的是abstractlist类。那么我们现在有一个疑问，这些多实现或少实现的接口和类会对我们linkedlist的特点产生影响吗？这里我们先将这个疑问放在心里，我们先走正常的流程，先把linkedlist的源码看完（主要是要解释这些东西看deque的源码，还要去看collections里面的逻辑，我怕扯远了）
第5-7行：定义记录元素数量size，因为我们之前说过linkedlist是个双向链表，所以这里定义了链表链表头节点first和链表尾节点last
第60-70行：定义一个节点node类，next表示此节点的后置节点，prev表示侧节点的前置节点，element表示元素值
第22行：检查当前的下标是否越界，因为是在构造函数中所以我们这边的index为0，且size也为0
第24-29行：将集合c转化为数组a，并获取集合的长度；定义节点pred、succ，pred用来记录前置节点，succ用来记录后置节点
第70-89行：node()方法是获取linkedlist中第index个元素，且根据index处于前半段还是后半段 进行一个折半，以提升查询效率
第30-36行：如果index==size，则将元素追加到集合的尾部，pred = last将前置节点pred指向之前结合的尾节点，如果index！=size表明是插入集合，通过node(index)获取当前要插入index位置的节点，且pred = succ.prev表示将前置节点指向于当前要插入节点位置的前置节点
第38-46行：链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作，第40行以前置节点 和 元素值e，构建new一个新节点；第41行如果前置节点是空，说明是头结点，且将成员变量first指向当前节点，如果不是头节点，则将上一个节点的尾节点指向当前新建的节点；第45行将当前的节点为前置节点了，为下次添加节点做准备。这些走完基本上我们的新节点也都创建出来了，可能这块代码有点绕，大家多看看
第48-53行：循环结束后，判断如果后置节点是null， 说明此时是在队尾添加的，设置一下队列尾节点last，如果不是在队尾，则更新之前插入位置节点的前节点和当前要插入节点的尾节点
第55-56行：修改当前集合数量、修改modcount记录值
ok,虽然说是分析的构造函数的源码，但是把node(int index)、addall(int index, collection<? extends e> c)方法也都看了，所以来小结一下：链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作；通过下标index来获取节点node是采用的折半法来提升效率的
2.2 增加元素
常见的方法有以下三种
|
1 2 3 |
linkedlist.add(e e) linkedlist.add( int index, e element) linkedlist.addall(collection<? extends e> c) |
来看看具体的源码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public boolean add(e e) { linklast(e); return true ; }
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++; }
public void add( int index, e element) { checkpositionindex(index);
if (index == size) linklast(element); else linkbefore(element, node(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) { return addall(size, c); } |
第2、6-16行：创建一个newnode它的prev指向之前队尾节点last，并记录元素值e，之前的队尾节点last的next指向当前节点，size自增，modcount自增
第18-20，27-38行：首先去检查下标是否越界，然后判断如果加入的位置刚好位于队尾就和我们add（e element）的逻辑一样了，如果不是则需要通过 node(index)函数定位出当前位于index下标的node，再通过linkbefore()函数创建出newnode将其插入到原先index位置
第40-42行：就是我们在构造函数中看过的批量加入元素的方法
ok，添加元素也很简单，如果是在队尾进行添加的话只需要创建一个新node将其前置节点指向之前的last，如果是在队中添加节点，首选拆散原先的index-1、index、index+1之间的联系，新建节点插入进去即可。
2.3 删除元素
常见方法有以下这几个方法
|
1 2 3 |
linkedlist.remove( int index) linkedlist.remove(object o) linkedlist.remove(collection<?> c) |
源码如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
public e remove( int index) { checkelementindex(index); return unlink(node(index)); }
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 ; }
x.item = null ; size--; modcount++; return element; }
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 boolean removeall(collection<?> c) { objects.requirenonnull(c); boolean modified = false ; iterator<?> it = iterator(); while (it.hasnext()) { if (c.contains(it.next())) { it.remove(); modified = true ; } } return modified; } |
第1-4，6-30行：首先根据index通过方法值node(index)来确定出集合中的下标是index的node，咋们主要看unlink()方法，代码感觉很多，其实只是将当前要删除的节点node的头结点的尾节点指向node的尾节点、将node的尾结点的头节点指向node的头节点，可能有点绕（哈哈），看一下代码基本上就可以理解了，然后将下标为index的node置空，供gc回收
第32-49行：首先判断一下当前要删除的元素o是否为空，然后进行for循环定位出当前元素值等于o的节点node，然后再走的逻辑就是上面我们看到过的unlink()方法，也很简单，比remove(int index) 多了一步
第51-62行：这一块因为涉及到迭代器iterator，而我们linkedlist使用的是listitr，这个后面我们将迭代器的时候一起讲，不过大致的逻辑是都可以看懂的，和我们的arraylist的迭代器方法的含义一样的，可以先那样理解
ok，小结一下， 按下标删，也是先根据index找到node，然后去链表上unlink掉这个node。 按元素删，会先去遍历链表寻找是否有该node，考虑到允许null值，所以会遍历两遍，然后再去unlink它。
2.5 修改元素
|
1 2 3 4 5 6 7 |
public e set( int index, e element) { checkelementindex(index); node<e> x = node(index); e oldval = x.item; x.item = element; return oldval; } |
只有这一种方法，首先检查下标是否越界，然后根据下标获取当前node，然后修改节点中元素值item，超级简单
2.6 查找元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public e get( int index) { checkelementindex(index); //判断是否越界 [0,size) return node(index).item; //调用node()方法 取出 node节点， }
public int indexof(object o) { int index = 0 ; if (o == null ) { for (node<e> x = first; x != null ; x = x.next) { if (x.item == null ) return index; index++; } } else { for (node<e> x = first; x != null ; x = x.next) { if (o.equals(x.item)) return index; index++; } } return - 1 ; }
public int lastindexof(object o) { int index = size; if (o == null ) { for (node<e> x = last; x != null ; x = x.prev) { index--; if (x.item == null ) return index; } } else { for (node<e> x = last; x != null ; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return - 1 ; } |
获取元素的源码也很简单，主要是通过node(index)方法获取节点，然后获取元素值，indexof和lastindexof方法的区别在于一个是从头向尾开始遍历，一个是从尾向头开始遍历
2.7 迭代器
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
public iterator<e> iterator() { return listiterator(); }
public listiterator<e> listiterator() { return listiterator( 0 ); }
public listiterator<e> listiterator( final int index) { rangecheckforadd(index);
return new listitr(index); }
private class listitr extends itr implements listiterator<e> { listitr( int index) { cursor = index; }
public boolean hasprevious() { return cursor != 0 ; }
public e previous() { checkforcomodification(); try { int i = cursor - 1 ; e previous = get(i); lastret = cursor = i; return previous; } catch (indexoutofboundsexception e) { checkforcomodification(); throw new nosuchelementexception(); } }
public int nextindex() { return cursor; }
public int previousindex() { return cursor- 1 ; }
public void set(e e) { if (lastret < 0 ) throw new illegalstateexception(); checkforcomodification();
try { abstractlist. this .set(lastret, e); expectedmodcount = modcount; } catch (indexoutofboundsexception ex) { throw new concurrentmodificationexception(); } }
public void add(e e) { checkforcomodification();
try { int i = cursor; abstractlist. this .add(i, e); lastret = - 1 ; cursor = i + 1 ; expectedmodcount = modcount; } catch (indexoutofboundsexception ex) { throw new concurrentmodificationexception(); } } } |
可以看到，其实最后使用的迭代器是使用的listiterator类，且集成自itr，而itr类就是我们昨天arraylist内部使用的类，hasnext()方法和我们之前的一样，判断不等于size大小，然后next()获取元素主要也是e next = get(i);这行代码，这样就又走到我们之前的获取元素的源码当中，获得元素值。
ok，这样我们上面的基本方法都看完了，再来看看我们上面遗留的问题，首先来看deque接口有什么作用，我们来一起看看
deque 是 double ended queue (双端队列) 的缩写,读音和 deck 一样，蛋壳。
deque 继承自 queue,直接实现了它的有 linkedlist, araydeque, concurrentlinkeddeque 等。
deque 支持容量受限的双端队列，也支持大小不固定的。一般双端队列大小不确定。
deque 接口定义了一些从头部和尾部访问元素的方法。比如分别在头部、尾部进行插入、删除、获取元素。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public interface deque<e> extends queue<e> { void addfirst(e e); //插入头部，异常会报错 boolean offerfirst(e e); //插入头部，异常不报错 e getfirst(); //获取头部，异常会报错 e peekfirst(); //获取头部，异常不报错 e removefirst(); //移除头部，异常会报错 e pollfirst(); //移除头部，异常不报错
void addlast(e e); //插入尾部，异常会报错 boolean offerlast(e e); //插入尾部，异常不报错 e getlast(); //获取尾部，异常会报错 e peeklast(); //获取尾部，异常不报错 e removelast(); //移除尾部，异常会报错 e polllast(); //移除尾部，异常不报错 } |
deque也就是一个接口，上面是接口里面的方法，然后了解deque就必须了解queue
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public interface queue<e> extends collection<e> { //往队列插入元素，如果出现异常会抛出异常 boolean add(e e); //往队列插入元素，如果出现异常则返回false boolean offer(e e); //移除队列元素，如果出现异常会抛出异常 e remove(); //移除队列元素，如果出现异常则返回null e poll(); //获取队列头部元素，如果出现异常会抛出异常 e element(); //获取队列头部元素，如果出现异常则返回null e peek(); } |
然后我们知道linkedlist实现了deque接口，也就是说可以使用linkedlist实现栈和队列的功能，让写写看
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
package com.ysten.leakcanarytest;
import java.util.collection; import java.util.linkedlist;
/** * desc : 实现栈 * time : 2018/10/31 0031 19:07 * * @author : wangjitao */ public class stack<t> { private linkedlist<t> stack;
//无参构造函数 public stack() { stack= new linkedlist<t>(); } //构造一个包含指定collection中所有元素的栈 public stack(collection<? extends t> c) { stack= new linkedlist<t>(c); } //入栈 public void push(t t) { stack.addfirst(t); } //出栈 public t pull() { return stack.remove(); } //栈是否为空 boolean isempty() { return stack.isempty(); }
//打印栈元素 public void show() { for (object o:stack) system.out.println(o); } } |
测试功能
|
1 2 3 4 5 6 7 8 |
public static void main(string[] args){ stack<string> stringstack = new stack<>(); stringstack.push( "1" ); stringstack.push( "2" ); stringstack.push( "3" ); stringstack.push( "4" ); stringstack. show(); } |
打印结果如下：
4
3
2
1
队列的实现类似的，大家可以下来自己写一下，然后继续我们的问题，实现deque接口和实现randomaccess接口有什么区别，我们上面看了deque接口，实现deque接口可以拥有双向链表功能，那我们再来看看randomaccess接口
|
1 2 |
public interface randomaccess { } |
发现什么都没有，原来randomaccess接口是一个标志接口（marker），然而实现这个接口有什么作用呢？
答案是只要list集合实现这个接口，就能支持快速随机访问，然而又有人问，快速随机访问是什么东西？有什么作用？
google是这样定义的：给可以提供随机访问的list实现去标识一下，这样使用这个list的程序在遍历这种类型的list的时候可以有更高效率。仅此而已。
这时候看一下我们collections类中的binarysearch方法
|
1 2 3 4 5 6 |
int binarysearch(list<? extends comparable<? super t>> list, t key) { if (list instanceof randomaccess || list.size()<binarysearch_threshold) return collections.indexedbinarysearch(list, key); else return collections.iteratorbinarysearch(list, key); } |
可以看到这时候去判断了如果当前集合实现了randomaccess接口就会走collections.indexedbinarysearch方法，那么我们来看一下collections.indexedbinarysearch()方法和collections.iteratorbinarysearch()的区别是什么呢？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
int indexedbinarysearch(list<? extends comparable<? super t>> list, t key) { int low = 0 ; int high = list.size()- 1 ;
while (low <= high) { int mid = (low + high) >>> 1 ; comparable<? super t> midval = list.get(mid); int cmp = midval测试数据pareto(key);
if (cmp < 0 ) low = mid + 1 ; else if (cmp > 0 ) high = mid - 1 ; else return mid; // key found } return -(low + 1 ); // key not found }
int iteratorbinarysearch(list<? extends comparable<? super t>> list, t key) { int low = 0 ; int high = list.size()- 1 ; listiterator<? extends comparable<? super t>> i = list.listiterator();
while (low <= high) { int mid = (low + high) >>> 1 ; comparable<? super t> midval = get(i, mid); int cmp = midval测试数据pareto(key);
if (cmp < 0 ) low = mid + 1 ; else if (cmp > 0 ) high = mid - 1 ; else return mid; // key found } return -(low + 1 ); // key not found } |
通过查看源代码，发现实现randomaccess接口的list集合采用一般的for循环遍历，而未实现这接口则采用迭代器
，那现在让我们以linkedlist为例子看一下，通过for循环、迭代器、removefirst和removelast来遍历的效率（之前忘记写这一块了，顺便一块先写了对于linkedlist那种访问效率要高一些）
迭代器遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 |
linkedlist linkedlist = new linkedlist(); for ( int i = 0 ; i < 100000 ; i++){ linkedlist.add(i); } // 迭代器遍历 long start = system.currenttimemillis(); iterator iterator = linkedlist.iterator(); while (iterator.hasnext()){ iterator.next(); } long end = system.currenttimemillis(); system.out.println( "iterator：" + (end - start) + "ms" ); |
打印结果：iterator：28ms
for循环get遍历
|
1 2 3 4 5 6 7 |
// 顺序遍历(随机遍历) long start = system.currenttimemillis(); for ( int i = 0 ; i < linkedlist.size(); i++){ linkedlist.get(i); } long end = system.currenttimemillis(); system.out.println( "for ：" + (end - start) + "ms" ); |
打印结果 for ：6295ms
使用增强for循环
|
1 2 3 4 |
long start = system.currenttimemillis(); for (object i : linkedlist); long end = system.currenttimemillis(); system.out.println( "增强for ：" + (end - start) + "ms" ); |
输出结果 增强for ：6ms
removefirst来遍历
|
1 2 3 4 5 6 |
long start = system.currenttimemillis(); while (linkedlist.size() != 0 ){ linkedlist.removefirst(); } long end = system.currenttimemillis(); system.out.println( "removefirst ：" + (end - start) + "ms" ); |
输出结果 removefirst ：3ms
综上结果可以看到，遍历linkedlist时，使用removefirst()或removelast()效率最高，而for循环get()效率最低，应避免使用这种方式进行。应当注意的是，使用removefirst()或removelast()遍历时，会删除原始数据，若只单纯的读取，应当选用迭代器方式或增强for循环方式。
ok，上述的都是只针对linkedlist而言测试的，然后我们接着上面的randomaccess接口来讲，看看通过对比arraylist的for循环和迭代器遍历看看访问效率
arraylist的for循环
|
1 2 3 4 5 6 |
long start = system.currenttimemillis(); for ( int i = 0 ; i < arraylist.size(); i++) { arraylist.get(i); } long end = system.currenttimemillis(); system.out.println( "for ：" + (end - start) + "ms" ); |
输出结果 for ：3ms
arraylist的迭代遍历
|
1 2 3 4 5 6 7 |
long start = system.currenttimemillis(); iterator iterable = arraylist.iterator() ; while (iterable.hasnext()){ iterable.next(); } long end = system.currenttimemillis(); system.out.println( "for ：" + (end - start) + "ms" ); |
输出结果 for ：6ms
所以让我们来综上对比一下
arraylist
普通for循环：3ms
迭代器：6ms
linkedlist
普通for循环：6295ms
迭代器：28ms
从上面数据可以看出，arraylist用for循环遍历比iterator迭代器遍历快，linkedlist用iterator迭代器遍历比for循环遍历快,所以对于不同的list实现类，遍历的方式有所不用，randomaccess接口这个空架子的存在，是为了能够更好地判断集合是否arraylist或者linkedlist，从而能够更好选择更优的遍历方式，提高性能！
（在这里突然想起在去年跳槽的时候，有家公司的面试官问我，list集合的哪一种遍历方式要快一些，然后我说我没有每个去试过，结果那位大佬说的是for循环遍历最快，还叫我下去试试，现在想想，只有在集合是arraylist的时候for循环才最快，对于linkedlist来说for循环反而是最慢的，那位大佬，你欠我一声对不起（手动斜眼微笑））
3，上面把我们该看的点都看了，那么我们再来总结总结：
linkedlist 是双向列表，链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。
arraylist基于数组， linkedlist基于双向链表，对于随机访问， arraylist比较占优势，但linkedlist插入、删除元素比较快，因为只要调整指针的指向。针对特定位置需要遍历时，所以linkedlist在随机访问元素的话比较慢。
linkedlist没有实现自己的 iterator，使用的是 listiterator。
linkedlist需要更多的内存，因为 arraylist的每个索引的位置是实际的数据，而 linkedlist中的每个节点中存储的是实际的数据和前后节点的位置。
linkedlist也是非线程安全的，只有在单线程下才可以使用。为了防止非同步访问，collections类里面提供了synchronizedlist()方法。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。
原文链接：https://HdhCmsTestcnblogs测试数据/wjtaigwh/p/9883828.html
查看更多关于Java基于JDK 1.8的LinkedList源码详析的详细内容...