LinkedList实现原理

2019-10-15 本文已影响0人奇点一氪

LinkedList介绍

LinkedList底层所采用的数据结构是链表。链表是由多个节点构成，每个节点都包含三个部分，头部指向上一个元素的节点，中部指向该元素节点，尾部指向下一个元素节点。如下图展示了一个链表的数据结构情况。

image.png

LinkedList是采用链表的方式来实现List接口的，因此在进行insert和remove动作时效率要比ArrayList高。适合用来实现Stack(堆栈)与Queue(队列)。

继承于AbstractSequentialList的双向链表。它可以被当成堆栈、队列或双端队列进行操作。
实现了List接口，能对它进行队列操作。
实现了Deque接口，能当作双端队列使用。
实现了Cloneable接口，覆盖了clone(),能克隆。
实现了java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
是线程不同步的。

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

image.png

LinkedList 集合也实现了Cloneable接口和Serializable接口，分别用来支持克隆以及支持序列化。List 接口也不用多说，定义了一套 List 集合类型的方法规范。

注意:

相对于 ArrayList 集合，LinkedList 集合多实现了一个 Deque 接口，这是一个双向队列接口，双向队列就是两端都可以进行增加和删除操作。

字段属性

一个链表中，第一个节点的头部是null，最后一个节点的尾部是null。

//链表元素（节点）的个数
    transient int size = 0;

    /**
     *指向第一个节点的指针
     */
    transient Node<E> first;

    /**
     *指向最后一个节点的指针
     */
    transient Node<E> last;

LinkedList也是使用size属性来记录集合的元素个数。除此之外还有两个非常重要的属性，一个是first，一个是last。它们都是Node类型。first是用来记录链表头节点，last是用来记录链表尾节点的。
下图是LinkedList内部结构的可视化，能够帮我们更好的理解LinkedList内部的结构。

image.png

上图的 LinkedList 是有四个元素，也就是由 4 个 Node 对象组成，size=4，head 指向第一个elementA,tail指向最后一个节点elementD。

Node类型属性

LinkedList类中有一个内部私有类Node，这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。
源码中的实现是这样的。

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的实现中多次调用。

LinkedList常用方法分析

image.png

LinkedList构造函数

 // 默认构造函数
LinkedList()
// 创建一个LinkedList，保护Collection中的全部元素。
LinkedList(Collection<? extends E> collection)

LinkedList 有两个构造函数，第一个是默认的空的构造函数，第二个是将已有元素的集合Collection 的实例添加到 LinkedList 中，调用的是 addAll() 方法，这个方法下面我们会介绍。

1.addLast(E e)和add(E e)操作：

将指定元素添加到链表尾

image.png

//将元素添加到链表末尾
    public void addLast(E e) {
        linkLast(e);
    }
    //将元素添加到链表末尾
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        final Node<E> l = last;//将l设为尾节点
        final Node<E> newNode = new Node<>(l, e, null);//构造一个新节点，节点上一个节点引用指向尾节点l
        last = newNode;//将尾节点设为创建的新节点
        if (l == null)//如果尾节点为空，表示原先链表为空
            first = newNode;//将头节点设为新创建的节点（尾节点也是新创建的节点）
        else
            l.next = newNode;//将原来尾节点下一个节点的引用指向新节点
        size++;//节点数加1
        modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    }

我们平常使用的add方法，底层实际是调用linkLast方法，该方法是把添加进来的节点当做尾节点的。
构造节点，并把原尾节点放在该节点头部，该节点放在中部，尾部为null，并更新属性last为当前节点。
接着判断原last是否为空，若为空，则代表添加的进来的节点是第一个节点，将first也更新为当前节点，若不为空，需要将原last节点的尾部由空更新为当前节点。最后size++，modCount++。

2.addFirst(E e)操作：

将指定元素添加到链表头

image.png

//将指定的元素附加到链表头节点
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        final Node<E> f = first;//将头节点赋值给 f
        final Node<E> newNode = new Node<>(null, e, f);//将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点
        first = newNode;//将新节点设为头节点，那么原先的头节点 f 变为第二个节点
        if (f == null)//如果第二个节点为空，也就是原先链表是空
            last = newNode;//将这个新节点也设为尾节点（前面已经设为头节点了）
        else
            f.prev = newNode;//将原先的头节点的上一个节点指向新节点
        size++;//节点数加1
        modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    }

