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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. Add (E) method

    Call the LinkeLast method to add elements to the tail

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
  8. 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.

  9. remove() method

    public E remove() {
        return removeFirst();
    }
    

    Very simple, call the removeFirst method to delete the first element of the two-way linked list.

  10. 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.

  11. 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.

  12. get (int index) method

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

    Very simple, as defined above.

  13. 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.

  14. 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.

  15. 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.

  16. 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.

  17. 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