jdk1.8集合框架源码解析（五）LinkedList源码解析

ゝ一世哀愁。 2022-04-10 12:43 331阅读 0赞

# 一、LinkedList数据结构 #

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。

他的数据结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6YXVfaXRkb2c_size_16_color_FFFFFF_t_70][]

# 二、LinkedList的继承体系 #

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List、Deque、Cloneable、Serializable接口

继承AbstractSequentialList

Deque是双端队列

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

下表总结了上述 12 种方法：

<table> 
 <tbody> 
  <tr> 
   <td colspan="1" style="width:55px;">&nbsp;</td> 
   <td colspan="3" style="width:431.5px;"> <p><strong>第一个元素（头部）</strong></p> </td> 
   <td colspan="3" style="width:362.5px;"> <p>最后一个元素（尾部）</p> </td> 
  </tr> 
  <tr> 
   <td style="width:143px;">抛出异常</td> 
   <td style="width:121px;">特殊值</td> 
   <td style="width:135px;">返回值</td> 
   <td style="width:144px;">抛出异常</td> 
   <td style="width:156px;">特殊值</td> 
   <td>返回值</td> 
  </tr> 
  <tr> 
   <td style="width:55px;">插入</td> 
   <td style="width:143px;"> <p><a rel="nofollow"><code>addFirst(e)</code></a></p> </td> 
   <td style="width:121px;"> <p><a rel="nofollow"><code>offerFirst(e)</code></a></p> </td> 
   <td style="width:135px;"> <p>如果元素被添加到此双端队列，则返回 true，否则返回 false</p> </td> 
   <td style="width:144px;"> <p><a rel="nofollow"><code>addLast(e)</code></a></p> </td> 
   <td style="width:156px;"> <p><a rel="nofollow"><code>offerLast(e)</code></a></p> </td> 
   <td> <p>如果元素被添加到此双端队列，则返回 true，否则返回 false</p> </td> 
  </tr> 
  <tr> 
   <td style="width:55px;">移除</td> 
   <td style="width:143px;"> <p><a rel="nofollow"><code>removeFirst()</code></a></p> </td> 
   <td style="width:121px;"> <p><a rel="nofollow"><code>pollFirst()</code></a></p> </td> 
   <td style="width:135px;"> <p>如果此双端队列为空，则返回 null</p> </td> 
   <td style="width:144px;"> <p><a rel="nofollow"><code>removeLast()</code></a></p> </td> 
   <td style="width:156px;"> <p><a rel="nofollow"><code>pollLast()</code></a></p> </td> 
   <td> <p>如果此双端队列为空，则返回 null</p> </td> 
  </tr> 
  <tr> 
   <td style="width:55px;">检查</td> 
   <td style="width:143px;"> <p><a rel="nofollow"><code>getFirst()</code></a></p> </td> 
   <td style="width:121px;"> <p><a rel="nofollow"><code>peekFirst()</code></a></p> </td> 
   <td style="width:135px;"> <p>如果此双端队列为空，则返回 null。</p> </td> 
   <td style="width:144px;"> <p><a rel="nofollow"><code>getLast()</code></a></p> </td> 
   <td style="width:156px;"> <p><a rel="nofollow"><code>peekLast()</code></a></p> </td> 
   <td> <p>如果此双端队列为空，则返回 null。</p> </td> 
  </tr> 
 </tbody> 
</table>

在作为双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

<table> 
 <tbody> 
  <tr> 
   <td><strong>Queue 方法</strong></td> 
   <td><strong>等效 Deque 方法</strong></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>add(e)</code></a></td> 
   <td><a rel="nofollow"><code>addLast(e)</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>offer(e)</code></a></td> 
   <td><a rel="nofollow"><code>offerLast(e)</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>remove()</code></a></td> 
   <td><a rel="nofollow"><code>removeFirst()</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>poll()</code></a></td> 
   <td><a rel="nofollow"><code>pollFirst()</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>element()</code></a></td> 
   <td><a rel="nofollow"><code>getFirst()</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>peek()</code></a></td> 
   <td><a rel="nofollow"><code>peekFirst()</code></a></td> 
  </tr> 
 </tbody> 
</table>

双端队列也可用作 LIFO（后进先出）堆栈。

