本文共 8713 字，大约阅读时间需要 29 分钟。

简介

LinkedList底层使用双向链表结构，有一个头结点和一个尾结点。这就意味着我们既可以从头开始正向遍历，也可以从尾开始逆向遍历。从它的继承关系和实现，extends AbstractSequentialList implements List, Deque, Cloneable, Serializable ，可以看出来和ArrayList有相同的也有不同的。

它继承了AbstractSequentialList抽象类，在遍历LinkedList的问题上，官方更推荐使用迭代器。毕竟，每次遍历都要从链表的头部或者尾部进行。 它实现了Deque，Deque是一个双端队列，即LinkedList是一个双端队列的实现。

先看基本属性

public class LinkedList
   
     extends AbstractSequentialList
    
      implements List
     
      , Deque
      
       , Cloneable, Serializable {
       //集合元素的数量    transient int size;    //链表的头结点    transient LinkedList.Node
       
         first;    //链表的尾结点    transient LinkedList.Node
        
          last; private static final long serialVersionUID = 876323262645176354L;
        
       
      
     
    
   

已经很清晰了，集合元素size，链表头结点、尾结点。接下来看看Node

Node类

private static class Node
   
     {
       //元素的值    E item;    //后继结点，可以理解为指向当前节点的后一个节点的指针    LinkedList.Node
    
      next;    //前驱结点，可以理解为指向当前节点的前一个节点的指针    LinkedList.Node
     
       prev;    Node(LinkedList.Node
      
        var1, E var2, LinkedList.Node
       
         var3) {
           this.item = var2;        this.next = var3;        this.prev = var1;    }}
       
      
     
    
   

通过next和prev这两个结点，足以证明linkedList是由双向链表实现的。

构造方法

LinkedList就提供了两个构造方法，ArrayList比它多一个通过设置初始化容量来初始化类。之所以LinkedList没提供这个构造，还是取决于它的底层结构——双向链表。当有新元素加入，就会链接新的节点，它的容量是跟随着元素的个数的变化而动态变化的。

无参数构造

public LinkedList() {
       this.size = 0;}

集合类型参数构造

如果传入的是集合的话用addAll方法把集合全部加入链表中

public LinkedList(Collection
    var1) {
       this();    this.addAll(var1);}

addAll方法

addAll方法把集合加入链表中：

//以size为下标，插入集合的所有元素public boolean addAll(Collection
    var1) {
       return this.addAll(this.size, var1);}//传入下标、集合对象public boolean addAll(int var1, Collection
    var2) {
       //先检查是否越界，几乎所有的涉及到在指定位置添加或者删除或修改操作都需要判断传进来的参数是否合法    this.checkPositionIndex(var1);    //然后把集合对象全部转换成数组，然后为数组添加新引用    Object[] var3 = var2.toArray();    //数组的长度    int var4 = var3.length;    //如果待添加的集合为空，直接返回    if (var4 == 0) {
           return false;    } else {
           //前置结点        LinkedList.Node var5;        //后置结点        LinkedList.Node var6;        //在链表尾部追加数据        if (var1 == this.size) {
               var6 = null;//尾部数据一定是null            var5 = this.last;//前置结点是队尾        } else {
               var6 = this.node(var1);            var5 = var6.prev;        }        Object[] var7 = var3;        int var8 = var3.length;        //批量添加        for(int var9 = 0; var9 < var8; ++var9) {
               Object var10 = var7[var9];            LinkedList.Node var12 = new LinkedList.Node(var5, var10, (LinkedList.Node)null);            if (var5 == null) {
                   this.first = var12;            } else {
                   var5.next = var12;            }            var5 = var12;        }        if (var6 == null) {
               this.last = var5;        } else {
               var5.next = var6;            var6.prev = var5;        }        this.size += var4;        ++this.modCount;        return true;    }}

checkPositionIndex方法

checkPositionIndex方法，检查index是否合法。调用的是isPositionIndex(index)方法，而且我们新添加的元素可能在LinkedList最后一个元素的后面，所以这里允许index<=size。如果不合法，则抛出异常。

//就是看看在区间【0，size】中没private void checkPositionIndex(int var1) {
       if (!this.isPositionIndex(var1)) {
           throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));    }}

outOfBoundsMsg

作为一个辅助方法，返回越界信息

private String outOfBoundsMsg(int index) {        return "Index: "+index+", Size: "+size;    }

isPositionIndex方法

isPositionIndex对index检查是否合法，毕竟新添加的元素可能在LinkedList最后一个元素的后面，所以这里允许index<=size。

private boolean isPositionIndex(int var1) {
       return var1 >= 0 && var1 <= this.size;}

根据index 查询出Node

LinkedList.Node
   
     node(int var1) {
       LinkedList.Node var2;    int var3;    if (var1 < this.size >> 1) {
           var2 = this.first;        for(var3 = 0; var3 < var1; ++var3) {
               var2 = var2.next;        }        return var2;    } else {
           var2 = this.last;        for(var3 = this.size - 1; var3 > var1; --var3) {
               var2 = var2.prev;        }        return var2;    }}
   

常规操作

get方法

短短两行，分以下两步走

