preface
The linked list structure should be clear to everyone. LinkedList is implemented based on two-way linked list. The previous article briefly analyzed ArrayList, which is implemented based on array; This article will make a simple analysis of LinkedList. As long as you understand the structure of the linked list, the source code looks very simple, just the binding and unbinding operation between nodes.
1, Data and linked list
The two-way linked list has three important attributes: node (data node), PRED (previous node) and next (next node). It is linked together through the association relationship between nodes. The advantage of this is that it increases, deletes and traverses faster, but its random search is slower than the array. The search for an element in a normal array is calculated through binary search, Faster query efficiency; The linked list can only traverse from the beginning to the end to find the corresponding elements.
2, LinkedList
LinkedList is implemented based on a two-way linked list. A Node class is defined inside it to represent the nodes of the linked list.
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;
}
}
Core attribute
There is a Node class inside the LinkedList, which is a Node in the linked list. Needless to say, it is basically clear to those who understand the basic data structure.
Core properties of LinkedList:
- size: also records the length of internal elements of LinkedList.
- First: the first element.
- Last: the last element.
Core method
Construction method
The construction method of LinkedList does not specify the size, because its implementation is a linked list without specifying the size.
Let's not talk about parameterless construction. There's nothing. Let's take a look at the construction method of passing Collection.
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* The core method is addAll, which converts the contents of other types of collections into linked list form
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
//Convert collection to array
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//Find the corresponding node
Node<E> pred, succ;
if (index == size) { //At first, the size and index are the same, both 0
succ = null;
pred = last;
} else { //Don't go here at the beginning. You can only go here when there is data in the linked list
succ = node(index); //Find the corresponding index of the node
pred = succ.prev;
}
//Loop through
for (Object o : a) {
@SuppressWarnings("unchecked")
E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) //For the first time, pred is empty, and the head node is the created node
first = newNode;
else //Sets the link point between nodes
pred.next = newNode;
pred = newNode; //Assign the intermediate value again
}
//Assign the last node as the last node after traversal
if (succ == null) {
last = pred;
} else { //Establish the link between the two linked lists
pred.next = succ;
succ.prev = pred;
}
size += numNew; //size is set to the common length of the two linked lists
modCount++;
return true;
}
/**
* Node lookup
*/
Node<E> node(int index) {
//If the passed in index is less than the length of the current linked list / 2, search from left to right
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//If the passed in index is greater than the length of the current linked list / 2, search from right to left
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
add() method
public boolean add(E e) {
linkLast(e);
return true;
}
//Hang the added node at the end of the linked list
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++;
}
get() method
Directly return the element bound by the subscript node
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
remove() method
The remove() method of LinkedList also has subscript removal and object removal
Subscript removal:
public E remove(int index) {
checkElementIndex(index);
//Find the element at the subscript position and unlink it
return unlink(node(index));
}
Object removal, first traverse to find the corresponding element, and then unlink:
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;
}
Take a look at the method of unlinking:
E unlink(Node<E> x) {
//Gets the element in x, the previous node and the next node
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//If the previous node is empty, then x is the head node, and set the next node as the head node; If the previous node is not empty, bind the previous node and the next node together
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//If the next node is empty, then x is the tail node. Set the previous node as the tail node; If the next node is not empty, bind the previous node and the next node together
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//If the reference of the X element position is set to null, and the links between the upper and lower nodes of X are also disconnected and set to null, then x is completely released and will be recycled during garbage collection
x.item = null;
size--;
modCount++;
return element;
}
The size() method is also omitted. Although the linked list has no length, there is a size inside the LinkedList, which always records how many elements are currently stored.