LinkedList source code interpretation
Inheritance structure of LinkedList
Properties of LinkedList
LinkedList constructor
The core method of LinkedList
FailFast mechanism
Inheritance structure of LinkedList
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Properties of LinkedList
/** * LinkedList Length of bidirectional linked list */ transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null)  * (first.prev == null && first.item != null) * Pointer to the first node of the twoway linked list. The initial value is null */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null)  * (last.next == null && last.item != null) * Pointer to the tail node of the bidirectional linked list. The initial value is null */ transient Node<E> last; /** * A private static internal class, a very important data structure, represents a node of a twoway linked list */ private static class Node<E> { E item; //Value of node Node<E> next; //Pointer to the back node Node<E> prev; //Pointer to the previous node Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } /** * Records the number of nodes added and deleted from the bidirectional linked list. This attribute is inherited from the parent class AbstractList of the direct parent class AbstractSequentialList. It is used to protect data security when reading and writing the bidirectional linked list at the same time in a concurrent environment */ protected transient int modCount = 0;
LinkedList constructor

Parameterless constructor
public LinkedList() { //Nothing }

Parametric constructor
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
Another overloaded addAll method addAll method was called
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }
The overloaded addAll method is defined as follows. Here we only look at the execution route
public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); // Check whether the index position is legal and 0 is legal Object[] a = c.toArray(); // Set to array int numNew = a.length; // Get the length of the converted array, and then increase the length of the linked list if (numNew == 0) return false; Node<E> pred, succ; // pred: points to the front node of the node to be inserted; succ: points to the back node of the node to be inserted if (index == size) { //Go here and add in the tail. succ is null and pred is the tail node pointed to by last succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { // Traverse, and add the elements in the transformed array to the bidirectional linked list in turn @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); //Assembly node, the front pointer points to the tail node, and the rear pointer is null if (pred == null) // The first element goes here as the first node first = newNode; else // The remaining elements go here, and the rear pointer of the tail node points to the new node pred.next = newNode; pred = newNode; // New node as tail node } if (succ == null) { // Here, the tail pointer points to the tail node last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; // Update the length of bidirectional linked list modCount++; return true; }
The core method of LinkedList

Addfirst (E) method
public void addFirst(E e) { linkFirst(e); }
Call the private linkFirst method. The linkFirst (E) method is defined as follows
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
The head insertion method of twoway linked list.
This method is used to add elements to the head of the twoway linked list. First, define a new node. The front pointer of the new node points to null, and the rear pointer points to the original first node. Take the new node as the first node, and then judge whether the original first node is null. If yes, it means that there are no nodes in the original linked list, and the new node is also used as the tail node, Otherwise, make the front pointer of the original first node point to the new node, and add 1 to the length of the twoway linked list.

Addlast (E) method
public void addLast(E e) { linkLast(e); }
Call the private linkLast method. The linkLast (E) method is defined as follows
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++; }
Tail interpolation of twoway linked list.
This method is used to add an element at the end of the twoway linked list. First, define a new node. The front pointer of the new node points to the original tail node, and the rear pointer points to null. Take the new node as the tail node, and then judge whether the original tail node is null. If yes, it means that there are no nodes in the original linked list, and the new node is also taken as the first node, Otherwise, make the back pointer of the original tail node point to the new node, and add 1 to the length of the twoway linked list.

removeFirst() method
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
This method is used to delete the first node of the twoway linked list.
First judge whether the first node exists. If it does not exist, throw a NoSuchElementException exception. Otherwise, call the unlinkFirst method to delete the first node.
The unlikfirst method is defined as follows
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size; modCount++; return element; }
First find the next node of the first node, make the pointer of the first node point to null, take the next node as the new first node, and then judge whether the next node exists. If it exists, cancel the pointer before the next node, and the original first node will be recycled by GC if it loses application. If it does not exist, it means that the original linked list has only the first node, and make the last pointer point to null, The original first node loses the references of first and last at the same time, triggers GC and is recycled. The deletion is successful, and the length of the twoway linked list is reduced by 1.

removeLast() method
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
This method is used to delete the tail node of the twoway linked list.
First judge whether the tail node exists. If it does not exist, throw a NoSuchElementException exception. Otherwise, call the unlinkLast method to delete the tail node.
The unliklast method is defined as follows
private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size; modCount++; return element; }
First find the prev of the previous node of the original tail node and cancel the pointing of the front pointer of the original tail node. Prev is used as a new tail node, and then judge whether prev is null. If so, it indicates that there is only one node in the original linked list, and make the first pointer null. In this way, the original tail node will lose the references of first and last at the same time, trigger GC and be recycled; If the pointer to the original node is not recovered after the reference to the prev node is lost.

getFirst method
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
This method is used to obtain the value of the first node.
If the first node does not exist, a NoSuchElementException exception is thrown. Otherwise, the value of the first node is returned.

