《Java源码解析》集合框架List之LinkedList

我就是我 2022-07-13 03:08 257阅读 0赞

# LinkedList #

## 1.首先看看 **LinkedList** 的继承体系的结构 ##

![LinkedList的类继承结构][LinkedList]

LinkedList主要是继承自AbstractSequentialList抽象类并实现了List接口、实现了Cloneable和Serializable接口使得ArrayList具有克隆和序列化的功能、实现了Deque接口和Queue因此具有队列的性质。

## 2.重要属性 ##

LinkedList的内部是基于双向链表实现的，对于每一个元素其实就是一个结点，LinkedList中对于结点的定义是通过LinkedList内部的一个静态类实现的：源码如下

private static class Node<E> { 
        E item;//节点中保存的元素对象
        Node<E> next;//当前结点的后继
        Node<E> prev;//当前结点的前驱
        //构造函数，传入Node的三个属性
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

也就是一个元素存储单元包括三个部分，具体的如下图：  
![Node结点的存储结构][Node]

下面再看看LinkedList中有哪些重要的类属性:

//List的容量
    transient int size = 0;
    //指向LinkedList中第一个结点
    transient Node<E> first;
    //指向LinkedList中最后一个结点
    transient Node<E> last;

由于LinkedList是基于双向链表实现的，所以并不像ArrayList中那样需要数组来存储数据。

## 3. 五个关注点在LinkedList上面的答案 ##

**LinkedList**

<table> 
 <thead> 
  <tr> 
   <th>关注点</th> 
   <th align="center">结论</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>集合底层实现的数据结构</td> 
   <td align="center">双向链表</td> 
  </tr> 
  <tr> 
   <td>集合中元素是否允许为空</td> 
   <td align="center">允许</td> 
  </tr> 
  <tr> 
   <td>是否允许重复的数据</td> 
   <td align="center">允许</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td align="center">有序</td> 
  </tr> 
  <tr> 
   <td>是否线程安全。</td> 
   <td align="center">非线程安全</td> 
  </tr> 
 </tbody> 
</table>

## 4. LinkedList的构造函数 ##

LinkedList有两个构造函数：

//空的构造函数
    public LinkedList() {
    }
    
    //指定集合来初始化LinkedList
    public LinkedList(Collection<? extends E> c) {
        this();//调用空的构造函数
        addAll(c);//调用内部方法addAll()将集合c的元素全部添加到LinkedList中
    }

对于有参数的构造函数，主要是调用了`addAll(c);` 这个方法，这个方法内部又是直接调用了  
`addAll(size, c);` 这个方法表示在size个元素后面添加c集合的元素。  
下面我们看看`addAll(int index, Collection<? extends E> c)` 这个函数的源码：

public boolean addAll(int index, Collection<? extends E> c) {
        //检查index的位置是否在0-size之间，因为添加的集合所有结点只能插入在这些位置的后面
        checkPositionIndex(index);
        //获取到集合中的每一个结点的数组
        Object[] a = c.toArray();
        //获取集合c的大小
        int numNew = a.length;
        //如果集合为空，直接返回false
        if (numNew == 0)
            return false;
        /**pred：用于表示即在此结点位置的后面插入新的结点 succ：用于表示在此结点的前面位置插入结点，即插入之前此时此刻链表中的index位置的节点；如果index==size，则在尾结点处插入 如果index==size，则在尾结点处插入 否则：找到索引为index（从零开始）的位置节点 */
        //pred表示插入点的前驱结点；succ表示插入点的后继结点
        Node<E> pred, succ;
        //在List的末尾插入
        if (index == size) {
            succ = null;//这时后继是null
            pred = last;
        } else {
       //在List的中间插入
            //获取index位置的Node，然后从index位置之前开始插入，这个node()函数采用了一步的二分查找思想：先判断index在1/2 size的前面还是后面，然后分别在两部分不断求后继(或则是前驱)来找到index位置的结点。这种分段的思想主要是为了提高性能。
            succ = node(index);
            pred = succ.prev;//获取插入点的前驱
        }
        //foreach来迭代插入c中的节点
        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;//predict结点后移
        }
        /* 在尾结点加入时，pred所指向的就是last的位置， 否则，则将pred与succ的指向要进行连接起来。 */
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
    
        size += numNew;//size自己集合中元素的个数
        modCount++;//List的修改次数自加1
        return true;
    }

下面给出node(index)的实现源码，这个函数在后面用得比较多：

//返回指定索引index位置的元素
    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;
        }
    }

## 5.LinkedList关键函数之add(E e) ##

LinkedList的实现源码如下：其实也在List的末尾添加一个元素;

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

可知上面的源码主要是调用了`linkLast(E e)` ，源码如下：

void linkLast(E e) {
        //new一个新的节点，然后插入在List的最后。
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //l为空，表示list最开始是空的list，所以first指向newNode
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;//List的元素个数自增
        modCount++;//list修改次数标记自增
    }

## 6.LinkedList关键函数之add(int index, E element) ##

该函数是在指定的索引index位置插入一个元素，

public void add(int index, E element) {
        //首先检查index位置的合法性，不能越界size
        checkPositionIndex(index);
        //如果index为size，那么就在List的末尾插入该元素
        if (index == size)
            linkLast(element);
        else//在index位置之前
            linkBefore(element, node(index));
    }

由注释可知，如果index为size就在list的末尾插入元素，反之就在index位置所在结点前插入元素。下面来分析一下`linkBefore(element, node(index));` 该函数的源码解析：

/** 在succ元素前插入元素e */
    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++;
    }

稍微看一下就知道和linkLast()函数差不多的实现原理，这里就不分析了。

## 7. get(int index)和set(int index, E element) 操作 ##

先看看get和set的源码：

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

其实都是比较简单的，一眼都能看出是什么意思，核心的还是调用了node(index)函数，该函数已在上文分析过了。

## 8. clear()函数 ##

先看源码再说话：

public void clear() {
        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++;
    }

这段代码的实质就是将List中所有的Node全部置为Null。

## 9. LinkedList并没有subList()这个的实现。 ##

[LinkedList]: /images/20220713/e17174cb58264ae1b007858c140fd112.png
[Node]: /images/20220713/7a9deaa24fc945b6a288b074601b50e0.png