public E get(int var1) {
   	//老套路，先check，判断index是否是元素索引    this.checkElementIndex(var1);    //调用node方法    return this.node(var1).item;}

checkElementIndex方法

checkElementIndex方法判断index是否是元素的索引，不是就抛异常：

private void checkElementIndex(int index) {
           if (!isElementIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }

该方法设计的很巧妙啊，判断目标index在哪个结点区域内，然后再去搜索。避免了从头到尾的全量搜索，将性能从O(n)活生生的优化到了O(n/2)的性能去获取一个节点

Node
   
     node(int index) {
       // 目标在前半区间就从head搜索    if (index < (size >> 1)) {
           Node
    
      x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {
   //目标在后半区间就从tail搜索        Node
     
       x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}
     
    
   

set方法

public E set(int var1, E var2) {
   	//跟get一样，先check...    this.checkElementIndex(var1);    //调用node    LinkedList.Node var3 = this.node(var1);    Object var4 = var3.item;    var3.item = var2;    return var4;}

remove

从LinkedList中删除指定元素，且只删除第一次出现的指定的元素，如果指定的元素在集合中不存在，则返回false，否则返回true

public boolean remove(Object var1) {
       LinkedList.Node var2;    //判断Object是否为null分为两种情况,去和LinkedList中的每个元素比较。找到了就删除、返回true，否则返回false    if (var1 == null) {
           for(var2 = this.first; var2 != null; var2 = var2.next) {
               if (var2.item == null) {
                   this.unlink(var2);                return true;            }        }    } else {
           for(var2 = this.first; var2 != null; var2 = var2.next) {
               if (var1.equals(var2.item)) {
                   this.unlink(var2);                return true;            }        }    }    return false;}

indexOf查询

挨个从头开始遍历，获取第一次出现的位置

public int indexOf(Object var1) {
       int var2 = 0;    LinkedList.Node var3;    if (var1 == null) {
           for(var3 = this.first; var3 != null; var3 = var3.next) {
               if (var3.item == null) {
                   return var2;            }            ++var2;        }    } else {
           for(var3 = this.first; var3 != null; var3 = var3.next) {
               if (var1.equals(var3.item)) {
                   return var2;            }            ++var2;        }    }    return -1;}

lastIndexOf方法

这个方法的作用是倒着遍历，然后找到出现的最后一次的位置

public int lastIndexOf(Object var1) {
       int var2 = this.size;    LinkedList.Node var3;    if (var1 == null) {
           for(var3 = this.last; var3 != null; var3 = var3.prev) {
               --var2;            if (var3.item == null) {
                   return var2;            }        }    } else {
           for(var3 = this.last; var3 != null; var3 = var3.prev) {
               --var2;            if (var1.equals(var3.item)) {
                   return var2;            }        }    }    return -1;}

toArray方法

转换为数组

public Object[] toArray() {
       //又建立一个新的数组    Object[] var1 = new Object[this.size];    int var2 = 0;    //挨个遍历，，，然后把每个元素fang放到新的数组里面    for(LinkedList.Node var3 = this.first; var3 != null; var3 = var3.next) {
           var1[var2++] = var3.item;    }    return var1;}

clone方法

首先获取从superClone方法返回的LinkedList对象，接着把该对象的所有域都设置为初始值，然后把LinkedList中所有的内容复制到返回的对象中。

public Object clone() {
           LinkedList
   
     clone = superClone();        // Put clone into "virgin" state        clone.first = clone.last = null;        clone.size = 0;        clone.modCount = 0;        // Initialize clone with our elements        for (Node
    
      x = first; x != null; x = x.next)            clone.add(x.item);        return clone;    }
    
   

superClone方法

@SuppressWarnings("unchecked")    private LinkedList
   
     superClone() {
           try {
               return (LinkedList
    
     ) super.clone();        } catch (CloneNotSupportedException e) {
               throw new InternalError(e);        }    }
    
   

两种迭代器！

ListIterator迭代器

public ListIterator
   
     listIterator(int index) {
           checkPositionIndex(index);        return new ListItr(index);    }
   

Iterator迭代器

public Iterator
   
     descendingIterator() {
           return new DescendingIterator();    }
   

总结一下！

1.Q:LinkedList的底层实现？

A：双向链表嘛，巴拉巴拉… 2.Q：LinkedList是否线程安全？ A：肯定不安全撒，再多线程的环境下，会抛出ConcurrentModificationException异常，其实是checkForComodification方法抛出的，原因就是modCount != expectedModCount；看到这个是不是很熟悉？ArrayList也是这原因导致的嘛！至于解决办法嘛，要么换成ConcurrentLinkedQueue，要么使用 Collections.synchronizedList(new LinkedList()) 3.Q：LinkedList的优缺点？ A：优点嘛就是它对数据的插入、删除效率贼高，这归功于它自己的底层实现——双线链表。增、删不需要移动底层数据结构，只需要修改链表结点指针就可以了… 缺点嘛，遍历效率低。顺便提一下，HashMap也和双链表有关系。 提了LinkedList，不说ArrayList有点不合适了： ArrayList优点：基于数组实现，读取效率高、可null，有序、异步、可重复 缺点：不适合对数据进行频繁的插入、删除操作，因为每次操作都要移动数组中的元素。毕竟是基于动态数组实现的，增、删不能像ArrayList直接修改链表结点指针那么潇洒…