getLast method
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
This method is used to obtain the value of the tail node.
If the tail node does not exist, a NoSuchElementException exception will be thrown. Otherwise, the value of the tail node will be returned.

Add (E) method
Call the LinkeLast method to add elements to the tail
public boolean add(E e) { linkLast(e); return true; }

remove (Object o) method
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
Traverse the linked list from beginning to end to find the specified Object object. If it is not found, return false. If it is found, call the unlink function to delete the corresponding node, and then return true.
The unlink function is defined as follows
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; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size; modCount++; return element; }
Find the front and back nodes to delete.
If the front node does not exist, the back node is the first node. Otherwise, the back pointer of the front node points to the back node, and the front pointer of the node to be deleted is set to null.
If the back node does not exist, the front node is the tail node. Otherwise, the front pointer of the back node points to the front node, and the back pointer of the node to be deleted is set to null.

remove() method
public E remove() { return removeFirst(); }
Very simple, call the removeFirst method to delete the first element of the twoway linked list.

remove (int index) method
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
The checkElementIndex method is used to verify whether the index is legal. It is defined as follows
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
The isElementIndex method is defined as follows
private boolean isElementIndex(int index) { return index >= 0 && index < size; }
If the index is illegal, an IndexOutOfBoundsException exception is thrown. Otherwise, the unlink method is called to delete the specified node, and the node method is called. The node method is defined as follows
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; } }
If the index is to the right, look from back to front. After finding the node, return to the node.
If the index is left, look from front to back. After finding the node, return to the node.

add (int index, E element)
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
checkPositionIndex checks whether the subscript is legal. The checkPositionIndex method is defined as follows
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
If the index is illegal, an IndexOutOfBoundsException exception will be thrown.
If the index is size, the linkLast method is called to insert the element into the tail of the twoway linked list.
Otherwise, call the linkBefore method to insert the element into the specified position. The linkBefore method is defined as follows
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++; }
This function finds the node and its front node at the original index position. These two nodes are the front and rear nodes of the node to be inserted, and then correctly handle the pointing of the front and rear pointers of each node.

get (int index) method
public E get(int index) { checkElementIndex(index); return node(index).item; }
Very simple, as defined above.

set (int index, E e)
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
Very simple, as defined above.

indexOf (Object o) method
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return 1; }
Very simple, as defined above.

lastIndexOf (Object o) function
public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index; if (o.equals(x.item)) return index; } } return 1; }
Very simple, as defined above.

toArray() method
public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
Create an Object array of size, copy the data of the twoway linked list into the Object array in turn, and return the Object array.

clear() method
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: //  helps a generational GC if the discarded nodes inhabit // more than one generation //  is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
Set the back pointer, value and front pointer of each node to null, and set the points of first and last to null. Finally, set the length of the twoway linked list to 0.
FailFast mechanism
FailFast mechanism, i.e. fast failure mechanism.
Through the core method of LinkedList above, we can see that modCount will be automatically increased in adding and deleting nodes, and modCount represents the number of modifications.
FailFast mechanism is to protect the security and correctness of data in LinkedList when reading and writing LinkedList at the same time.
The specific implementation is as follows: the next iteration function is defined as follows
public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; }
The checkforconfirmation function is defined as follows
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
modCount is the current modification times and expectedModCount is the expected modification times. If the two values are inconsistent, it means that the linked list has been written at the same time in the process of reading the linked list. This is not allowed. At this time, the ConcurrentModificationException exception exception will be thrown. This process can be analogous to the shared lock of a database.
FailFast mechanism test
Read thread
package cn.edu.hstc.LinkedList; import java.util.Iterator; import java.util.List; /** * ReadObject */ public class ReadThread extends Thread { private List list; public ReadThread(List list) { this.list = list; } @Override public void run() { while (true){ for (Iterator iterator = list.iterator(); iterator.hasNext();){ System.out.println("ReadThread: " + iterator.next()); try { Thread.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } } } } }
Write thread
package cn.edu.hstc.LinkedList; import java.util.List; /** * wirteThread */ public class WirteThread extends Thread { private List list; public WirteThread(List list) { this.list = list; } @Override public void run() { for (int i = 0; i < 100; i++){ list.add(i); try { Thread.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } } } }
Test class
package cn.edu.hstc.LinkedList; import cn.edu.hstc.Array.WiretThread; import java.util.LinkedList; import java.util.List; /** * test FailFast */ public class TestFailFast { public static void main(String[] args) { List<Object> list = new LinkedList<>(); new ReadThread(list).start(); new WiretThread(list).start(); } }
test result
loop execute : 0 loop execute : 1 loop execute : 2 Exception in thread "Thread0" java.util.ConcurrentModificationException at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966) at java.util.LinkedList$ListItr.next(LinkedList.java:888) at cn.edu.hstc.LinkedList.ReadThread.run(ReadThread.java:21) loop execute : 3 loop execute : 4 loop execute : 5 loop execute : 6 loop execute : 7 loop execute : 8 loop execute : 9