Let’s move on to part 15 of our JDK series
An overview of the
The source code for LinkedList is actually relatively easy to understand if you understand the basic structure of a LinkedList. LinkedList is implemented based on a bidirectional LinkedList, which, unlike ArrayList, does not occupy contiguous memory space in memory and is linked by “chains” between linked elements. For singly linked lists, each node has a successor pointer to the next node. For a bidirectional list, in addition to the successor pointer, there is a precursor pointer to the previous node. So what’s so good about a two-way list? Since there is a precursor pointer, when traversal can be traversed forward, as can be seen in the source code analysis below, this is a single linked list does not have the function.
As I mentioned earlier with ArrayList, arrays have random access, and the time complexity of random access by subscript is O(1). Similarly, in order to ensure the continuity of memory, its insert and delete operations are much less efficient. On the contrary, linked lists do not have random access, but inserts and deletes are relatively efficient, and only need to modify the nodes to which the successor and precursor Pointers point. The time complexity of both insert and delete operations is O(1), but this O(1) is not very rigorous. Delete the specified node, or delete the node value equal to the given value, single list or bidirectional list, in fact, the performance of time complexity is not the same, the following source code analysis will also be reflected. So much for LinkedList, let’s get into the source code analysis of LinkedList.
First take a look at the UML diagram of LinkedList:
The source code parsing
Class declaration
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable {}
Copy the code-
AbstractSequentialList inherits AbstractSequentialList class, which provides the implementation of some basic methods independent of collection type, such as get set Add remove, etc. In general, the collection types that implement it do not have random access capability, as opposed to AbstractList.
-
Implement the List interface
-
The realization of the Deque interface, that can also be used as a double-ended queue, the source code has also implemented the relevant methods.
-
Cloneable interface is implemented to provide cloning capability. Like ArrayList, it is a shallow copy.
-
Serializable interface is implemented to provide serialization capability
Member variables
transient int size = 0; // Indicates the list size
transient Node<E> first; / / head node
transient Node<E> last; / / end nodes
private static final long serialVersionUID = 876323262645176354L;
Copy the codeTake a look at the definition of the Node class:
private static class Node<E> {
E item;
Node<E> next; // Next pointer
Node<E> prev; // Precursors
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeEach node contains a precursor pointer to the previous node, prev, and a successor pointer to the next node, next. A precursor pointer to a head node and a successor pointer to a tail node both point to NULL.
The constructor
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeThe first is the default no-parameter construct, which builds an empty linked list. The second list is constructed using the addAll() method based on the set of arguments. The order of the elements in the list is based on the iteration order of the iterators of set C.
methods
If you look at the LinkedList API list, there are many, many methods, many of which are repetitive. It implements methods in the Deque interface and overwrites methods in AbstractSequentialList class. To sum up, it calls its own private methods linkxxx/unlinkxxx. It is also a design idea worth learning. Let’s take a look at these methods first.
linkFirst(E e)
// set e to the head
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) // If the list is empty, e is the last node
last = newNode;
else
f.prev = newNode; // Insert the prev of the original header into e
size++;
modCount++;
}
Copy the codeIf the list is empty, e is inserted as both a header and a tail.
If the list is not empty, move the precursor pointer to the original header.
linkLast(E e)
// set e to the end
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; // If the list is empty, e is the head node
else
l.next = newNode; // Insert e into the list, and point next from the original tail to e
size++;
modCount++;
}
Copy the codeIf the list is empty, e is inserted as both a header and a tail.
If the list is not empty, the subsequent pointer to the original tail is moved.
linkBefore(E e, Node succ)
// Insert elements before node succ
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); // Build a new node
succ.prev = newNode; // Set succ's prev pointer to the new node
if (pred == null) // if pred is null, succ is the original header, and now the header needs to be updated
first = newNode;
else
pred.next = newNode; // The next pointer to the previous node of succ points to the new node
size++;
modCount++;
}
Copy the codeIt’s very simple, you can think of it as a knotted rope, you just open the SUCC node, and then you tie the node that you want to insert, in order one time. Of course, this is a two-way list. Is it still O(1) for a one-way list? Obviously not, because you can’t execute the following line of code in a one-way list:
final Node<E> pred = succ.prev;
Copy the codeThat is, you can’t get the precursor of suCC directly, and you can’t directly point the next pointer from the previous node of SUCC to the new node. You can only get the precursor by traversing. So, for a singly linked list, the insertion time is still O(n).
unlinkFirst(Node f)
// remove the header f
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC header is null for GC
first = next;
if (next == null) // Next is empty, indicating that the list originally had only one element
last = null;
else
next.prev = null; // Empty the prev of next, where next is the header
size--;
modCount++;
return element;
}
Copy the codeThe f node in the default parameter is the header. If there is only one element in the linked list, then the first and last nodes are null. If there is more than one element, just the precursor pointer to the next node of the head node points to NULL.
unlinkLast(Node l)
// Remove the tail node L
private E unlinkLast(Node<E> l) {
// assert l == last && l ! = null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC header is null for GC
last = prev;
if (prev == null) // Prev is empty, indicating that the list originally had only one element
first = null;
else
prev.next = null; // Empty next of prev, where prev is the tail
size--;
modCount++;
return element;
}
Copy the codeUnlinkfirst = null; unlinkFirst = null; unlinkFirst = null;
unlink(Node x)
// Remove the specified non-empty node x
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) { // x is the header
first = next;
} else {
prev.next = next; // Next of x points to a node after x
x.prev = null;
}
if (next == null) { // x is the tail node
last = prev;
} else {
next.prev = prev; // Point the prev of x to a node in front of x
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeThe code is also relatively simple, modify the previous node’s successor pointer and the next node’s precursor pointer, pay attention to the parameter node is the head or tail of the special case. The time complexity is also O(1), O(n) for singly linked lists.
The above inserts and deletes are for specified nodes and, in the other case, for specified values. For example, for a linked list of int values, if I want to delete a node of value 1, is the time still O(1)? Now let’s look at the remove(Object O) method.
remove(Object o)
public boolean remove(Object o) {
if (o == null) { // Delete the null element
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null) {
unlink(x);
return true; }}}else { // Remove non-null elements
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true; }}}return false;
}
Copy the codeObviously, for nodes whose deletion value is equal to the specified value, the time complexity is also O(n). Loop through the node and then call unlink() to delete it. Note also that this method only removes nodes whose first occurrence value is equal to the specified value. Lists allow duplicate elements.
Now that we’re done with insert and delete, let’s look at lookup. LinkedList is optimized for lookup, although the list lookup must be O(N). Let’s look at the get() method.
get(int index)
// Returns the element at the specified position
public E get(int index) {
checkElementIndex(index); // boundary check
return node(index).item; // The time complexity is still O(n), but only half of the list is traversed
}
Copy the codeCheckElementIndex Checks whether an index is out of bounds. The node() method is used to get the specified node at index.
Node<E> node(int index) {
// assert isElementIndex(index);
// Only half of the list is traversed at a time, depending on whether the subscript is less than size/2
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 codeThanks to the feature of bidirectional LinkedList, the search of LinkedList only needs to traverse half of the list each time. Although the time complexity is O(n), the performance is actually improved.
So much for the LinkedList method. Although most of the methods are not mentioned, the rest of the methods are basically based on the above analysis methods, so there is no need to come up with separate methods. I’ve annotated them all in the source file, so if you’re interested go to Github and check out linkedList.java.
conclusion
LinkedList is based on bidirectional LinkedList, discontinuous in memory, no random access, high insertion and deletion efficiency, low search efficiency. There is no size limit, natural support expansion.
Null values are allowed and duplicate elements are allowed. Like ArrayList, it is fail-fast. The Fail-fast mechanism was explained in detail in the Introduction to ArrayList (2) of the JDK and will not be covered here.
Bidirectional linked lists have performance advantages over unidirectional linked lists in some operations because they can be traversed in reverse. However, because each node needs extra memory space to store the precursor pointer, bidirectional linked lists need more memory space, which is also a reflection of space swap time.
Article first published wechat public account: Bingxin said, focus on Java, Android original knowledge sharing, LeetCode problem solving.
More JDK source code analysis, scan code to pay attention to me!
