LinkedList overview
LinkedList is an important implementation of the Java Collections framework. Let’s briefly describe some of the features of LinkedList:
LinkedListUnderlying adoptedTwo-way linked listStructure;LinkedListSupport for null and duplicate values (a feature of lists);LinkedListDeque interface, with the characteristics of a double-ended queue, can also be used as a stack;LinkedListWhen storing elements, you do not need to expand them as you would with an ArrayList, but the nodes that store elements need extra space to store precursor and subsequent references.LinkedListThe insertion efficiency is relatively high at the head and tail of the linked list. However, when the insertion is performed at the specified position, the node at this position needs to be located. The time complexity of this operation isO(N);LinkedListA non-thread-safe collection class, where multiple threads working on the LinkedList at the same time can raise unexpected exception errors in a concurrent environment.
LinkedList inherits the architecture
View the inheritance system of LinkedList directly through IDEA. The architecture is complicated, so take a look at it one by one.
- AbstractSequentialList;
- Implement List and Deque interface;
- Implement serialization interface;
- Cloneable interface is implemented
AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList AbstractSequentialList provides methods that are basically implemented through ListIterator, such as the get and Add methods below. However, although LinkedList inherits AbstractSequentialList, it does not directly use the methods of the parent class. Instead, it re-implements a set of methods, the implementation of which will be discussed later.
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}// Leave it to subclasses
public abstract ListIterator<E> listIterator(int index);
Copy the codeIn addition, as outlined at the beginning of this article, LinkedList implements the Deque interface and features a dual-ended queue.
Member properties of the LinkedList
// Record the actual number of elements in the list
transient int size = 0;
// Maintain the first reference of the linked list
transient Node<E> first;
// Maintain the last node references of the linked list
transient Node<E> last;
Copy the codeYou can see that first and last are of type Node, so let’s take a quick look at the inner class in LinkedList
private static class Node<E> {
E item; // The actual element in the node
Node<E> next; // Maintain the successor of the node
Node<E> prev; // Maintain the precursor of the node
// create a new node with parameters: precursor node, insert element reference, successor node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeIt can be seen that the structure of the Node static internal class is relatively simple, each Node maintains its own stored element information + precursor Node reference + successor Node reference. Without going into too much detail here, let’s take a quick look at how the LinkedList is constructed
Constructor of LinkedList
// Create an empty set (the list is empty)
public LinkedList(a) {}// Call your own no-argument constructor to construct an empty Collection, and then add all the elements in the Collection to the list
// If the Collection is passed empty, a null-pointer exception will be thrown
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeThe main method of LinkedList
The add method
The main methods for adding LinkedList implementations are as follows
-
Add nodes to the end of the list (linkLast method)
-
Add an element to the top of the list (linkFirst method)
-
Add elements to the middle of the list (linkBefore method)
Let’s look at the implementation of these three methods.
(1) linkLast method
public void addLast(E e) {
linkLast(e);
}
Copy the codeLinkLast () : linkLast () : linkLast (); linkLast () : linkLast ();
void linkLast(E e) {
// (1) Obtain the global successor node of the current list instance
final Node<E> l = last;
// create a new Node, as we know from the Node constructor
// The element item in this new node is the generic reference passed in at the moment. The precursor node is the global successor node, and the successor node is null
//(that is, the new node is the new successor node of the linked list)
final Node<E> newNode = new Node<>(l, e, null);// Node(Node<E> prev, E element, Node<E> next){}
// (3) Update the reference to the global successor node
last = newNode;
// (4) If the successor of the original list is null, then the global header reference is also required to point to the new node
if (l == null)
first = newNode;
// the prev of newNode is set to last when a newNode is created. So here we have to put the original last
// Set the successor of the node to newNode
else
l.next = newNode;
// (6) Update the number of sizes in the current list
size++;
// (7) Here is the parameter used by the fast-fail mechanism
modCount++;
}
Copy the codeLet’s briefly simulate this process with an example diagram
- When the list is initially empty, we call add to add a new node
- The list is not empty when the add method is called to add nodes at the end of the list
(2) linkFirst method
This method is a private method that is exposed to the consumer through the addFirst method call.
public void addFirst(E e) {
linkFirst(e);
}
Copy the codeLet’s focus on the implementation logic of the linkFirst method
private void linkFirst(E e) {
// (1) Get the global head node
final Node<E> f = first;
// create a new node whose predecessor is null and whose successor is the current global first node
final Node<E> newNode = new Node<>(null, e, f);
// (3) Update global header references
first = newNode;
// if the first node is null, the last node points to the new node
if (f == null)
last = newNode;
// (5) is not null, the precursor of the original head node is newNode
else
f.prev = newNode;
size++;
modCount++;
}
Copy the codeThe logic above is also relatively simple, which is to set the newly added node as the head node, and then update the link between the nodes in the linked list. Let’s use the following diagram to understand briefly.
(3) linkBefore method
public void add(int index, E element) {
// Check the validity of index: if the value is greater than or equal to 0 and less than or equal to size, an exception will be raised
checkPositionIndex(index);
//index = size, insert a new node at the end, as mentioned above
if (index == size)
linkLast(element);
// Insert node at index (node(index));
else
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;
}
Copy the codeThe main logic in the add(index,element) method is linkBefore, so let’s look at this method. Before that, we call node(index) and find the node at index
Node<E> node(int index) {
//index < size/2
if (index < (size >> 1)) {
// Use the global header node to find (traverse the list)
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//index > size / 2
Node<E> x = last;
// Use the global tail node to look forward
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeNode method makes use of the two characteristics of bidirectional linked list and record the total length of the linked list. It is divided into two parts to traverse and query the nodes at the position of JIndex. After this node is found, the linkBefore method is called as an argument, as shown below
void linkBefore(E e, Node<E> succ) {
//succ ! = null; Succ is the node at the specified location
// Element =succ
final Node<E> pred = succ.prev;
// Create a new node
// A precursor is a precursor of an incoming node
// The successor is the node passed in
final Node<E> newNode = new Node<>(pred, e, succ);
// Update the precursor reference to the index node
succ.prev = newNode;
// the index node is null, which is equivalent to inserting the node in the head and updating first
if (pred == null)
first = newNode;
// not null, then its successor is the new node
else
pred.next = newNode;
size++;
modCount++;
}
Copy the codeThe logic of this method is also relatively simple. It is to insert a new node between succ and succ.prev. We understand this process by simple illustration
delete
As a double-ended queue, there are two ways to delete elements: at the beginning of the queue, at the end of the queue. As a List, you need to support intermediate deletion of elements, so there are three methods for deleting elements.
(1) unlinkFirst method
The following are two public methods that call unlinkFirst. The main difference is that removeFirst raises an exception when first is null, while pollFirst returns NULL.
// remove throws an exception if no element is present
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// poll returns null if there are no elements
public E pollFirst(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
Copy the codeMainly look at the implementation of the method unlinkFirst
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
// Get the element value of the header
final E element = f.item;
// Get the successor of the header
final Node<E> next = f.next;
// Delete item and its successor, GC
f.item = null;
f.next = null; // help GC
// Update the header reference (the successor of the original header)
first = next;
// If there is only one node in the list, then the last node is null
if (next == null)
last = null;
// Set the precursor of the new head node to NULL
else
next.prev = null;
// Update size and modCount
size--;
modCount++;
// Returns the value of the original head node
return element;
}
Copy the code(2) unlinkLast method
The following are two public methods that call unlinkLast. The main difference is that removeLast raises an exception when first is null, while pollLast returns NULL.
// remove throws an exception if no element is present
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// poll returns null if there are no elements
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
Copy the codeThe following is an implementation of the unlinkLast method
// Delete the tail node
private E unlinkLast(Node<E> l) {
// The element value of the last node
final E element = l.item;
// The leading pointer to the tail node
final Node<E> prev = l.prev;
// Clear the contents of the tail node to assist GC
l.item = null;
l.prev = null; // help GC
// Make the front node the new tail node
last = prev;
// If there is only one element, delete and set first to null
// Otherwise, empty next for the front node
if (prev == null)
first = null;
else
prev.next = null;
// Update size and modCount
size--;
modCount++;
// Returns the deleted element
return element;
}
Copy the code(4) Unlink method
// Delete the intermediate node
public E remove(int index) {
// Check for overbounds
checkElementIndex(index);
// Delete the index node
return unlink(node(index));
}
Copy the code// Delete node X
E unlink(Node<E> x) {
// The element value of x
final E element = x.item;
// The front node of x
final Node<E> next = x.next;
// the post-node of x
final Node<E> prev = x.prev;
// If the front node is empty
// specify the first node, so that first points to the node after x
// Otherwise change next of the front node to the back node of x
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// If the back node is empty
// Last points to the front node of x
// Otherwise, change the prev of the rear node to the front node of X
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// Empty the element value of x to assist GC
x.item = null;
// The number of elements is reduced by 1
size--;
// The number of changes is increased by 1
modCount++;
// Returns the deleted element
return element;
}
Copy the codeTo find the
LinkedList is based on a LinkedList structure and does not randomly access elements in a given location as an ArrayList does. The LinkedList lookup is a bit more cumbersome, going back from the head (or tail) of the list in O(N) time. The relevant source code is as follows:
public E get(int index) {
checkElementIndex(index); // Check the validity of index
// Call the node method to iterate through the node at index and return the node's item, as described above
return node(index).item;
}
Copy the codetraverse
The list traversal process is also very simple, similar to the above search process, we go back to the beginning of the node on the line. However, you need to be careful about traversing the LinkedList, which can lead to inefficient code. Typically, we would iterate over the LinkedList using foreach, which ultimately translates to an iterator. So the core of analyzing LinkedList traversal is its iterator implementation, which looks like this:
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
The /** constructor refers next to the node */ at the specified location
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext(a) {
return nextIndex < size;
}
public E next(a) {
checkForComodification();
if(! hasNext())throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
/ /... other method
}
Copy the codeHere’s a quick note about traversing the LinkedList. Linkedlists are not good at random location access, and it would be inefficient to traverse a LinkedList using random access. For example:
List<Integet> list = new LinkedList<>();
list.add(1)
list.add(2)...for (int i = 0; i < list.size(); i++) {
Integet item = list.get(i);
// do something
}
Copy the codeWhen there are many elements in the list, the above traversal method is very inefficient. The reason is that the above method requires traversal of the beginning node(or the end node) for every element acquired (call get(I) method, the implementation of which is described above), which is inefficient and inefficient in the case of large data volume. This should be avoided in everyday use.
conclusion
Finally, summarize the differences between ArrayList and LinkedList that are often asked in interviews. For ArrayList, please refer to my previous source analysis of ArrayList.
-
ArrayList is based on dynamic array implementation, LinkedList is based on bidirectional LinkedList implementation;
-
ArrayList(array subscript access) is superior to LinkedList(traversal list access) for random access;
-
Without adding data directly to the tail, an ArrayList adds/deletes data to and from the specified index by copying the array. LinkedList is implemented by addressing node pointing; So LinkedList (changing the next and prev points of a node) is better than ArrayList (moving array elements).
-
LinkedList does not waste space on the data store. Dynamic expansion of ArrayList results in some space being wasted.