在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

<table> 
 <tbody> 
  <tr> 
   <td><strong>堆栈方法</strong></td> 
   <td><strong>等效 Deque 方法</strong></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>push(e)</code></a></td> 
   <td><a rel="nofollow"><code>addFirst(e)</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>pop()</code></a></td> 
   <td><a rel="nofollow"><code>removeFirst()</code></a></td> 
  </tr> 
  <tr> 
   <td><a rel="nofollow"><code>peek()</code></a></td> 
   <td><a rel="nofollow"><code>peekFirst()</code></a></td> 
  </tr> 
 </tbody> 
</table>

AbstractList

AbstractList类中与随机访问类相对的另一套系统，采用的是在迭代器的基础上实现的get、set、add和remove方法。

为了实现这个列表。仅仅需要拓展这个类，并且提供ListIterator和size方法。   
对于不可修改的List，编程人员只需要实现Iterator的hasNext、next和hasPrevious、previous和index方法   
对于可修改的List还需要额外实现Iterator的的set的方法   
对于大小可变的List，还需要额外的实现Iterator的remove和add方法

# 三、LinkedList的字段 #

//链表大小
        transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        //头结点
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        //尾节点
        transient Node<E> last;

LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

# 四、内部类Node<E>源码解析 #

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;
            }
        }

# 五、LinkedList构造函数解析 #

public LinkedList() {}
        public LinkedList(Collection<? extends E> c) {
            //调用无参构造函数，构造一个空的链表
            this();
            // 添加集合中所有的元素
            addAll(c);
        }

# 六、核心函数的分析 #

## 6.1 add函数分析 ##

<table>  add函数  
 <tbody> 
  <tr> 
   <td style="width:394px;">函数</td> 
   <td style="width:455px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:394px;">public void addFirst(E e)</td> 
   <td style="width:455px;"> <p>将指定元素插入此列表的开头</p> </td> 
  </tr> 
  <tr> 
   <td style="width:394px;">public void addLast(E e)</td> 
   <td style="width:455px;">将指定元素添加到此列表的结尾</td> 
  </tr> 
  <tr> 
   <td style="width:394px;">public boolean add(E e)</td> 
   <td style="width:455px;">将指定元素添加到此列表的结尾</td> 
  </tr> 
  <tr> 
   <td style="width:394px;">&nbsp;public boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td style="width:455px;"> <p>添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序</p> </td> 
  </tr> 
  <tr> 
   <td style="width:394px;">&nbsp;public boolean addAll(int index, Collection&lt;? extends E&gt; c)&nbsp;</td> 
   <td style="width:455px;"> <p>将指定 collection 中的所有元素从指定位置开始插入此列表。移动当前在该位置上的元素（如果有），所有后续元素都向右移（增加其索引）。新元素将按由指定 collection 的迭代器返回的顺序在列表中显示。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:394px;">&nbsp;public void add(int index, E element)</td> 
   <td style="width:455px;"> <p>在此列表中指定的位置插入指定的元素。移动当前在该位置处的元素（如果有），所有后续元素都向右移</p> </td> 
  </tr> 
 </tbody> 
</table>

### 6.1.1 addFirst(E e) ###

public void addFirst(E e) {
             linkFirst(e);
        }
    
        private void linkFirst(E e) {
            //获取当前第一个节点
            final Node<E> f = first;
            //创建新节点，其上个节点为null，下个节点为 f（当前首节点）
            final Node<E> newNode = new Node<>(null, e, f);
            //首节点置为新创建的节点
            first = newNode;
            //如果首节点为空代表链表为空，尾节点也为新创建的节点
            if (f == null)
                last = newNode;
            else
                //新节点与f相连
                f.prev = newNode;
            //修改集合大小和修改次数
            size++;
            modCount++;
        }

### 6.1.2  addLast(E e) ###

public void addLast(E e) {
            linkLast(e);
        }
        void linkLast(E e) {
            //获取最后一个节点
            final Node<E> l = last;
            //创建一个新节点，其前一个节点为l，后一个节点为null
            final Node<E> newNode = new Node<>(l, e, null);
            //最后的节点置为 newNode
            last = newNode;
            //如果最后的节点为空，代表链表为空，最后一个节点也是第一个节点
            if (l == null)
                first = newNode;
            else
                //新节点和最后的节点相连
                l.next = newNode;
            size++;
            modCount++;
        }

