关于java:一文搞懂LinkedList

01 原理

LinkedList 底层采纳双向链表实现。与 ArrayList 不同，链表 不须要扩容，除此之外还会有以下特点。

02 特点

1. 非间断的内存，因而 不反对随机拜访，只能通过节点持有的指针，顺次向后（向前）查找就安顿，查找的复杂度高。

2. 插入操作性能好。只须要插入地位的前后节点的援用指向该节点即可。

  3.  删除性能好，与插入相似，将删除节点前后节点的援用相互指向即可。

03 源码

最初从源码里具体分析一下，LinkedList 中的 增加(add)，查找（get），删除(remove)，插入（add）。

增加(add):

 public boolean add(E e) {linkLast(e); // 增加节点到开端
        return true;
    }

 void linkLast(E e) {
        final Node<E> l = last; // 尾节点
        final Node<E> newNode = new Node<>(l, e, null); // 创立 e 的节点，其中 prev 指针指向尾部节点，next 为空
        last = newNode; // 将尾节点批改为增加的节点
        if (l == null)
            first = newNode; // 没有尾节点，则该节点也是头节点
        else
            l.next = newNode; // 旧的尾节点 next 指针指向新增加的节点
        size++; // 数据大小 + 1
        modCount++;
    }

查找（get）:

public E get(int index) {checkElementIndex(index); 
        return node(index).item; // 查找
    }
 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;
        }
    }

插入（add）：

public void add(int index, E element) {checkPositionIndex(index);

        if (index == size)
            linkLast(element);  // 增加节点到链表开端，与增加逻辑统一
        else
            linkBefore(element, node(index)); // 查找下标指向的节点，插入新节点
    }

void linkBefore(E e, Node<E> succ) { // e: 插入节点，succ: 插入地位上的节点
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ); // 创立插入 e 的节点，其中 prev 指针指向 succ 的前继节    
                                                                                 //  点，next 指向 succ 节点
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode; // succ 前继节点的 next 指针指向插入的节点
        size++;
        modCount++;
    }

删除(remove)：

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

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; // 前继节点的 next 指针指向后继节点
            x.prev = null; // 删除节点的 pre 指针置为 null
        }

        if (next == null) { // 插入地位为尾部
            last = prev;
        } else {
            next.prev = prev; // 后继节点的 prev 指针指向前继节点
            x.next = null; // 删除节点的 next 指针置为 null
        }

        x.item = null; // 删除节点的指置为 null, 让 GC 能够回收
        size--;
        modCount++;
        return element;
    }