[Java] Java LinkedList的实现原理图文详解

doubly-linked list implementation of the list and deque interfaces. implements all optional list operations, and permits all elements (including null).all of the operations perform as could be expected for a doubly-linked list. operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.note that this implementation is not synchronized. if multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (a structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) this is typically accomplished by synchronizing on some object that naturally encapsulates the list.

//链表的节点个数
transient int size = 0;
//指向头节点的指针
transient node<e> first;
//指向尾节点的指针
transient node<e> last;

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

private void linkfirst(e e) {
 final node<e> f = first;
 //当前节点的前驱指向 null，后继指针原来的头节点
 final node<e> newnode = new node<>(null, e, f);
 //头指针指向新的头节点
 first = newnode;
 //如果原来有头节点，则更新原来节点的前驱指针，否则更新尾指针
 if (f == null)
 last = newnode;
 else
 f.prev = newnode;
 size++;
 modcount++;
}

void linklast(e e) {
 final node<e> l = last;
 //当前节点的前驱指向尾节点，后继指向 null
 final node<e> newnode = new node<>(l, e, null);
 //尾指针指向新的尾节点
 last = newnode;
 //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针
 if (l == null)
 first = newnode;
 else
 l.next = newnode;
 size++;
 modcount++;
}

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