3.add(int index, E element)操作：

将指定的元素插入此列表中的指定位置

image.png

//将指定的元素插入此列表中的指定位置
    public void add(int index, E element) {
        //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
        checkPositionIndex(index);

        if (index == size)//如果索引值等于链表大小
            linkLast(element);//将节点插入到尾节点
        else
            linkBefore(element, node(index));
    }
/**
*检查index 是否合法
*/
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

    /**
     * 尾部插入
     */
    void linkLast(E e) {
        final Node<E> l = last;//将l设为尾节点
        final Node<E> newNode = new Node<>(l, e, null);//构造一个新节点，节点上一个节点引用指向尾节点l
        last = newNode;//将尾节点设为创建的新节点
        if (l == null)//如果尾节点为空，表示原先链表为空
            first = newNode;//将头节点设为新创建的节点（尾节点也是新创建的节点）
        else
            l.next = newNode;//将原来尾节点下一个节点的引用指向新节点
        size++;//节点数加1
        modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    }
  /**
    * 相当于查找某个位置的节点（元素）
    */
    Node<E> node(int index) {
        // 算是一种小优化，看需要插入的位置是处于链表的前半部分还是后半部分
        // 如果是前半部分则从头部开始顺序查找插入位置的节点
        if (index < (size >> 1)) {//如果插入的索引在前半部分
            Node<E> x = first;//设x为头节点
            for (int i = 0; i < index; i++)//从开始节点到插入节点索引之间的所有节点向后移动一位
                x = x.next;
            return x;
        } else {//如果插入节点位置在后半部分
            Node<E> x = last;//将x设为最后一个节点
            for (int i = size - 1; i > index; i--)//从最后节点到插入节点的索引位置之间的所有节点向前移动一位
                x = x.prev;
            return x;
        }
    }
/**
  * 关键是这个函数, 在succ之前插入数据
  */
    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;//将pred设为插入节点的上一个节点
        final Node<E> newNode = new Node<>(pred, e, succ);//将新节点的上引用设为pred,下引用设为succ
        succ.prev = newNode;//succ的上一个节点的引用设为新节点
        if (pred == null)//如果插入节点的上一个节点引用为空
            first = newNode;//新节点就是头节点
        else
            pred.next = newNode;//插入节点的下一个节点引用设为新节点
        size++;
        modCount++;
    }

当向LinkedList的index位置添加元素时，首先判断index位置是否合法，合法则顺序查找index位置的节点（元素），此处的查找有一个小小的优化，只需要顺序查找到链表一半位置即可，找到该节点后，则利用链表的特性直接插入元素，因此在性能上要优于ArrayList，首先LinkedList不需要考虑扩容，其次不需要移动插入位置之后的元素。

4.addAll(Collection<? extends E> c)操作：

按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾，此方法还有一个 addAll(int index, Collection<? extends E> c)，将集合 c 中所有元素插入到指定索引的位置。其实
addAll(Collection<? extends E> c) == addAll(size, Collection<? extends E> c)
源码如下：

//按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    //将集合 c 中所有元素插入到指定索引的位置。
    public boolean addAll(int index, Collection<? extends E> c) {
        //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
        checkPositionIndex(index);

        Object[] a = c.toArray();//将集合转换成一个 Object 类型的数组
        int numNew = a.length;
        if (numNew == 0)//如果添加的集合为空，直接返回false
            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;
    }

看到上面向 LinkedList 集合中添加元素的各种方式，我们发现LinkedList 每次添加元素只是改变元素的上一个指针引用和下一个指针引用，而且没有扩容。，对比于 ArrayList ，需要扩容，而且在中间插入元素时，后面的所有元素都要移动一位，两者插入元素时的效率差异很大，下一篇博客会对这两者的效率，以及何种情况选择何种集合进行分析。
还有，每次进行添加操作，都有modCount++ 的操作，

5.get(int index)操作：

get函数是返回index位置节点的数据，同set很类似，也需要遍历到index位置，因此时间复杂度为n/2也即为n，源码实现如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

