How to implement LinkedList (JDK1.8)
The underlying LinkedList uses a two-way LinkedList. If you are familiar with the structure of LinkedList, it is quite easy to understand the implementation principle of LinkedList.
A linked list is a series of discrete blocks of memory connected by “Pointers”, where each element (node) points to its next element and the next pointer to the last node is null, whereas a bidirectional list means that every element except the first node has a pointer to its last element. Linked list is different from array, because of its discontinuous address, and the size of the element occupation is uncertain, so it can not directly value according to the address, the acquisition of elements requires traversal access, and bidirectional linked list compared with one-way linked list, to a certain extent, occupy extra memory, but support bidirectional traversal, speed up the element request.
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.SerializableCopy the codeAbstractSequentialList class, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList, AbstractSequentialList AbstractList However, LinkedList also implements the Queue interface, so LinkedList also supports the use of queues, such as PEEK, POP, and so on.
1. Member variables
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item ! = null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */ transient Node<E> last;Copy the codeThere are only three main member variables of LinkedList: size, first, and last. This is also in line with the characteristics of bidirectional linked lists. The whole LinkedList can be traversed according to the head or tail nodes. The Node type is the inner class Node.
Private static class Node<E> {private static class Node<E> {private static class Node<E> { // next Node Node<E> next; // Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}Copy the codeThe Node class simply has three attributes, namely the three elements required for a bidirectional list Node: item for the current Node, next for the next Node, and prev for the previous Node.
2. Construction method
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); // addAll elements addAll(c); }Copy the codeLinkedList is basically just two constructors, one that takes no arguments and does nothing, and the other that takes a collection, which initializes the LinkedList object and adds all the elements of collection C.
We’ll look at the addAll method later.
Because LinkedList is based on linked lists, there is no need to apply for memory size in advance. Therefore, there is no constructor to initialize LinkedList with specified size.
3. Add elements
3.1. Tail addition
There are many ways to add a LinkedList, starting with the simplest and most commonly used tail addition.
public boolean add(E e) {
linkLast(e);
return true;
}Copy the codeThe main logic is linkLast(E E).
void linkLast(E e) { final Node<E> l = last; Last final Node<E> newNode = newNode <>(l, E, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; // increment the operand modCount++; }Copy the codeTo add a newNode, newNode is constructed, and the last node prev points to the original last node, and the node is changed to the new last node. If l == null, newNode is also the head node. If L is null, newNode is the only element in the current set. If l is not null, the next node of all L points to newNode because of the bidirectional list.
Finally, the size increment and modCount increment are done.
Tail in addition to the add operation, there is also a addLast (E, E) method, both in addition to the return value is the same, there is no difference, are called linkLast method.
public void addLast(E e) {
linkLast(e);
}Copy the code3.2. Intermediate additions
Public void add(int index, E element) {// Range checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }Copy the codeFor intermediate to add, need a range check first of all, namely guarantee insert location index between [0, size], otherwise throw an array abnormal IndexOutOfBoundsException, er… Array out of bounds……
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 codeIf index == size, it’s a tail insert, so we call linkLast, which we just talked about tail insert.
If index < size, insert the middle in two steps:
- The node(int index) method retrieves the element succ at index
- LinkBefore (E E, Node succ) concatenates the element element to be inserted after succ
The Node method is a frequently invoked method, and many operations on the LinkedList depend on it finding the corresponding element. Index < (size >> 1), compared with the middle position, the first position is the first order traversal, otherwise the last order traversal.
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; return x; }}Copy the codeThe traversal logic is simple: loop to the Node above index (or next), get next (prev) and return 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); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }Copy the codeLinkBefore is almost exactly the same as linkLast, except that one is added to last and one is added to SUCC.
For intermediate inserts, if the index is 0, the header inserts will be inserted instead of calling node to find the element, so LinkedList also provides an addFirst(E E) method.
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}Copy the code3.3. Batch Insert
LinkedList provides tail bulk inserts and middle bulk inserts, but the internal implementation actually calls addAll(Int Index, Collection C).
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? Extends E> c) {// range 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 insert for (Object o: a) {@suppressWarnings ("unchecked") 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 codeThe addAll(int index, Collection C) method may seem complicated at first glance, but it becomes clearer when you understand how it works. List insertion is like a water pipe, which is disconnected at one point and then connected to the part that needs to be connected. In this method, the key is the two Node objects pred and succ, where succ is the index position element and pred is the element preceding the index.
Index == size; succ = null; pred = last;
Next comes the loop assignment, where a node is constructed, similar to linkLast.
The last one is the concatenation, if the tail is inserted, then pred is the tail node (loop assignment pred = newNode), so just specify last = pred. Next = succ, and succ.prev = pred binds the index position to the new preceding element.
4. Find elements
In addition to providing the generic GET, which has the first and last nodes in its attributes, LinkedList also provides the getFirst and getLast methods.
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}Copy the codeFor getFirst and getLast, since they are member variables, the search process is omitted and the item can be returned directly.
Public E get(int index) {// Range checkElementIndex(index); Return node(index).item; }Copy the codeBy obtaining the pointer, the main is to call the node method to find the node corresponding to the index, node method has been described in front, no longer tiresome.
5. Modify elements
To modify an element in the LinkedList collection, first find the element and then change its Node data item.
Public E set(int index, E element) {// Scope checkElementIndex(index); Node<E> x = Node (index); E oldVal = x.item; x.item = element; return oldVal; }Copy the code6. Delete elements
LinkedList provides a number of ways to delete elements, but the internal implementation logic is basically the same: find the corresponding Node and replace the points pointing to that Node.
6.1. Remove by index
Let’s first look at the remove(int index) method by index.
Public E remove(int index) {// Range checkElementIndex(index); Return unlink(node(index)); }Copy the codeThe unlink(node x) method is the main logic for deleting a node.
E unlink(Node<E> x) { // assert x ! = null; final E element = x.item; // Final Node<E> next = x.next; // Final Node<E> prev = x.rev; If (prev == null) {first = next; if (prev == null) {first = next; } else { prev.next = next; x.prev = null; If (next == null) {last = prev;} // If (next == null) {last = prev; } else { next.prev = prev; x.next = null; } // Trigger GC work x.tem = null; size--; // operate counter increment modCount++; return element; }Copy the codeThe whole unlink method is a standard two-way list deletion operation, with three nodes prev, x, and next. Deleting x actually points prev to Next, and next to prev, but with some special judgments.
Take a look at remove by index, and then take a look at removeFirst and removeLast, two other special cases.
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(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 first = next; if (next == null) last = null; else next.prev = null; size--; // operate counter increment modCount++; return element; }Copy the codeUnlinkFirst is a simplified version of the unlink method, because only the head node is processed, and the next node, next, exists as the new first.
Similarly with removeLast, you can experience it yourself.
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(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 last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }Copy the codeThe LinkedList also has a remove with no arguments, which is defined by the Deque interface and implemented as removeFirst.
public E remove() {
return removeFirst();
}Copy the code6.2. Remove by element
Removing by element is not much different from removing by index, except that the way you find the corresponding node has changed.
Public Boolean remove(Object o) {LinkedList support null 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 codeAs you can see, the node is found and the unlink method is called regardless of whether the element is null.
Due to the nature of two-way traversal, LinkedList provides both pre-order deletion and post-order deletion methods, namely removeFirstOccurrence and removeLastOccurrence.
public boolean removeFirstOccurrence(Object o) { return remove(o); } public Boolean removeLastOccurrence(Object o) {if (o == null) {for (Node<E> x = last; x ! = null; x = x.prev) { if (x.item == null) { unlink(x); return true; For (Node<E> x = last; x ! = null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }Copy the codeThere’s nothing magical about these two methods. The removeLastOccurrence just loops through the collection in reverse order.
6.3. Delete files in batches
In the LinkedList class, there is no removeAll method because it doesn’t override it, but uses its parent, AbstractCollection
public boolean removeAll(Collection<? > c) { Objects.requireNonNull(c); boolean modified = false; // Use the Iterator<? > it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; }Copy the codeAbstractCollection class AbstractList class has its implementation, but AbstractSequentialList class overwrites this method.
public Iterator<E> iterator() {
return listIterator();
}Copy the codeThe iterator method calls listIterator(), which is implemented in AbstractList. It calls listIterator(int index), but LinkedList overwrites it, So it goes all the way back to the LinkedList.
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}Copy the codeHere the ListItr object is the inner class of LinkedList.
private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; Private int expectedModCount = expectedModCount;Copy the codeWhen ListItr is initialized, the operation counter modCount is assigned to the expectedModCount, and each subsequent remove method checks whether the expectedModCount is equal to the expectedModCount, otherwise an exception is thrown.
The ListItr remove method incremented the expectedModCount after each call, so that modCount == expectedModCount has been synchronized with unlink modCount++, so that modCount == expectedModCount is always valid. This is why we need to use the remove method of the LinkedList element’s iterator when looping to delete it.
Public void remove() {// Check modCount checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; // unlink delete node logic, modCount++; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; // expectedModCount Self-incrementing expectedModCount++; } final void checkForComodification() {// expectedModCount and modCount must be equal if (modCount! = expectedModCount) throw new ConcurrentModificationException(); }Copy the code