LinkedList源码解析

1、首先需要清除LinkedList和之前所说的ArrayList的区别

LinkedeList和ArrayList都实现了List接口，但是它们的工作原理却不一样。它们之间最主要的区别在于ArrayList是可改变大小的数组，而LinkedList是双向链接串列(doubly LinkedList)。ArrayList更受欢迎，很多场景下ArrayList比LinkedList更为适用。这篇文章中我们将会看看LinkedeList和ArrayList的不同，而且我们试图来看看什么场景下更适宜使用LinkedList，而不用ArrayList。

LinkedList和ArrayList的区别

LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。如果你很熟悉Array和LinkedList，你很容易得出下面的结论：

1. 因为Array是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。

2. 相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

3. 类似于插入数据，删除数据时，LinkedList也优于ArrayList。

4. LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

什么场景下更适宜使用LinkedList，而不用ArrayList

我前面已经提到，很多场景下ArrayList更受欢迎，但是还有些情况下LinkedList更为合适。譬如：

1. 你的应用不会随机访问数据。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。

2. 你的应用更多的插入和删除元素，更少的读取数据。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。

以上就是关于ArrayList和LinkedList的差别。你需要一个不同步的基于索引的数据访问时，请尽量使用ArrayList。ArrayList很快，也很容易使用。但是要记得要给定一个合适的初始大小，尽可能的减少更改数组的大小。

转发于https://www.cnblogs.com/zhujiabin/p/10020383.html

2、LinkedList源码解析

1：首先我们先看看LinkedList的核心，也就是LinkedList中真正用来存储元素的数据结构。

Node 类是LinkedList中的私有内部类，LinkedList中就是通过Node来存储集合中的元素。
E ：节点的值。
Node next：当前节点的后一个节点的引用（可以理解为指向当前节点的后一个节点的指针）
Node prev:当前节点的前一个节点的引用（可以理解为指向当前节点的前一个节点的指针）

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

2：LinkedList集合中有哪些元素：
size：用来记录LinkedList的大小
Node first：用来表示LinkedList的头节点。
Node last：用来表示LinkedList的尾节点。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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;
 }

3.接下来看看构造器，LinkedList提供了两个构造器，ArrayList比它多提供了一个通过设置初始化容量来初始化类。LinkedList不提供该方法的原因：因为LinkedList底层是通过链表实现的，每当有新元素添加进来的时候，都是通过链接新的节点实现的，也就是说它的容量是随着元素的个数的变化而动态变化的。而ArrayList底层是通过数组来存储新添加的元素的，所以我们可以为ArrayList设置初始容量（实际设置的数组的大小）。

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

4.这里有一个非常重要的方法addAll

// 首先调用一下空的构造器。
//然后调用addAll(c)方法。
  public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
//通过调用addAll(int index, Collection<? extends E> c) 完成集合的添加。
  public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
//重点来了。（还是建议大家自己手动写一次源码实现。） 
//几乎所有的涉及到在指定位置添加或者删除或修改操作都需要判断传进来的参数是否合法。
// checkPositionIndex(index)方法就起这个作用。该方法后面会介绍。  
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
//先把集合转化为数组，然后为该数组添加一个新的引用（Objext[] a）。
        Object[] a = c.toArray();
//新建一个变量存储数组的长度。
        int numNew = a.length;
//如果待添加的集合为空，直接返回，无需进行后面的步骤。后面都是用来把集合中的元素添加到
//LinkedList中。
        if (numNew == 0)
            return false;
//这里定义了两个节点：（读这里的程序的时候，强烈建议自己画一个图，辅助你理解这个过程）。
//Node<E> succ：指代待添加节点的位置。
//Node<E> pred：指代待添加节点的前一个节点。
//下面的代码是依据新添加的元素的位置分为两个分支：
//①新添加的元素的位置位于LinkedList最后一个元素的后面。
//新添加的元素的位置位于LinkedList中。
//如果index==size;说明此时需要添加LinkedList中的集合中的每一个元素都是在LinkedList
//最后面。所以把succ设置为空，pred指向尾节点。
//否则的话succ指向插入待插入位置的节点。这里用到了node（int index）方法，这个方法
//后面会详细分析，这里只需要知道该方法返回对应索引位置上的Node（节点）。pred指向succ节点的前一个节点。
//上面分析的这几步如果看不懂的话，可以自己画个图，清晰明了^_^。
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
//接着遍历数组中的每个元素。在每次遍历的时候，都新建一个节点，该节点的值存储数组a中遍历
//的值，该节点的prev用来存储pred节点，next设置为空。接着判断一下该节点的前一个节点是否为
//空，如果为空的话，则把当前节点设置为头节点。否则的话就把当前节点的前一个节点的next值
//设置为当前节点。最后把pred指向当前节点，以便后续新节点的添加。
        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;
        }
//这里仍然和上面一样，分两种情况对待：
//①当succ==null（也就是新添加的节点位于LinkedList集合的最后一个元素的后面），
//通过遍历上面的a的所有元素，此时pred指向的是LinkedList中的最后一个元素，所以把
//last指向pred指向的节点。
//当不为空的时候，表明在LinkedList集合中添加的元素，需要把pred的next指向succ上，
//succ的prev指向pred。
//最后把集合的大小设置为新的大小。
//modCount（修改的次数）自增。
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    } 

5.关于其他的删除，集合最后添加等方法，可参考博文，这里不具体说明了。

原文链接：https://blog.csdn.net/m0_37884977/article/details/80467658

6.LinkedList和ArrayList的大致区别：

1、ArrayList继承于 AbstractList， LinkedList继承于 AbstractSequentialList；

2、ArrayList基于数组， LinkedList基于双向链表，对于随机访问， ArrayList比较占优势，LinkedList插入、删除元素比较快，如果只要调整指针的指向那么时间复杂度是O(1),但是如果针对特定位置需要遍历时，时间复杂度是O(n)，也就是LinkedList在随机访问元素的话比较慢；

3、LinkedList没有实现自己的 Iterator，但是有 ListIterator和 DescendingIterator；

4、LinkedList需要更多的内存，因为 ArrayList的每个索引的位置是实际的数据，而 LinkedList中的每个节点中存储的是实际的数据和前后节点的位置；

5、ArrayList 和 LinkedList都是非同步的集合。

6、和ArrayList一样，LinkedList也是非线程安全的，只有在单线程下才可以使用。为了防止非同步访问，可以采用如下方式创建LinkedList：List list= Collections.synchronizedList(new LinkedList());

7、LinkedList基于双向链表实现，元素都可以为null。