LinkedList source code interpretation (the most detailed)

LinkedList source code interpretation

Inheritance structure of LinkedList

Properties of LinkedList

LinkedList constructor

The core method of LinkedList

FailFast mechanism

Inheritance structure of LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Properties of LinkedList

/**
 * LinkedList Length of bidirectional linked list
 */
transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 * Pointer to the first node of the two-way linked list. The initial value is null
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 * Pointer to the tail node of the bidirectional linked list. The initial value is null
 */
transient Node<E> last;
/**
 * A private static internal class, a very important data structure, represents a node of a two-way linked list
 */ 
private static class Node<E> {
    E item;    //Value of node
    Node<E> next;    //Pointer to the back node
    Node<E> prev;    //Pointer to the previous node

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
/**
 * Records the number of nodes added and deleted from the bidirectional linked list. This attribute is inherited from the parent class AbstractList of the direct parent class AbstractSequentialList. It is used to protect data security when reading and writing the bidirectional linked list at the same time in a concurrent environment
 */
protected transient int modCount = 0;

LinkedList constructor

Parameterless constructor
```
public LinkedList() {    //Nothing
}
```

Parametric constructor

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Another overloaded addAll method addAll method was called

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

The overloaded addAll method is defined as follows. Here we only look at the execution route

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);    // Check whether the index position is legal and 0 is legal

    Object[] a = c.toArray();    // Set to array
    int numNew = a.length;    // Get the length of the converted array, and then increase the length of the linked list
    if (numNew == 0)
        return false;

    Node<E> pred, succ;    // pred: points to the front node of the node to be inserted; succ: points to the back node of the node to be inserted
    if (index == size) {    //Go here and add in the tail. succ is null and pred is the tail node pointed to by last
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {    // Traverse, and add the elements in the transformed array to the bidirectional linked list in turn
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);    //Assembly node, the front pointer points to the tail node, and the rear pointer is null
        if (pred == null)    // The first element goes here as the first node
            first = newNode;
        else    // The remaining elements go here, and the rear pointer of the tail node points to the new node
            pred.next = newNode;
        pred = newNode;    // New node as tail node
    }

    if (succ == null) {    // Here, the tail pointer points to the tail node
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;    // Update the length of bidirectional linked list
    modCount++;
    return true;
}

The core method of LinkedList

Addfirst (E) method
```
public void addFirst(E e) {
    linkFirst(e);
}
```
Call the private linkFirst method. The linkFirst (E) method is defined as follows
```
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++;
}
```
The head insertion method of two-way linked list.

This method is used to add elements to the head of the two-way linked list. First, define a new node. The front pointer of the new node points to null, and the rear pointer points to the original first node. Take the new node as the first node, and then judge whether the original first node is null. If yes, it means that there are no nodes in the original linked list, and the new node is also used as the tail node, Otherwise, make the front pointer of the original first node point to the new node, and add 1 to the length of the two-way linked list.
Addlast (E) method
```
public void addLast(E e) {
    linkLast(e);
}
```
Call the private linkLast method. The linkLast (E) method is defined as follows
```
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++;
}
```
Tail interpolation of two-way linked list.

This method is used to add an element at the end of the two-way linked list. First, define a new node. The front pointer of the new node points to the original tail node, and the rear pointer points to null. Take the new node as the tail node, and then judge whether the original tail node is null. If yes, it means that there are no nodes in the original linked list, and the new node is also taken as the first node, Otherwise, make the back pointer of the original tail node point to the new node, and add 1 to the length of the two-way linked list.
removeFirst() method
```
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
```
This method is used to delete the first node of the two-way linked list.

First judge whether the first node exists. If it does not exist, throw a NoSuchElementException exception. Otherwise, call the unlinkFirst method to delete the first node.

The unlikfirst method is defined as follows
```
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--;
    modCount++;
    return element;
}
```
First find the next node of the first node, make the pointer of the first node point to null, take the next node as the new first node, and then judge whether the next node exists. If it exists, cancel the pointer before the next node, and the original first node will be recycled by GC if it loses application. If it does not exist, it means that the original linked list has only the first node, and make the last pointer point to null, The original first node loses the references of first and last at the same time, triggers GC and is recycled. The deletion is successful, and the length of the two-way linked list is reduced by 1.
removeLast() method
```
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
```
This method is used to delete the tail node of the two-way linked list.

First judge whether the tail node exists. If it does not exist, throw a NoSuchElementException exception. Otherwise, call the unlinkLast method to delete the tail node.

The unliklast method is defined as follows
```
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;
}
```
First find the prev of the previous node of the original tail node and cancel the pointing of the front pointer of the original tail node. Prev is used as a new tail node, and then judge whether prev is null. If so, it indicates that there is only one node in the original linked list, and make the first pointer null. In this way, the original tail node will lose the references of first and last at the same time, trigger GC and be recycled; If the pointer to the original node is not recovered after the reference to the prev node is lost.
getFirst method
```
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
```
This method is used to obtain the value of the first node.

If the first node does not exist, a NoSuchElementException exception is thrown. Otherwise, the value of the first node is returned.
getLast method
```
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
```
This method is used to obtain the value of the tail node.

