preface
The previous article looked at the internal working logic of ArrayList, and this one continues with LinkedList. The introduction of data structure learning can know that array and chain data structure is the most basic physical structure in programming, queue, stack, tree and other structures are logical concepts extended on this, array represents the continuous address space, in the initialization stage must specify the size of space; And today’s protagonist – linked list, is to use the “link”, do not take up a bit of your memory, now to understand the internal is how to do.
This article is based on JDK 1.8 LinkedList and is learned through the standard List interface.
A quick look at the members of our LinkedList:
transient int size = 0;
/ / head node
transient Node<E> first;
/ / end nodes
transient Node<E> last;
// It is obvious from the precursors and successors that this is a bidirectional list
private static class Node<E> {
E item; / / element
Node<E> next; / / the subsequent
Node<E> prev; / / precursor
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the code1. add(E) & add(int, E)
Let’s start with the add logic, because the add(E) logic is also handled in add(int, E), so let’s go straight to add(int, E).
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Copy the codeIf the index is equal to size, the index is appended to the end of the list. If the index is not, the index is inserted into the middle of the list.
LinkLast () :
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++;
}
Copy the codeSince it is appended to the tail, we need to get the tail node, and make the precursor of the node to be inserted (newNode) point to the current tail node, and then make the member of the node to be inserted (newNode) new tail node; If l is null, it indicates that there are no elements in the current list. If l is null, the first header should also point to newNode, or the successor of l should point to newNode. Finally, size++, modCount refers to the number of changes, which is related to iteration, so it is not involved here.
LinkBefore () takes two arguments. The first parameter is the index at the insertion position, and the second parameter is the node at the current index position. Let’s see how the node() method gets a node at a specified location:
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 codeEach node of the linked list is linked by chain. If you want to find the element at the specified position, you can only traverse it. The logic here is bidirectional linked list, so you can determine whether the index is in the left half or the right half of the size range. Then, it traverses half backwards from the head node or half forwards from the tail node respectively. Although the optimization of traversal here is still O(n) complexity, it can save half of the traversal time in the actual search process.
The node() method is now ready for linkBefore().
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++;
}
Copy the codeThe suCC passed in is not null, because the add method has already been checked for indexes. If the index is not valid, it will throw an exception, and the rest will be valid indexes.
NewNode: pred (succ), succ (succ), suCC (suCC), suCC (suCC);
- Before ：pred <–> succ
- After ：pred <– newNode <–> succ
At this point the element is inserted before succ, but that’s not all. If the fetched pred is empty, meaning suCC is the head node, newNode must also become the new head node, with first pointing to newNode; If not empty, the successor of pred points to newNode and then size++.
2. remove(int) & remove(Object)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
Copy the codeRemove (int) is relatively simple, node() we already know its logic, and unlink() also appears in remove(Object), so directly look at remove(Object) 👇.
Unlink () : unlink(); unlink() : unlink(); unlink() : 👇
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 codeUnlink () looks longer than any of the previous methods, but the logic is pretty simple: first fetch the old element of x, because the old element will be returned at the end, then fetch the precursor and successor of x, and begin the deletion operation:
if(Null precursor) indicates that X is the head node, so you need to point FIRST to x's successor, nextelseX is not the head node, and the successor of the precursor of X (prev) points directly to the successor of X (next)if(empty) indicates that X is the tail node and last needs to point to the precursor prev of XelseX is not a tail node, empty the precursor of the successor of X (next) to the precursor of X (prev)Copy the code- Before ：prev <–> x <–> next
- After ：prev <–> next
And then I’m going to empty the x element and then SIZE.
3. get(int)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Copy the codeThe node() method takes the node and returns the element
4. indexOf(Object)
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)
returnindex; index++; }}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
returnindex; index++; }}return -1;
}
Copy the codeThe traversal logic that distinguishes null values is already seen in remove(Object).
5. clear()
public void clear(a) {
// 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++;
}
Copy the codeEmpty elements, first and last. This is generally ok because the GC Root line is broken, but it still iterates through the linked list to clear elements before and after each node.
- Generational GC is facilitated if the discarded node exists in multiple generations
- Even during iteration, make sure memory is freed first
At the end
In the process of learning, it can be found that adding elements always needs to perform different logic for the beginning and the end nodes, so can we unify it? This problem can be optimized by using sentinel nodes.
In simple terms, the sentinel node is an empty node that holds no elements, only links. To make the list “never empty”, so that we don’t need to deal with the boundary problem, here is a simple sentinel node version written by Kotlin, as follows:
class LinkedList<E> : AbstractList<E>() {
private var first: Node<E>
private var last: Node<E>
override var size: Int = 0
private set
init {
val f = Node<E>(null.null.null)
val l = Node<E>(null.null.null)
f.next = l
l.prev = f
first = f
last = l
}
override fun add(index: Int, item: E): Boolean {
checkIndexForAdd(index)
val node = if (index == size) last else node(index)
linkBefore(node, item)
return true
}
private fun linkBefore(node: Node<E>, item: E) {
val prev = node.prev
valnewNode = Node(item, prev, node) prev? .next = newNode node.prev = newNode size++ }override fun remove(item: E): Boolean {
val index = indexOf(item)
if (index < 0) {
return false
}
val node = node(index)
returnunlink(node) ! =null
}
override fun removeAt(index: Int): E {
return unlink(node(index))
}
private fun unlink(node: Node<E>): E {
val oldVal = node.item
val prev = node.prev
valnext = node.next prev? .next = next next? .prev = prev size--return oldVal as E
}
override fun set(index: Int, item: E): E {
val node = node(index)
val oldVal = node.item
node.item = item
return oldVal as E
}
override fun get(index: Int): E {
return node(index).item as E
}
override fun indexOf(item: E): Int {
for (i in 0 until size) {
if (node(i).item == item) {
return i
}
}
return -1
}
private fun node(index: Int): Node<E> {
checkIndex(index)
var node: Node<E>?
if (index < size shr 1) {
node = first.next
for (i in 0until index) { node = node? .next }return node!!
}
node = last.prev
for (i in (size - 1) downTo (index + 1)) { node = node? .prev }return node!!
}
private fun checkIndexForAdd(index: Int) {
if (index < 0 || index > size) {
throw IndexOutOfBoundsException(errorMsg(index))
}
}
private fun checkIndex(index: Int) {
if (index < 0 || index >= size) {
throw IndexOutOfBoundsException(errorMsg(index))
}
}
private fun errorMsg(index: Int): String {
return "Index: $index, Size: $size"
}
override fun clear(a) {
first.next = last
last.prev = first
size = 0
}
override fun toString(a): String {
if (isEmpty()) {
return "[]"
}
val sb = StringBuilder().also {
it.append("[")}for (i in 0 until size) {
val item = node(i).item
sb.append("$item")
if (i == size - 1) {
sb.append("]")}else {
sb.append(",")}}return sb.toString()
}
private class Node<E>(
varitem: E? .varprev: Node<E>? .var next: Node<E>?
)
}
Copy the code