Class structure
The underlying LinkedList uses a two-way LinkedList structure to store data, allowing duplicate data and null values. The length is unlimited:
Each Node is represented by the inner class Node:
private static class Node<E> {
E item; // Store data
Node<E> next; // Subsequent nodes
Node<E> prev; // Predecessor node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeNode nodes contain item (storing data), next (succeeding nodes), and prev (succeeding nodes). Arrays must have contiguous memory addresses, whereas linked lists do not. Nodes can be distributed among memory addresses, and their relationships are maintained by prev and Next.
LinkedList class diagram:
As you can see, the LinkedList class does not implement the RandomAccess interface, but implements the Deque interface in addition, so it contains queue methods.
LinkedList contains the following member variables:
// Number of elements, default is 0
transient int size = 0;
/ / the first node, the first node must satisfy (first = = null && last = = null) | | (first. Prev = = null && first. The item! = null)
transient Node<E> first;
/ / the last node, the last node must satisfy (first = = null && last = = null) | | (last. Next = = null &&. Last item! = null)
transient Node<E> last;
Copy the codeMethod resolution
The constructor
LinkedList () :
public LinkedList(a) {}
Copy the codeThe null parameter constructor, which defaults to size 0, creates a Node Node each time a new element is added.
LinkedList(Collection
c) :
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// Loop to create node, set prev, next point to
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Copy the codeThis constructor is used to create a LinkedList and add the specified collection elements to it.
add(int index, E element)
Add (int index, E element) specifies the index to insert the element:
public void add(int index, E element) {
// Check subscript validity
checkPositionIndex(index);
if (index == size)
// If the insertion subscript is equal to size, it indicates that the insertion is in the tail
linkLast(element);
else
// If not, insert before the specified subscript node
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
void linkLast(E e) {
// Get the last node
final Node<E> l = last;
// Create a new node, prev is the last node of the original list, next is null
final Node<E> newNode = new Node<>(l, e, null);
// Update last to the new node
last = newNode;
if (l == null)
// If the last node of the original list is null, the original list has no nodes, and the new node is assigned to first
first = newNode;
else
// Otherwise update next of the last node of the original list as the new node
l.next = newNode;
/ / the size increases
size++;
// module increment, used for fast failure
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// succ obtains the prev node of the index node
final Node<E> pred = succ.prev;
// Create a new node. Prev specifies the prev node of the index node of the original list. Next specifies the index node of the original list
final Node<E> newNode = new Node<>(pred, e, succ);
// Update the prev of the index node to the new node
succ.prev = newNode;
if (pred == null)
// If the prev of the index node is null, the original list has no nodes. Assign the new node to first
first = newNode;
else
// Otherwise update the next node of the prev of the node at index position as the new node
pred.next = newNode;
/ / the size increases
size++;
// module increment, used for fast failure
modCount++;
}
// Use dichotomy to traverse each Node until the index Node is found
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;
returnx; }}Copy the codeAll it does is set the node’s prev and next relationship. It can be seen that in addition to head and tail inserts, inserting new nodes at other positions in the linked list involves node traversal operation. Therefore, we often say that the linked list inserts fast, which refers to the fast reference process of nodes before and after inserting nodes.
get(int index)
Get (int index) gets the specified subscript element:
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// Use dichotomy to traverse each Node until the index Node is found
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;
returnx; }}Copy the codeThe node function is used to find the specified index subscript node, and then obtain its item attribute value. The node search needs to traverse.
set(int index, E element)
Set (int index, E element) sets item of the specified subscript node to the specified value:
public E set(int index, E element) {
// Check subscript validity
checkElementIndex(index);
// Get the index index node
Node<E> x = node(index);
// Get the old value
E oldVal = x.item;
// Set the new value
x.item = element;
// Return the old value
return oldVal;
}
// Use dichotomy to traverse each Node until the index Node is found
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;
returnx; }}Copy the codeAs you can see, the set method also needs to traverse to find the target node.
remove(int index)
Remove (int index) Deletes the specified subscript node:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
Copy the codeRemove (int index) Uses the node method to find the node to be deleted, and then calls the unlink method to change the prev and next nodes of the deleted node.
The rest of the methods can read the source code themselves.
RandomAccess interface
The RandomAccess interface is an empty interface that contains no methods but serves as an identifier:
package java.util;
public interface RandomAccess {}
Copy the codeClasses that implement this interface indicate that they support fast random access. For example, ArrayList implements this interface, indicating that ArrayList supports fast random access. Fast random access refers to the ability to quickly retrieve an element object by its index without traversing it. LinkedList does not have this feature and must traverse the list to retrieve an element.
In the Collections class binarySearch(List
> list, T key) method, you can see RandomAccess applied:
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Copy the codeCall indexedBinarySearch when a List implements the RandomAccess interface, otherwise call iteratorBinarySearch. So when iterating through a collection, if the collection implements RandomAccess, the plain for loop is preferred, followed by foreach; Iterate over an interface that does not implement RandomAccess, preferring iterator to iterate.