1. General
LinkedList implements both the List interface and the Deque interface, that is, it can be regarded as not only a sequential container, but also a Queue and a Stack. In this way, LinkedList is an all-round champion. When you need to use Stack or Queue, you can consider using LinkedList. On the one hand, Java officials have declared that Stack class is not recommended. What's more, there is no class called Queue in Java (it's an interface name). With regard to stacks or queues, the current preferred is ArrayDeque, which has better performance than LinkedList (when used as a Stack or Queue).
2. Underlying implementation
- The underlying layer of LinkedList is realized through a two-way linked list, and each Node of the two-way linked list is represented by an internal class Node. LinkedList points to the first and last elements of the linked list through the first and last references, respectively.
//Node inner class
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;
}
}
3. Introduction to common methods
This section will focus on the maintenance process of bidirectional linked List when inserting and deleting elements, that is, functions directly related to the List interface.
3.1 add()
The add() method has two versions. One is add (E). This method inserts elements at the end of the LinkedList because last points to the end of the linked list. The cost of inserting elements at the end is a constant time. You only need to modify a few related references; The other is add(int index, E element). This method inserts elements in the specified table. First find the specific location through linear search, and then modify the relevant references to complete the insertion operation.
Combined with the above figure, we can see that the logic of add (E) is very simple.
//add(E e)
public boolean add(E e) {
final Node<E> l = last; // Keep the original tail node first
final Node<E> newNode = new Node<>(l, e, null); // Declare and initialize the node to be inserted
last = newNode; // Update tail node
if (l == null)
first = newNode; //The original linked list is empty. This is the first element inserted
else
l.next = newNode; // The original tail node becomes the penultimate node, and its next pointer is updated
size++;
return true;
}
The logic of add(int index, E element) is slightly complex and can be divided into two parts. 1. First find the location to insert according to the index; 2. Modify the reference and complete the insertion operation.
//add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);//index >= 0 && index <= size;
if (index == size)//The insertion position is the end, including when the list is empty
add(element);
else {
Node<E> succ = node(index);//1. First find the position to insert according to the index
//2. Modify the reference and complete the insertion operation.
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//The insertion position is 0
first = newNode;
else
pred.next = newNode;
size++;
}
}
The node(int index) function in the above code has a little trick, because the linked list is bidirectional. You can look back from the beginning or forward from the end. The specific direction depends on the condition index < (size > > 1), that is, whether the index is close to the front end or the back end.
3.2 remove()
The remove() method also has two versions. One is to delete the first element equal to the specified element, remove(Object o), and the other is to delete the element at the specified subscript, remove(int index).
Both deletion operations are: 1. Find the reference of the element to be deleted first, 2. Modify the relevant reference to complete the deletion operation. When looking for the deleted element reference, remove(Object o) calls the equals method of the element, while remove(int index) uses subscript counting. Both methods have linear time complexity. In step 2, both remove() methods are completed through the unlink (node < E > x) method. Here, we need to consider the boundary when the deleted element is the first or last.
//Unlink (Node < E > x), delete a Node
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {//The first element is deleted
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {//The last element is deleted
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;//let GC work
size--;
return element;
}
3.3 get()
get(int index) gets the reference of the element at the specified subscript by calling the node(int index) method mentioned above.
public E get(int index) {
checkElementIndex(index);//index >= 0 && index < size;
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // index is in the first half, looking from the pointer
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index is in the second half, starting with the tail pointer
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3.4 set()
The set(int index, E element) method modifies the element at the specified subscript to the specified value. It is also to find the reference of the corresponding element in the following table through node(int index), and then modify the value of item in Node.
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;//Replace new value
return oldVal;
}
4. Traversal method
4.1 Iterator method traversal
for(Iterator it = list.iterator();it.hasNext();){
System.out.println(it.next());
}
The deletion method of list cannot be used during traversal, otherwise concurrent modification exceptions will be reported, but the deletion method of iterator can be used
4.2 for loop traversal
for(int i = 0;i < list.size(); i ++){
System.out.println(list.get(i));
}
list can be modified during traversal
4.3 enhanced for loop traversal
for(String tmp:list){
System.out.println(tmp);
}
The underlying implementation is based on the iterator. The deletion method of list cannot be used during traversal, otherwise concurrent modification exceptions will be reported, but the deletion method of iterator can be used
4.4 traversal with pollFirst()
while(list.pollFirst() != null) {
;
}
4.5 traversal with pollLast()
while(list.pollLast() != null) {
;
}
4.6 traversal with removeFirst()
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}
4.7 traversal with removeLast()
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}