LinkedList source code analysis
1. Introduction
- Through the inheritance system, we can see that LinkedList not only implements the List interface, but also implements the Queue and Deque interfaces, so it can be used as a List, a double ended Queue, and of course, a stack.
- It can be seen from the inheritance system that LinkedList implements Cloneable and Serializable interfaces, indicating that it can be cloned or serialized! Similarly, when LinkedList is cloned, it is the same as ArrayList. Both are shallow copies.
2. Main attributes
// Number of elements transient int size = 0; // List head node transient Node<E> first; // End of list node transient Node<E> last;
The attribute is very simple. It defines the number of elements, size and the beginning and end nodes of the linked list. transient guarantees that it will not be serialized.
3. Main internal categories
Typical double linked list structure:
private static class Node<E> {
E item; // Elements stored by the current node
Node<E> next; // precursor
Node<E> prev; // Rear drive
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
4. Main construction methods
//Nonparametric structure
public LinkedList() {
}
//Parametric structure
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
5. Add elements
As a double ended queue, there are two main ways to add elements: one is to add elements at the end of the queue, and the other is to add elements at the head of the queue. These two forms are mainly realized in the LinkedList through the following two methods.
Queue header add
public void addFirst(E e) {
linkFirst(e);
}
// Add element to queue header
private void linkFirst(E e) {
// First node
final Node<E> f = first;
// Create a new node
final Node<E> newNode = new Node<>(null, e, f);
// Make the new node the first node
first = newNode;
// Determine whether it is the first element added
// If so, set last as the new node
//Otherwise, set the prev pointer of the original first node to the new node
if (f == null)
last = newNode;
else
f.prev = newNode;
// Number of elements plus one
size++;
// The number of modifications plus one indicates that this is a set that supports fail fast
modCount++;
}
Add at the end of queue
public void addLast(E e) {
linkLast(e);
}
// Add element from end of queue
void linkLast(E e) {
// Queue tail node
final Node<E> l = last;
// Create a new node. The prev of the new node is the tail node
final Node<E> newNode = new Node<>(l, e, null);
// Make the new node the new tail node
last = newNode;
// Determine whether it is the first element added
// If so, set first as the new node
// Otherwise, set the next pointer of the original node to the new node
if (l == null)
first = newNode;
else
l.next = newNode;
//Number of elements plus one
size++;
// Number of modifications plus one
modCount++;
}
As an unbounded queue, adding elements always succeeds:
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
As a List, you need to support adding elements in the middle, mainly through the following method.
Add at specified location
//Adds an element at the specified index location
public void add(int index, E element) {
//Check for out of bounds
checkPositionIndex(index);
//If index is a position after the end of the queue node
//Add the new node directly after the tail node
//Otherwise, the linkBefore() method is called to add nodes in the middle
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//Find the node corresponding to the index location
Node<E> node(int index) {
//Because it is a double linked list, it determines whether to traverse from the front or from the back according to whether the index is in the first half or the second half
//In this way, index can traverse half the elements less
if (index < (size >> 1)) {
//If it's in the first half
//Previous traversal
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//In the second half if
//Just traverse from the back
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// Add element before node succ
void linkBefore(E e, Node<E> succ) {
// Find the front node of the node to be added, that is, the front node of succ
final Node<E> pred = succ.prev;
// Create a new node between its predecessor and successor
final Node<E> newNode = new Node<>(pred, e, succ);
// Modify the leading pointer of the subsequent node to point to the new node
succ.prev = newNode;
// Judge whether the front node is empty
//If it is empty, it indicates that it is the first added element. Modify the first pointer
//Copy and modify the nxet of the front node as a new node
if (pred == null)
first = newNode;
else
pred.next = newNode;
//Number of elements + 1
size++;
//Modification times + 1
modCount++;
}
The method of adding elements in the middle of LinkedList is also very simple. A typical double linked list adds elements in the middle.
summary
The three ways to add elements are roughly as shown in the following figure:
- Adding elements at the beginning and end of the queue is very efficient, and the time complexity is O(1).
- Adding elements in the middle is inefficient. First, find the node at the insertion position, and then modify the pointers of the front and rear nodes. The time complexity is O(n).
6. Delete element
As a double ended queue, there are two ways to delete elements, one is to delete elements at the beginning of the queue, and the other is to delete elements at the end of the queue.
As a List, it also supports intermediate deletion of elements, so there are three methods to delete elements, as follows:
Delete header node
//An exception is thrown if no element is remove d
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//poll returns null if there is no element
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//Delete first node
private E unlinkFirst(Node<E> f) {
//Element value of the first node
final E element = f.item;
//next pointer of the first node
final Node<E> next = f.next;
//Set the value of the first node to null to assist the GC
f.item = null;
f.next = null; // help GC
//Take the next of the first node as the new first node
first = next;
//If only one element is deleted, set last to null
//Otherwise, set the leading pointer of next to null
if (next == null)
last = null;
else
next.prev = null;
//Number of elements minus one
size--;
//Number of modifications plus one
modCount++;
//Returns the deleted element
return element;
}
Delete tail node
//An exception is thrown if no element is remove d
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//poll returns null if there is no element
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//Delete tail node
private E unlinkLast(Node<E> l) {
//Element value of tail node
final E element = l.item;
//Leading pointer of tail node
final Node<E> prev = l.prev;
//Clear the contents of the tail node to assist the GC
l.item = null;
l.prev = null; // help GC
//Let the front node be called the new tail node
last = prev;
//If there is only one element, delete and set first to null
//Otherwise, set the next of the preceding node to null
if (prev == null)
first = null;
else
prev.next = null;
//Number of elements minus one
size--;
//Number of modifications plus one
modCount++;
//Returns the deleted element
return element;
}
Delete intermediate specified node
//Delete intermediate node
public E remove(int index) {
//Check for out of bounds
checkElementIndex(index);
//Delete the node at the specified index location
return unlink(node(index));
}
//Delete specified node
E unlink(Node<E> x) {
// Element value of node x
final E element = x.item;
// Front node of x
final Node<E> next = x.next;
// Post node of x
final Node<E> prev = x.prev;
//If the front node is empty
//The description is the first node. Let first point to the post node of x
//Otherwise, modify the post node whose next of the front node is x
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//If the post node is empty
//The description is the tail node. Let last point to the front node of x
//Otherwise, modify the front node whose prev is x
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//Clear the element value of x to assist GC
x.item = null;
//Number of elements minus one
size--;
//Number of modifications plus one
modCount++;
//Returns the deleted element
return element;
}
summary
The three methods of deleting elements are typical double linked list methods. The general process is shown in the following figure:
- It is efficient to delete elements at the beginning and end of the queue, and the time complexity is O(1).
- It is inefficient to delete elements in the middle. First, find the node at the deletion position, and then modify the front and rear pointers. The time complexity is O(n).
7. Removal method
Clear all elements
public void clear() {
//In order to make GC recycle the placed elements faster, you need to empty the reference relationship between node s.
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;
//Set the number of elements to 0
size = 0;
//Number of modifications plus one
modCount++;
}
8. As a stack
LinkedList is a double ended queue, which can be used as a stack.
//Element stack
public void push(E e) {
// The head element of the queue is the top element of the stack
addFirst(e);
}
//Delete the stack top element and return
public E pop() {
// The head element of the queue is the top element of the stack
return removeFirst();
}
The feature of the stack is LIFO, so it is easy to use as a stack. Adding and deleting elements only operate on the first node of the queue.
9. Summary
- LinkedList is a List implemented as a double linked List
- LinkedList is also a double ended queue, which has the characteristics of queue, double ended queue and stack
- LinkedList is very efficient in adding and deleting elements at the beginning and end of the queue, and the time complexity is O(1)
- LinkedList is inefficient to add and delete elements in the middle, and the time complexity is O(n)
- LinkedList does not support random access, so it is inefficient to access non queue elements
- LinkedList is functionally equal to ArrayList + ArrayDeque