### 6.1.3  add(E e) ###

public boolean add(E e) {
            linkLast(e);
            return true;
        }

add(E e)函数和 addLast(E e)原理是一样的

### 6.1.4  addAll(Collection<? extends E> c) ###

public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }

public boolean addAll(int index, Collection<? extends E> c) {
            //检查索引是否越界
            checkPositionIndex(index);
            //把c转换为数组
            Object[] a = c.toArray();
            // 保存集合大小
            int numNew = a.length;
            // 集合为空，直接返回
            if (numNew == 0)
                return false;
            //前节点，后节点
            Node<E> pred, succ;
            //如果插入的位置为链表的尾部
            if (index == size) {
                //后节点为null
                succ = null;
                //前节点为尾节点
                pred = last;
            } else {
                //查找到索引节点，赋给后节点
                succ = node(index);
                //后节点的前节点为前节点
                pred = succ.prev;
            }
            //经过上述操作已经确定插入点前后元素了
            //遍历数组，构建节点，
            for (Object o : a) {
                //把o进行类型转换
                @SuppressWarnings("unchecked") E e = (E) o;
                //构建节点上个节点为pred
                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
            size += numNew;
            modCount++;
            return true;
        }

上述用到了node(int index)这个方法查找某个位置上的节点

Node<E> node(int index) {
            // assert isElementIndex(index);
            // 判断index位置在链表前半段还是后半段
            if (index < (size >> 1)) {
                // 从头结点开始正向遍历
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                //返回index位置的node
                return x;
            } else {
                Node<E> x = last;
                // 从尾结点开始反向遍历
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                //返回index位置的node
                return x;
            }
        }

## 6.2 clear函数 ##

public void clear() {
            // Clearing all of the links between nodes is "unnecessary", but:
            // - helps a generational GC if the discarded nodes inhabit
            //   more than one generation
            // - is sure to free memory even if there is a reachable Iterator
            //遍历链表把node的所有属性置空
            for (Node<E> x = first; x != null; ) {
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            first = last = null;
            size = 0;
            modCount++;
        }

## 6.3 contains函数 ##

public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
        public int indexOf(Object o) {
            int index = 0;
            //如果元素为空
            if (o == null) {
                //从首节点开始遍历，当节点位置的元素为null返回索引
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                //从首节点开始遍历，当节点位置的元素为和传入的元素相等时（通过equals方法判断）返回索引
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }

contains方法就是遍历元素通过equals方法比较是否包含

## 6.4 get函数 ##

public E get(int index) {
            checkElementIndex(index);
            //依赖于node(index)函数
            return node(index).item;
        }

## 6.5 remove函数 ##

public boolean remove(Object o) {
            if (o == null) {
                //如果o为null遍历链表找到null，调用 unlink(Node<E> x)断开连接
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                //遍历链表找到o，调用 unlink(Node<E> x)断开连接
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }

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;
            //如果前驱为null，代表断开的是首节点
            if (prev == null) {
                //首节点的下个节点为首节点
                first = next;
            } else {
                //前驱节点的下个节点（目前是当前节点）置为后继节点
                prev.next = next;
                //当前节点的前驱置为空
                x.prev = null;
            }
             //如果后继为null，代表断开的是尾节点
            if (next == null) {
                //尾节点的上个节点为尾节点
                last = prev;
            } else {
                //后继节点的上个节点（目前是当前节点）为前驱节点
                next.prev = prev;
                //当前节点的后继置为空
                x.next = null;
            }
            //节点x的前驱后继包括元素都置为空
            x.item = null;
            //修正size
            size--;
            modCount++;
            return element;
        }

### 小结  ###

在addAll函数中传入一个集合参数和插入位置，总是要不集合转成数组去操作，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？![2019010817041555.png][]

1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。

2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合

# 七、内部类分析 #

**未完...**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6YXVfaXRkb2c_size_16_color_FFFFFF_t_70]: /images/20220330/8e3605498b7a435e9f11eac02fcd2018.png
[2019010817041555.png]: /images/20220330/ea247a9c9f004a92ba867e86e7d9633a.png