判断索引"index >= 0 && index < size"
get方法中调用的是checkElementIndex()方法，先对index做合法判断。如果index值不合法，就抛出下标越界异常。
判断完index的合法之后，通过node()方法，获取下标为index的节点，并获取节点的中间部分，item表示的是获取节点中间部分，现在我们来具体看看node()方法是怎么实现。

 /**
    * 相当于查找某个位置的节点（元素）
    */
    Node<E> node(int index) {
        // 算是一种小优化，看需要插入的位置是处于链表的前半部分还是后半部分
        // 如果是前半部分则从头部开始顺序查找插入位置的节点
        if (index < (size >> 1)) {//如果插入的索引在前半部分
            Node<E> x = first;//设x为头节点
            for (int i = 0; i < index; i++)//从开始节点到插入节点索引之间的所有节点向后移动一位
                x = x.next;
            return x;
        } else {//如果插入节点位置在后半部分
            Node<E> x = last;//将x设为最后一个节点
            for (int i = size - 1; i > index; i--)//从最后节点到插入节点的索引位置之间的所有节点向前移动一位
                x = x.prev;
            return x;
        }
    }

右移一位相当于除以2，右移运算远高于除法运算。首先判断要获取的节点是在链表的前半段还是后半段，如果是前半段的话就从第一个节点开始遍历，一个节点一个节点的取，直到取到第index个。反之则从最后一个节点开始遍历。
这么做的原因是链表数据结构只能通过上一个节点的尾部获取到下一个节点的地址，或者通过下一节点的头部获取上一个节点的位置。无法像数组一样，直接通过下标获取数据。

6.remove(Object o)操作：

remove()函数，默认从链表的头部开始删除数据，remove(int index)函数也很容易理解，删除指定位置的元素，此处就不在分析了，比较好奇的是remove(Object o)这个函数，当链表中存在相同的两个元素，那么是如何删除的呢？

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

// 作用是删除x节点,返回对应的值
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;
       //头节点为空设置当前元素为第一个元素
        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;    // x节点的数据域、next、prev都设置为null，方便垃圾回收
        size--;
        modCount++;
        return element;
}

从代码可以看到，删除某一个元素是从头部开始查找，当找到时就删除对应节点，即便之后还有相同的元素也不会删除，删除成功则返回true，否则为false。
上段是unlink()方法的源码，我们来分析一下链表的删除操作。

先判断该节点是否存在上一个节点，即是否有前驱节点。无前驱节点则说明要删除的节点为链表的第一节点，那么只需要把该节点的下一个节点设置为链表的第一个节点。有前驱节点则需要把前驱节点的尾部引用指向该节点的下一个节点。
再判断该节点是否存在下一个节点，即是否有后继节点。无后继节点则说明该节点是链表的最后一个节点，那么只需要把该节点前驱节点设置成链表的最后一个节点即可。若有后继节点则需要把后继节点的头部引用指向该节点的上一个节点。
上述的操作核心就是在于将要删除的节点的前驱节点尾部指向该节点的后继节点，将要删除的节点的后继节点的头部指向该节点的前驱节点。这样便完成了链表的删除操作。

下图为删除操作的图例。

image.png

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

set函数是用来更新index节点的值，返回旧值，由于存在需要顺序遍历到第index位置，因此时间复杂度为n/2也即为n，源码如下：

public E set(int index, E element) {
     checkElementIndex(index);    // 检查index 位置的合法性
     Node<E> x = node(index);    // 遍历获取index位置的节点
     E oldVal = x.item;
     x.item = element;
     return oldVal;
}

listIterator(int index)操作

这是返回一个LinkedList的迭代器，通常我们不会直接调用此函数，一般是直接调用List的iterator()，它最终就是调用listIterator(int index)，只不过index为0而已，通过迭代器对链表进行遍历，相当于C语言里面的指针一样，指向某个元素顺序遍历，因此复杂度为n。此处就不在展示对应的源码。

我们都知道对List容器进行遍历通常有两种方式，一种为for循环直接遍历，一种通过迭代器方式进行遍历，那么到底哪种遍历方式比较好呢？