If the tail node does not exist, a NoSuchElementException exception will be thrown. Otherwise, the value of the tail node will be returned.
Add (E) method

Call the LinkeLast method to add elements to the tail
```
public boolean add(E e) {
    linkLast(e);
    return true;
}
```

remove (Object o) method

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;
}

Traverse the linked list from beginning to end to find the specified Object object. If it is not found, return false. If it is found, call the unlink function to delete the corresponding node, and then return true.

The unlink function is defined as follows

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;
}

Find the front and back nodes to delete.

If the front node does not exist, the back node is the first node. Otherwise, the back pointer of the front node points to the back node, and the front pointer of the node to be deleted is set to null.

If the back node does not exist, the front node is the tail node. Otherwise, the front pointer of the back node points to the front node, and the back pointer of the node to be deleted is set to null.

remove() method
```
public E remove() {
    return removeFirst();
}
```
Very simple, call the removeFirst method to delete the first element of the two-way linked list.

remove (int index) method

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

The checkElementIndex method is used to verify whether the index is legal. It is defined as follows

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

The isElementIndex method is defined as follows

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

If the index is illegal, an IndexOutOfBoundsException exception is thrown. Otherwise, the unlink method is called to delete the specified node, and the node method is called. The node method is defined as follows

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;
    }
}

If the index is to the right, look from back to front. After finding the node, return to the node.

If the index is left, look from front to back. After finding the node, return to the node.

add (int index, E element)
```
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
```
checkPositionIndex checks whether the subscript is legal. The checkPositionIndex method is defined as follows
```
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```
If the index is illegal, an IndexOutOfBoundsException exception will be thrown.

If the index is size, the linkLast method is called to insert the element into the tail of the two-way linked list.

Otherwise, call the linkBefore method to insert the element into the specified position. The linkBefore method is defined as follows
```
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++;
}
```
This function finds the node and its front node at the original index position. These two nodes are the front and rear nodes of the node to be inserted, and then correctly handle the pointing of the front and rear pointers of each node.

get (int index) method

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Very simple, as defined above.

set (int index, E e)

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

Very simple, as defined above.

indexOf (Object o) method

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)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

Very simple, as defined above.

lastIndexOf (Object o) function

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

Very simple, as defined above.

toArray() method

public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

Create an Object array of size, copy the data of the two-way linked list into the Object array in turn, and return the Object array.

clear() method

public void clear() {
    // 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++;
}

Set the back pointer, value and front pointer of each node to null, and set the points of first and last to null. Finally, set the length of the two-way linked list to 0.

FailFast mechanism

FailFast mechanism, i.e. fast failure mechanism.

Through the core method of LinkedList above, we can see that modCount will be automatically increased in adding and deleting nodes, and modCount represents the number of modifications.

FailFast mechanism is to protect the security and correctness of data in LinkedList when reading and writing LinkedList at the same time.

The specific implementation is as follows: the next iteration function is defined as follows

public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

The checkforconfirmation function is defined as follows

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

modCount is the current modification times and expectedModCount is the expected modification times. If the two values are inconsistent, it means that the linked list has been written at the same time in the process of reading the linked list. This is not allowed. At this time, the ConcurrentModificationException exception exception will be thrown. This process can be analogous to the shared lock of a database.

FailFast mechanism test

Read thread

package cn.edu.hstc.LinkedList;

import java.util.Iterator;
import java.util.List;

/**
 * ReadObject
 */
public class ReadThread extends Thread {

    private List list;

    public ReadThread(List list) {
        this.list = list;
    }

    @Override
    public void run() {
        while (true){
            for (Iterator iterator = list.iterator(); iterator.hasNext();){
                System.out.println("ReadThread: " + iterator.next());
                try {
                    Thread.sleep(5);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

Write thread

package cn.edu.hstc.LinkedList;

import java.util.List;

/**
 * wirteThread
 */
public class WirteThread extends Thread {

    private List list;

    public WirteThread(List list) {
        this.list = list;
    }

    @Override
    public void run() {
        for (int i = 0; i < 100; i++){
            list.add(i);
            try {
                Thread.sleep(5);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Test class

package cn.edu.hstc.LinkedList;

import cn.edu.hstc.Array.WiretThread;

import java.util.LinkedList;
import java.util.List;

/**
 * test FailFast
 */
public class TestFailFast {

    public static void main(String[] args) {
        List<Object> list = new LinkedList<>();

        new ReadThread(list).start();
        new WiretThread(list).start();
    }
}

test result

loop execute : 0
loop execute : 1
loop execute : 2
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966)
	at java.util.LinkedList$ListItr.next(LinkedList.java:888)
	at cn.edu.hstc.LinkedList.ReadThread.run(ReadThread.java:21)
loop execute : 3
loop execute : 4
loop execute : 5
loop execute : 6
loop execute : 7
loop execute : 8
loop execute : 9

Keywords: Java source code set

Added by roustabout on Fri, 18 Feb 2022 10:42:03 +0200

Programming VIP

LinkedList source code interpretation (the most detailed)

LinkedList source code interpretation

Inheritance structure of LinkedList

Properties of LinkedList

LinkedList constructor

The core method of LinkedList

FailFast mechanism

Popular Keywords