LinkedList的实现原理(阅读书籍＜Java编程的逻辑＞)

LinkedList特点分析：
用法上，LinkedList是一个List,但也实现了Deque接口，可以作为队列、栈和双端队列使用，实现原理上，LinkedList内部是一个双向链表。并维护了长度、头节点、和尾结点，如图所示可以看出
因此这决定了它有如下特点：
1）按需分配空间，不需要预先分配很多空间。
2）不可以随机访问，按照索引位置访问效率比较低，所以必须从头或尾顺着链接找，效率为O(N/2).
3) 不管列表是否已经排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)
4) 在两端添加、删除元素的效率很高，为O(1)。
5）在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(l)。

1.内部组成
LinkedList内部实现是双向链表，每个元素在内存都是单独存放的，元素之间通过链接连接在一起，类似于小朋友之间手拉手一样。
为了表示链接关系，需要一个节点的概念。节点包括实际的元素，但同时有两个链接，分别指向前一个节点和后一个节点。节点是一个内部类，具体定义为：

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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

LinkedList的内部组成就是如下三个实例变量：

transient int size = 0;  // 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;  // 指向尾结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.add方法

public boolean add(E e) {
        linkLast(e);
        return true;
    }
1
2
3
4

主要是调用了LinkLast(e)方法，它的代码为：

void linkLast(E e) {
        final Node<E> l = last;  // 1.创建一个新的节点newNode。l和last指向原来的尾结点
        final Node<E> newNode = new Node<>(l, e, null); // 2.如果链表为空，则为null.
        last = newNode; // 3.修改尾结点last,指向新的最后节点newNode。
        if (l == null) // 4.修改前节点的后向链接，如果原来链表为空
            first = newNode; // 则让头节点指向新节点，
        else
            l.next = newNode;  // 否则让前一个节点的next指向新节点。
        size++; // 5.增加链表大小
        modCount++;  //6.记录修改次数，便于迭代中间检测结构型变化
    }
1
2
3
4
5
6
7
8
9
10
11

我们可以通过图示来进行介绍：

public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<String>();
        linkedList.add("简单爱");
        linkedList.add("轨迹");
    }
1
2
3
4
5

执行完第一行代码后LinkedList内部结构如图：

添加第一个元素后LinkedList对象内部结构：(这里画图出现失误，size的大小改为1)

添加两个元素后对象内部结构：

以上图片所示可以看出LinkedList是按需分配的，不需要预先分配多余的内存，添加元素只需分配新元素的空间，然后调节几个链接即可。