LinkedList源码分析_JDK1.8.0_191

LinkedList JDK1.8.0_191


 

基于双向链表实现,实现了Deque接口,可以用于队列操作

不是线程安全,可以使用Collections.synchronizedList包裹一个线程安全的ListedList

支持fail-fast机制


ListedList的变量

transient Node<E> first;

transient Node<E> last;


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的方法

1.linkLast():add的核心操作

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

将元素加到链表尾。

linkBefore():插入到指定位置

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

链表的常规插入插入操作

2.node():获取index位置的元素

Node<E> node(int index) {
    // assert isElementIndex(index);
//如果index在前半段,则从头开始查找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x;
//如果index在后半段,则从尾开始查找 } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

3.unlink():删除的核心方法

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.it
    final Node<E> next = x
    final Node<E> prev = x
    if (prev == null) {
//如果删除的是头节点,则将first指针指向下一个节点 first = next; } else {
//如果删除的不是头节点,则将前一节点指向后一节点,x的prev指针置为null prev.next = next; x.prev = null; } if (next == null) {
//如果删除的是尾节点,则将last指针指向前一节点 last = prev; } else {
//不是 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }

 

上一篇:JAVA源码学习-LinkedList


下一篇:基于Comparable接口实现的二叉树操作