for循环方式遍历

int size = list.size()
for(int i=0; i<size;i++){                
    System.out.println(list.get(i)+"  ");         
}

迭代器方式遍历

Iterator iter = list.iterator();          
while(iter.hasNext()) {                       
    String value = (String)iter.next();       
    System.out.print(value + "  ");           
}

这两种方式到底哪种性能更优化，还需要看具体是对哪种List容器进行遍历，如果是ArrayList，由于get函数时间复杂度为1，因此采用for循环遍历要优于迭代器方式，如果是LinkedList，由于get函数（上面已经分析过）还需要对List进行遍历找到对应位置，因此采用迭代器方式遍历性能更好，总之，对于数组结构的线性表采用for循环方式遍历，对于链表结构的线性表采用迭代器方式进行遍历。

分析到此处，我们还需要注意一个点，大家知道for和for-each的区别吗？

List<Person> list = new ArrayList();
for (Person per:list) {
    System.out.println(per);
}
我们看看最后转化为class文件的代码如下：
 
List<Person> list = new ArrayList();
Iterator var5 = list.iterator();
 
while(var5.hasNext()) {
    Person per = (Person)var5.next();
    System.out.println(per);
}

总结：因此我们在遍历ArrayList的时候，最好不要使用for-each而是for，对于LinkedList的遍历，则建议使用for-each或者直接迭代器遍历。

push(E e)&pop()

push:向链表头部添加元素:addFirst(e)
pop:移除链表头元素
类似于栈的功能。

AbstractSequentialList简介

介绍一下AbstractSequentialList。毕竟，LinkedList是AbstractSequentialList的子类。

1）AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。

2）我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。 LinkedList是AbstractSequentialList的子类。

3）AbstractSequentialList实现了get(int index)、set(int indext, E element)、add(int index,E element)和remove（int index）这些函数。这些接口都是随机访问List的，LinkedList是双向链表，既然它继承了AbstractSequentialList，就相当于已经实现了这些接口。

4）若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的hasNext、next、hasPrevious、previous和index方法即可。

LinkedList其他介绍

1）LinkedList包含两个重要的成员: header和size

2）Header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量:previous,next,element。Previous是该节点的上一个节点，next是该节点的下一个节点，next是该节点的下一个节点，element是该节点所包含的值。

3）先对LinkedList的整体实现进行大致说明：
LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。
既然LinkedList是通过双向链表的，但是它也实现了List接口{也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。

4）LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？
实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。

(01) LinkedList 实际上是通过双向链表去实现的。
它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
(02) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
(03) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
(04) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
(05) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

LinkedList遍历方式

LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();

(02) 通过快速随机访问遍历LinkedList

int size = list.size();
for (int i=0; i<size; i++) {
    list.get(i);        
}

(03) 通过另外一种for循环来遍历LinkedList

for (Integer integ:list) 
    ;

(04) 通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
    ;

(05) 通过pollLast()来遍历LinkedList

while(list.pollLast() != null)
    ;

(06) 通过removeFirst()来遍历LinkedList

try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
}

(07) 通过removeLast()来遍历LinkedList

try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
}

总结

至此LinkedList的源码分析就结束了，LinkedList是基于双向链表实现，可以快速插入删除元素，由于保存有链表头部和尾部的应用（C/C++ 角度可以理解为指针），因此可以方便实现队列和栈的功能，同时在遍历链表时，建议使用迭代器来完成，而不是通过for+get(index)这种形式来遍历。

LinkedList实现原理

LinkedList介绍

注意:

字段属性

Node类型属性

LinkedList常用方法分析

LinkedList构造函数

1.addLast(E e)和add(E e)操作：

2.addFirst(E e)操作：

3.add(int index, E element)操作：

4.addAll(Collection<? extends E> c)操作：

5.get(int index)操作：

6.remove(Object o)操作：

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

listIterator(int index)操作

总结：因此我们在遍历ArrayList的时候，最好不要使用for-each而是for，对于LinkedList的遍历，则建议使用for-each或者直接迭代器遍历。

push(E e)&pop()

AbstractSequentialList简介

LinkedList其他介绍

LinkedList遍历方式

总结

猜你喜欢

热点阅读