LinkedList 源码及数据存储结构 ​

存储结构 ​

LinkedList 它是用双向列表的一个形式进行数据存储的，在 LinkedList 里面它最基本的单位叫做 Node，就是节点每个 Node 他本身是一个 class，它是这个 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;
        }
    }

它这里面它包含的节点的元素，这个 next 跟 prove，是分别指向下一个节点跟上一个节点的一个 Node 对象，通过这三个可以形成一个双向列表，而且 LinkedList 它是实现了 Deque 接口，可以利用 addFirst 和 addLast 来记录列表的起始节点。

常用方法 ​

1、add() ​

add() 方法将节点添加到列表末尾，它最终调用的是这个 linkLast() 这个方法

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

2、get() ​

get 方法根据索引获取元素，先判断索引有效性，get 方法会根据索引位置选择从头或尾开始遍历查找

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

它会先通过 CheckElementIndex 方法来判断它是否大于等于元素的个数，就是要检查的一个方法，它最终是调的这个 Node 这个方法。 它会首先来判断所有 Index 的它的位置，它到底是靠近尾节点，还是靠近这个头节点，最终它会决定是往前辨率还是往后辨率。

3、Remove() ​

Remove方法删除指定索引的节点，调用 unlink 方法来调整这个 Node 节点前后的一个节点的指向

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }