Based on JDK1.8 to the source code of the LinkedList set for in-depth analysis, including a variety of methods, LinkedList construction, iterator mechanism of the underlying implementation.

1 Overview of LinkedList

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

JDK1.2 when the collection class is added, the bottom is the use of two-way linked list to achieve the linear table, from the list head or tail operation data elements, can be used as a dual-end queue, can also simulate the storage of stack space.

The AbstractSequentialList abstract class directly inherits from the AbstractSequentialList abstract class, which is the unified parent of the linear table of the linked list implementation. For linear tables implemented with random access data (such as arrays), AbstractList should be inherited directly. AbstractSequentialList also inherits AbstractList.

The List interface is implemented, so you can also use the “index” method get (index) to access elements, but it’s less efficient because all get (index) actually iterates from start to finish! This index is not an array index, but a self-maintained index!

No implementation of RandomAccess signature interface, no support for fast RandomAccess.

Cloneable, Serializable signature interface, support for cloning and serialization!

In JDK1.5, the Queue interface was added, and in JDK1.6, the Deque interface was implemented directly, providing a number of additional methods (described below)!

This implementation is not synchronous. You can use: List the List = Collections. SynchronizedList (new LinkedList (…). ) to a thread-safe List!

2 API method of LinkedList

By API methods, I mean the API methods specific to LinkedList in addition to the common API methods of the List interface.

When it was created (JDK1.2), it provided a series of methods for the head and tail of a linked list:

Public void addFirst(E E) inserts the specified element at the beginning of the list. Public void addLast(E E) adds the specified element to the end of the list. Public E getFirst() returns the first element of the list. If this list is empty, a NoSuchElementException is thrown. Public E getLast() returns the last element in the list. If this list is empty, a NoSuchElementException is thrown. Public E removeFirst() removes and returns the first element of the list. If this list is empty, a NoSuchElementException is thrown. Public E removeLast() removes and returns the last element in the list. If this list is empty, a NoSuchElementException is thrown.

In JDK1.5, we added some new methods to implement the Queue interface:

Public E peek() retrieves but does not remove the header (the first element) of the list. If this list is empty, null is returned. Public E element() gets but does not remove the header (the first element) of the list. If this list is empty, a NoSuchElementException is thrown. Public E poll() gets and removes the head (first element) of the list. If this list is empty, null is returned. Public E remove() gets and removes the header (first element) of this list. If this list is empty, a NoSuchElementException is thrown. Public Boolean Offer (E E) Adds the specified element to the end of the list (the last element).

In JDK1.6, LinkedList does not implement a Queue directly. Instead, it implements a Deque interface, and provides a new set of methods for the head of the list and the end of the list:

Public Boolean offerFirst(E E) Inserts the specified element at the beginning of this list. Public Boolean offerLast(E E) Inserts the specified element at the end of this list. public E peekFirst(); Gets, but does not remove, the head (first element) of this list. If this list is empty, null is returned. public E peekLast(); Gets, but does not remove, the last element in this list. If this list is empty, null is returned. Public E pollFrist() gets and removes the head (first element) of this list. If this list is empty, null is returned. Public E pollLast() gets and removes the last element in the list. If this list is empty, null is returned.

Conclusion: As you can see, different versions of the JDK provide different methods to achieve the same functionality. For compatibility, we have not removed the old methods, but JDK1.6 provides new methods, more powerful than the methods in JDK1.2 and JDK1.5. We recommend using the new API methods in JDK1.6.

  1. JDK 1.2, JDK1.5: If the number of elements in the list is null, NoSuchElementException may be thrown when using a method.
  2. If the number of elements in a linked list is null, the method will return null without exception.

3 Source code analysis of LinkedList

As shown in the figure above, LinkedList is an implementation of the linear list chain structure. (Vector and ArrayLsit are both implementations of the linear list sequence structure.) the underlying LinkedList uses a bidirectional LinkedList structure, with a head and a tail node reference kept outside. A bidirectional list means that we can start at the beginning and go forward, or we can start at the tail and go backwards, and we can do things for the head and tail.

Because you design to data structures, you need some knowledge of data structures. This article will not explain the knowledge of data structure, mainly explain the source code, on the implementation of linear table sequence structure and chain structure and the difference in myData structures and algorithmsThere are special related articles in detail:Java linear table data structure in detail and implementation cases. In fact, linear tables are pretty easy to understand!

3.1 Main class attributes

    // The number of elements in the LinkedList
    transient int size = 0;
    // Link list header node
    transient Node<E> first;
    // End node of the list
    transient Node<E> last;
Copy the code

The addition of the head and tail nodes allows the LinkedList to be added from the first or the last node, that is, as a first-in, first-out (FIFO) queue or as a LIFO (last in, first out) stack.

3.2 the Node Node

Unlike ArrayList, which has natural sequential storage as an internal array, a LinkedList implementation needs to keep track of an element’s predecessor and successor, so LinkedList uses an object Node as an element Node.

As the core of LinkedList, Node is the data structure that actually stores the elements in the LinkedList. The inner Node class is the actual Node object, or the place where the actual elements are stored, with one Node per Node.

In JDK1.6 and before, nodes are called entries.

private static class Node<E> {
    /** * Data field, actual stored elements, node values */
    E item;
    /** * after, stores a reference to the next node */
    Node<E> next;
    /** * precursor, which stores references to the previous node */
    Node<E> prev;

    /** * Node@paramPrev A precursor, that is, a reference * to the previous node@paramElement Specifies the value of the stored element *@paramNext The application of the next node */
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

3.3 the constructor

LinkedList has two constructors, and both are simple.

3.3.1 LinkedList ()

Construct an empty list with no implementation in it, just pointing to itself (null) with the header node’s first and last elements.

public LinkedList(a) {}Copy the code

3.3.2 rainfall distribution on 10-12 LinkedList (Collection <? extends E> c)

Constructs a list of the elements in the specified collection in the order returned by the iterators of their collection.

public LinkedList(Collection<? extends E> c) {
    // First call to construct it with no arguments, creating an empty list
    this(a);// Call the addAll method
    addAll(c);
}
Copy the code

3.4 Adding Methods

3.4.1 Adding methods to the Tail

public boolean add(E e)

Adds the specified element to the end of the list.

Source code parsing:

public boolean add(E e) {
    // Call the linkLast method internally
    linkLast(e);
    return true;
}

/** * link elements to the end of the list *@paramE The added element */
void linkLast(E e) {
    // Create a node reference l, pointing to the original tail node
    final Node<E> l = last;
    // Create a new node as the new tail node, whose prev is the current tail node, e is the stored data E, and next is null
    final Node<E> newNode = new Node<>(l, e, null);
    // The new node to be inserted is the new tail node
    last = newNode;
    // Check whether the original tail node is null, that is, whether the original set has node data
    if (l == null)
        // If the original tail node is null and the original set has no node data, then the new node is also the first node
        first = newNode;
    else
        // If the original tail node is not null, that is, the original set has node data, then the next reference to the original tail node refers to the new tail node
        l.next = newNode;
    // The number of nodes increases by 1
    size++;
    // The number of structural changes increases by 1
    modCount++;
}
Copy the code

All the other tail additions work the same way:

public void addLast(E e)

public void addLast(E e) {
    linkLast(e);
}
Copy the code

public boolean offerLast(E e)

public boolean offerLast(E e) {
    addLast(e);
    return true;
}
Copy the code

public boolean offer(E e)

public boolean offer(E e) {
    return add(e);
}
Copy the code

3.4.2 Methods to add to the header

public void addFirst(E e)

Inserts the specified element at the beginning of the list.

public void addFirst(E e) {
    // Call the linkFirst method internally
    linkFirst(e);
}

/** * Link elements to the list header *@paramE The added element */
private void linkFirst(E e) {
    // Create a node reference l, pointing to the original head node
    final Node<E> f = first;
    // Create a new node as the new head node, whose prev is null, e is the stored data e, and next node is the current head node
    final Node<E> newNode = new Node<>(null, e, f);
    // The new node to be inserted is the new head node
    first = newNode;
    // Check whether the original header is null, that is, whether the original set has node data
    if (f == null)
        // If the original head node is null and the original set has no node data, then the new node is also the tail node
        last = newNode;
    else
        // If the original head node is not null, that is, the original set has node data, then the prev reference of the original head node is pointed to the new head node
        f.prev = newNode;
    // The number of nodes increases by 1
    size++;
    // The number of structural changes increases by 1
    modCount++;
}
Copy the code

You can add it to the tail node in a similar way.

All the other tail additions work the same way:

public boolean offerFirst(E e)

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
Copy the code

3.4.3 Specify a location to add

Public void add(int index,E element) index – index of the element to be inserted

To add an element at the specified location, the additional step is to find the element corresponding to the original index, and then change the reference relationship again. The element of the original index is linked after the new element.

Source code parsing:

add(int index,E element)

public void add(int index, E element) {
    // Check whether the index is between [0-size]
    checkPositionIndex(index);
    // Determine whether index is equal to size
    if (index == size)
        // If the index is equal to size, it is actually added to the end of the list. Call the linkLast(element) method
        linkLast(element);
    else
        // If not, call the linkBefore method
        linkBefore(element, node(index));
}

/** * Check the index method *@paramThe index index * /
private void checkPositionIndex(int index) {
    if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/** * Whether the index is greater than or equal to 0 and smaller than or equal to size *@paramThe index index *@returnIf yes, return true; If no, return false */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

Copy the code

The linkBefore method takes two parameters, one for the value of the inserted node and one for the node found at the specified index, so we first need to call the node(index) method to find the node corresponding to the index.

/** * Obtain the Node * at the corresponding index@paramThe index index *@returnThe corresponding node */
Node<E> node(int index) {
    /* Determine whether the index is less than half the number of nodes. Size >> 1 is a bit operation
    if (index < (size >> 1)) {
        /* If the index is less than half the number of nodes, then look for nodes at the corresponding index */ from the list header
        // Get the reference x of the header node
        Node<E> x = first;
        // Loop to obtain the next node of x, and obtain I ++ once. When I =index, the element at the corresponding index is found
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        /* If the index is greater than half the number of nodes, then start at the end of the list to find nodes at the corresponding index */
        // Get the reference x of the tail node
        Node<E> x = last;
        // Select * from 'prev' where 'I' = 'index' where 'I' = 'index' where 'I' = 'index'
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}Copy the code

From the implementation of node node search, it can be seen that the search of the index here starts from the beginning or the end of the loop search, the time complexity is O(n), so the efficiency is relatively low compared with the search time complexity of ArrayLsit O(1).

Next is the linkBefore method:

/** * insert an element before the specified node, where the node object is not null *@paramE the value of the element to store *@paramSucc Specifies a node */
void linkBefore(E e, Node<E> succ) {
    // Get the node before the specified node succ
    final Node<E> pred = succ.prev;
    // Create a new node with the header pointing to the node in front of the succ and the tail pointing to the succ node
    final Node<E> newNode = new Node<>(pred, e, succ);
    // Make the succ node header point to the new node
    succ.prev = newNode;
    // If succ is null, succ is the first node, and the new node becomes the first node
    if (pred == null)
        first = newNode;
    else
        // If there is a previous node, make the next node of the previous node point to the point of the new node
        pred.next = newNode;
    // The number of nodes increases by 1
    size++;
    // The number of structural changes increases by 1
    modCount++;
}

Copy the code

3.5 Removal Methods

3.5.1 Method for Removing a Head Node

E remove()

Gets and removes the head (first element) of this list. If the list is NULL, a NoSuchElementException is thrown.

/** * get and remove the header (first element) of this list. If the list is NULL, a NoSuchElementException is thrown. * *@returnThe value of the removed element */
public E remove(a) {
    // Call the removeFirst method internally directly
    return removeFirst();
}

/** * get and remove the header (first element) of this list. If the list is NULL, a NoSuchElementException is thrown. * *@returnThe value of the removed element */
public E removeFirst(a) {
    // Get a reference to the header node
    final Node<E> f = first;
    // If the header is null, NoSuchElementException is thrown, indicating that the collection element has no elements
    if (f == null)
        throw new NoSuchElementException();
    // If the header node is not null, the unlinkFirst method is called
    return unlinkFirst(f);
}

/** * get and remove the header (first element) of this list. * *@paramF head node *@returnThe value of the head node */
private E unlinkFirst(Node<E> f) {
    // Get the value of this node (header node)
    final E element = f.item;
    // Get the next node from the head node
    final LinkedLisNode<E> next = f.next;
    // Set the value of the header node to NULL
    f.item = null;
    // Set the next reference value of the header node to NULL
    f.next = null;
    // Make the head node reference point to the next node
    first = next;
    // If the next node is null, there is only one element, then the collection is empty
    if (next == null)
        // Then the reference to the tail node is set to null
        last = null;
    else
        // The next node is not null, that is, there is more than one element, the next node is the head node, and the prev reference to the next node is set to null
        next.prev = null;
    // The number of nodes decreases by 1
    size--;
    // The number of structural changes increases by 1
    modCount++;
    // Return the value of the original head node. There is no reference to the original head node, and the original head node is cleaned up by GC
    return element;
}

Copy the code

All other methods of removing a head node work the same way:

E removeFirst()

Gets and removes the head (first element) of this list. If the list is NULL, a NoSuchElementException is thrown.

public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
Copy the code

E poll()

Gets and removes the head (first element) of this list. If the list is NULL, null is returned.

public E poll(a) {
    final Node<E> f = first;
    return (f == null)?null : unlinkFirst(f);
}
Copy the code

E pollFrist()

Gets and removes the head (first element) of this list. If the list is NULL, null is returned.

public E pollFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : unlinkFirst(f);
}
Copy the code

3.5.2 Method for Removing a Tail Node

public E removeLast()

Gets and removes the end (last element) of this list. If the list is NULL, a NoSuchElementException is thrown.

/** * get and remove the last element of the list. If the list is NULL, a NoSuchElementException is thrown. * *@returnThe value of the removed element */
public E removeLast(a) {
    // Get a reference to the tail node
    final Node<E> l = last;
    // If the tail node is null, NoSuchElementException is thrown, indicating that the collection element has no elements
    if (l == null)
        throw new NoSuchElementException();
    // If the tail node is not null, call the unlinkFirst method
    return unlinkLast(l);
}

/** * get and remove the last element of the list. * *@returnThe value of the removed element */
private E unlinkLast(Node<E> l) {
    // Get the value of this node (tail node)
    final E element = l.item;
    // Get the last node of the tail node
    final Node<E> prev = l.prev;
    // Set the value of the last node to NULL
    l.item = null;
    // Set the reference value of the next node to null
    l.prev = null;
    // Make the last node reference to the last node
    last = prev;
    // If the previous node is null, there is only one element, then the collection is empty
    if (prev == null)
        // Then set the header reference to null
        first = null;
    else
        // If the last node is not null, that is, if there is more than one element, the last node will be the last node and the next reference to the last node will be null
        prev.next = null;
    // The number of nodes decreases by 1
    size--;
    // The number of structural changes increases by 1
    modCount++;
    // Return the value of the original tail node. There is no reference to the original tail node, and the original tail node is cleaned up by GC
    return element;
}
Copy the code

All other methods of removing a tail node work the same way:

public E pollLast()

Gets and removes the last element of the list; If this list is empty, null is returned.

public E pollLast(a) {
    final Node<E> l = last;
    return (l == null)?null : unlinkLast(l);
}
Copy the code

3.5.2 Removing a Specified Location

E remove(int index)

Removes the element at the specified position in this list. Returns the element removed from the list.

Just like the principle of deleting the head and tail nodes, one step more is to find the element at the corresponding index, and then change the reference of the front and back nodes.

/** * remove the element at the specified position in the list, and the following element at the index is linked at the deleted position, returning the deleted element from the list. * *@param index
 * @return* /
public E remove(int index) {
    / / check index, beyond the scope of the index > = 0 && index < size, will throw IndexOutOfBoundsException
    [0,size]; [0,size];
    checkElementIndex(index);
    // Call the unlink method, passing in the node at the specified index
    return unlink(node(index));
}

/** * Unlink non-empty node x **@paramThe node * at the specified index found by x@returnThe value of the deleted node */
E unlink(Node<E> x) {
    // Get the value of this object
    final E element = x.item;
    // Create a node reference next, pointing to the next node of this node
    final Node<E> next = x.next;
    // Create a node reference to prev, pointing to the previous node of this node
    final Node<E> prev = x.prev;
    // Check whether the previous node exists on this node
    if (prev == null) {
        // If no previous node exists, then this node is the first node, then let the first node reference to the next node of this node
        first = next;
    } else {
        // If a previous node exists, the reference to the next node of the previous node points to the next node of that node
        prev.next = next;
        // The reference to the last node of this node points to null
        x.prev = null;
    }
    // Check whether there is a next node in this node
    if (next == null) {
        // If there is no next node, this node is the last node. Then the tail node reference points to the last node of that node
        last = prev;
    } else {
        // If there is a next node, the previous node reference to the next node refers to the previous node of the next node
        next.prev = prev;
        // The reference to the next node of this node points to null
        x.next = null;
    }

    // The value of this object is left blank. There is no reference to the node object and the object will be collected by the garbage collector
    x.item = null;
    // The number of nodes decreases by 1
    size--;
    // The number of structural changes increases by 1
    modCount++;
    // Return the value of this object
    return element;
}
Copy the code

3.6 Obtaining Methods

3.6.1 Methods for Obtaining the Head Node

public E getFirst()

Returns the first element of this list. If this list is empty, a NoSuchElementException is thrown.

public E getFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
Copy the code

public E peek()

Gets, but does not remove, the head (first element) of this list. If this list is empty, null is returned.

public E peek(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
}
Copy the code

public E element()

Gets, but does not remove, the head (first element) of this list. If this list is empty, a NoSuchElementException is thrown.

public E element(a) {
    return getFirst();
}
Copy the code

public E peekFirst();

Gets, but does not remove, the first element of this list; If this list is empty, null is returned.

public E peekFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
 }
Copy the code

3.6.2 Methods for Obtaining the Last Node

public E getLast()

Returns the last element of this list. If this list is empty, a NoSuchElementException is thrown.

public E getLast(a) {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
Copy the code

public E peekLast()

Gets, but does not remove, the last element of this list; If this list is empty, null is returned.

public E peekLast(a) {
    final Node<E> l = last;
    return (l == null)?null : l.item;
}
Copy the code

3.6.3 Specify the location

public E get(int index)

Returns the element at the specified location in this list.

    /** * Returns the element in this list at the specified position. *@paramIndex Specifies the index *@returnThe value of the element at that position */
    public E get(int index) {
        / / check index, beyond the scope: the index > = 0 && index < size, that is [0, size), will throw IndexOutOfBoundsException
        checkElementIndex(index);
        // Return the value of the found node
        return node(index).item;
    }
Copy the code

You can see that the node method called internally looks up the elements at the specified index in order, so the lookup method is not very efficient.

3.7 the contains and indexOf

public boolean contains(Object o)

Returns true if the list contains the specified elements. The indexOf(Object O) method determines whether the list contains Object O by determining whether the value returned by the indexOf(Object o) method is -1.

public int indexOf(Object o)

Returns the index of the first occurrence of the specified element in this list, or -1 if the list does not contain the element. The equals method is used internally to determine whether two elements are equal. So in general, if the data being stored is an object, then you need to override equals.

/** * Return true if the list contains the specified elements. * *@paramO compares elements *@returnTrue Exists false Does not exist */
public boolean contains(Object o) {
    // Call the indexOf method internally
    returnindexOf(o) ! = -1;
}

/** * Returns the index of the first occurrence of the specified element in this list, or -1 if the list does not contain the element. * *@paramO searches for the element *@returnThe index that appears. -1 indicates that */ does not exist
public int indexOf(Object o) {
    int index = 0;
    // Iterates from front to back to find the list, returning "index of the node whose value is object (o)" does not exist
    if (o == null) {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (x.item == null)
                returnindex; index++; }}else {
        for(Node<E> x = first; x ! =null; x = x.next) {
            // We can see that LinkedList is compared to equals ()
            if (o.equals(x.item))
                returnindex; index++; }}return -1;
}
Copy the code

3.8 clone method

Like most collection classes, the clone method of LinkedList does not clone the data; it is a shallow clone.

/** * Shallow clone (elements will not be cloned) *@returnA copy */
public Object clone(a) {
    // Call the clone method of the superclass (Object)
    LinkedList<E> clone = superClone();

    // Clear the internal variable reference values of the cloned object
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // Re-assign
    // Clone the Node from the original Node, but change the value of the Item in the Node from the original Node, and change the value of the Item in the Node.
    // However, if the storage is direct, it does not matter!
    for(Node<E> x = first; x ! =null; x = x.next)
        clone.add(x.item);
    // Return the cloned object
    return clone;
}

@SuppressWarnings("unchecked")
private LinkedList<E> superClone(a) {
    try {
        // The clone method of the Object
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw newInternalError(e); }}Copy the code

3.9 clear method

To clear the list, it is not simply to empty the external references, but to loop through the list, unassociating all the nodes one by one.

/** * Clear the list */
public void clear(a) {
    // Manually clear all the references between the list nodes to help GC
    for(LinkedList.Node<E> x = first; x ! =null;) { LinkedList.Node<E> next = x.next; x.item =null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // Finally, empty the external header/tail reference
    first = last = null;
    / / the size s
    size = 0;
    // The number of structural changes increases by 1
    modCount++;
}
Copy the code

Iterator mechanism

All lists have iterators and ListIterator iterators, and their methods are the same, but the implementation is implemented by these classes themselves!

Iterator and ListIterator Iterator methods and the implementation of ArrayList iterators, including fast and safe failure and the “concurrent modification” exception mechanism, are covered in this article:Java ArrayList collection source depth analysis and application introductionIn the explanation, the following encounter the same principle of time will not be repeated!

Let’s take a look at the iterator implementation for the LinkedList set. Intuition tells us that the two sets are different!

4.1 Iterator

List iterators all provide the same methods, but with different implementations. Here is a forward traversal of the LinkedList Iterator – delete use case.

The forward iterator is from the beginning to the end, and the reverse iterator is from the end to the end, but the reverse iterator is a ListIterator function, we’ll see later!

@Test
public void test2(a) {
    LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(1.2.3));
    System.out.println("Before removing an element:" + linkedList);
    // Get an Iterator instance
    Iterator<Integer> iterator = linkedList.iterator();
    // Loop through the data
    while (iterator.hasNext()) {
        // Get the next element
        Integer next = iterator.next();
        System.out.println(next);
        // Remove the next element
        iterator.remove();
    }
    System.out.println("After removing an element:" + linkedList);
}

Copy the code

4.1.1 Introduction of Iterator source code

Let’s look at the implementation of Iterator in LinkedList!

First we follow up with iterator(), which is used to get iterators, but we did not find the iterator() method in the LinkedList implementation class. At this point we know that the method that must be called is defined in the parent class and that the subclass did not override the method.

AbstractSequentialList; iterator(); iterator(); iterator();

/** * Iterator () method from parent AbstractSequentialList *@returnReturns an iterator instance */
public Iterator<E> iterator(a) {
    // Return a listIterator instance
    return listIterator();
}

Copy the code

We can see that the called iterator() method actually returns an instance of listIterator(the called listIterator() method), but this is true because listIterator inherits from iterator. Subclass objects returned in Java can be received using the parent class!

The Parent class of LinkedList, AbstractSequentialList, does not override the listIterator() method either. This method appears in a parent class of AbstractSequentialList, the AbstractList class, which is surprisingly complex, but let’s take a look at the listIterator() implementation of AbstractList class:

/** * listIterator() method in AbstractList parent class of AbstractSequentialList *@returnReturns a list iterator */
public ListIterator<E> listIterator(a) {
    // Calls the listIterator(0) method internally, taking an argument of 0
    return listIterator(0);
}

Copy the code

Another listIterator(0) method with a parameter is called internally, so where is this method? We see that LinkedList has overridden this method with arguments, so this time it must be calling its own overridden method. Take a look at its implementation:

/** * LinkedList overwrites methods with arguments *@paramIndex actually represents the index of the first element returned from the list iterator, the index * of the element from which the iteration began@returnA list iterator instance */
public ListIterator<E> listIterator(int index) {
    /* Check whether the index is out of bounds */
    checkPositionIndex(index);
    Return an instance of ListItr, which is an Iterator object */
    return new ListItr(index);
}

/** * Check whether the index is out of bounds *@param index
 */
private void checkPositionIndex(int index) {
    if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/** * Check whether the index is greater than or equal to 0 and less than or equal to size *@paramThe index index *@returnTrue - Yes false- no */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

Copy the code

After doing the index range check, we finally see the returned instance, a ListItr object. Then we find an implementation of the Inner ListItr class in the LinkedList class. Let’s take a look at the more common methods:

/** * The inner class ListItr implements the ListIterator interface, and thus has more methods than those that have the Iterator interface. * For example add(), set(), let's take a look at the forward Iterator method */
private class ListItr implements ListIterator<E> {
    /** * The last node returned */
    private Node<E> lastReturned;
    /** * Next node to be returned */
    private Node<E> next;
    /** * Index of the next node to be returned */
    private int nextIndex;
    /** * expectedModCount = modCount, used to detect concurrent modifications */
    private int expectedModCount = modCount;

    /** * constructor *@paramIndex represents the index of the first element returned from the list iterator, that is, the index */ of the element from which the iteration began
    ListItr(int index) {
        // Get the next node to be returned. If index == size then the next node to be returned is null(because indexes are counted from 0);
        // Otherwise, use the node(index) method to find the next node to be returned
        next = (index == size) ? null : node(index);
        // Get the index of the next node to be returned, and make it equal to index
        nextIndex = index;
    }

    /** * Whether there is a next node *@returnTrue - Yes false- No */
    public boolean hasNext(a) {
        // Return true if the index of the next node to be returned is less than size, indicating that there are still nodes that have not been iterated
        // Otherwise return false, indicating that the iteration is complete
        return nextIndex < size;
    }

    /** * Get the next node *@returnThe value of the next node */
    public E next(a) {
        /* Detect "concurrent changes "*/
        checkForComodification();
        /* Check whether there are still nodes that can be obtained */
        if(! hasNext())throw new NoSuchElementException();
        // Set the last node returned to point to the next node
        lastReturned = next;
        // The next node points to the next node
        next = next.next;
        // The index of the next node to be returned increases by 1
        nextIndex++;
        // Return the value of the last node returned
        return lastReturned.item;
    }

    /** * Remove the next node */
    public void remove(a) {
        /* Detect "concurrent changes "*/
        checkForComodification();
        LastReturned refers to null when you create an iterator and use this method directly. LastReturned cannot be used before next() and cannot be used continuously after remove()
        if (lastReturned == null)
            throw new IllegalStateException();
        /* Get the next node to the last node returned */
        Node<E> lastNext = lastReturned.next;
        /* Remove the reference between the lastReturned node and the list, and subsequent nodes link to the original node */
        unlink(lastReturned);
        /* if the next node is equal to the last node returned */
        if (next == lastReturned)
            // Then the reference to the next node refers to the node next to the last node returned. In fact, this is used for reverse iteration traversal, not positive iteration traversal
            next = lastNext;
        else
            // Otherwise, the index of the next node to be returned is decrement by 1. This is actually (next) for the positive order iterated traversal, which is not used for the reverse order traversal
            nextIndex--;
        // Set the reference to the last returned node to null
        lastReturned = null;
        / / due to call the external class unlink method, thus modCount certainly since increased by 1, in order to ensure that do not appear "ConcurrentModificationException" exception, finally will expectedModCount also from 1-6
        expectedModCount++;
    }

    / * * * testing "concurrent modification", if there is a throw ConcurrentModificationException * /
    final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

4.1.2 Parsing an Iterator instance

The following uses the source code and the above use case to show how forward Iterator travers-deletion in the LinkedList Iterator works.

  1. The preparatory work
    1. We first create a linked list whose element nodes are 1 — 2 — 3.
    2. Then we create an Iterator instance, which is actually a ListItr object that returns, which directly implements the ListIterator Iterator, but because the ListIterator Iterator inherits from the Iterator Iterator, the return is reasonable due to the upward transition of Java. It’s just that we can only use methods in an Iterator.
    3. In the constructor of the ListItr object, next=1, nextIndex=0, lastReturned=null, next=1, lastReturned=null, next=1, lastReturned=null, ExpectedModCount is initialized equal to modCount.
  2. Then start the first cycle
    1. The first is the hasNext() method. Obviously nextIndex=0
    2. Next comes the next() method, which gets the next element, and begins with a series of “concurrent change” checks, which are covered in detail in the ArrayList section (quick failure or security failure) and won’t go into much detail here. Obviously this is a passable area. Then lastReturned = next=1 node, next= next. Next =2 nodes, nextIndex++ becomes 1. Then return the value of lastReturned, which returns 1.
    3. NextIndex =1
    4. Now, let’s go back to the case, and then we have the remove method, and first we have a series of concurrent modification checks that we can pass. LastReturned is not null because lastReturned=1 node in the next method above. Next= 2 nodes, and then call unlink to remove the relationship between lastReturned and the list. At this point, the list node becomes 2 — 3. And then we’re going to see if next is equal to lastReturned, and just to show you, if we’re going backwards, then we’re going to return true, and if we’re going forwards we’re going to return false, so we’re obviously going forwards, so we’re going to return false, and then we’re going to change nextIndex to 0 again, Finally expectedModCount++, because will unlink methods modCount since 1, in order to prevent abnormal ConcurrentModificationException, therefore expectedModCount here have to add 1.
    5. At the end of the first loop, we see that next returns 1, the value of node 1 at index 0, remove removes node 1 from the list, and finally nextIndex=0, next=2, lastReturned=null, ExpectedModCount is also equal to modCount.
  3. Then start the second cycle
    1. The first is the hasNext() method. Note that because of the unlink operation in the last round of the loop, the size is subtracted by 1, where size=2, but obviously nextIndex=0
    2. Next comes the next() method, which gets the next element, and begins with a series of “concurrent modification” checks, which obviously pass. Then lastReturned = next=2 nodes, next= next. Next =3 nodes, nextIndex++ becomes 1. Then return the value of lastReturned, which returns 2.
    3. Next comes the remove method, which begins with a series of “concurrent modification” checks that can be passed. Then determine if lastReturned is equal to null, which is not null because lastReturned=2 nodes in the next method above. Next= 3, and then call unlink to unlink the 2 nodes pointed to by lastReturned. Then the list becomes 3. Then judge if next is equal to lastReturned, return false, then change nextIndex– then to 0 again, and finally expectedModCount++, where expectedModCount and modCount are always equal.
    4. NextIndex =0, next=3, lastReturned=null, nextIndex=0, next=3, lastReturned=null, ExpectedModCount is also equal to modCount.
  4. Then start the third cycle
    1. The first is the hasNext() method, where size=1, but obviously nextIndex=0
    2. Next comes the next() method, which gets the next element, and begins with a series of “concurrent modification” checks, which obviously pass. Then lastReturned = next=3 nodes, next= next. Next =null, nextIndex++ becomes 1. Then return the value of lastReturned, which returns 3.
    3. Next comes the remove method, which begins with a series of “concurrent modification” checks that can be passed. Then determine if lastReturned is equal to null, which is not null because lastReturned=3 nodes in the next method above. Next= null, and then call unlink to remove the relationship between lastReturned and the list. The list has no nodes left. Then judge if next is equal to lastReturned, return false, then change nextIndex– then to 0 again, and finally expectedModCount++, where expectedModCount and modCount are always equal.
    4. NextIndex =0, next=null, lastReturned=null, next=null, lastReturned=null, next=null, lastReturned=null, ExpectedModCount is also equal to modCount.
  5. Then start the fourth cycle
    1. NextIndex =0

Conclusion: The LinkedList Iterator is the same as the ArrayList Iterator is the same as the LinkedList Iterator is the same as the ArrayList Iterator is the same as the LinkedList Iterator. The loop condition is always nextIndex=0 and the size of the comparison, delete a size to reduce 1, when the size is equal to 0, the end of the natural loop, traversal – delete operation end, can see its principle is relatively simple!

4.2 ListIterator iterator

ListIterator inherits Iterator and is even more powerful! Can achieve reverse traversal, add, set and other operations. Here is a reverse traversal of the LinkedList ListIterator iterator – remove use case.

/** * ListIterator iterator iterator + delete case */
@Test
public void test3(a) {
    LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(1.2.3));
    System.out.println("Before removing an element:" + linkedList);
    // Get an iterator instance of ListIterator
    ListIterator<Integer> iterator = linkedList.listIterator(3);
    // Iterate backwards to process the data
    while (iterator.hasPrevious()) {
        // Get the next element
        Integer next = iterator.previous();
        System.out.println(next);
        // Remove the next element
        iterator.remove();
    }
    System.out.println("After removing an element:" + linkedList);
}

Copy the code

4.2.1 ListIterator source code introduction

Let’s look at the implementation of the ListIterator iterator in the LinkedList!

First we follow up with listIterator(), which is used to get iterators, but we did not find the listIterator() method in the LinkedList implementation class, so we know that the method that must be called is defined in the superclass and that the subclass does not override the method.

In the parent class AbstractSequentialList of LinkedList, we can’t find the listIterator() method either. We can find the source code of listIterator() in the parent class AbstractSequentialList:

public ListIterator<E> listIterator(a) {
    return listIterator(0);
}
Copy the code

The iterator() method also calls this method indirectly.

In fact, both the LinkedList iterator() and listIterator() return a ListItr inner class object. The difference is that the preceding static type is different.

Iterator iterator=new ListItr(0);   
ListIterator listIterator=new ListItr(0);
Copy the code

So the above iterator actually has methods that were originally part of the listIterator?

In our opinion, this is true, but according to the Java method call rules, only the static type of the left iterator can be called, although the actual type of the iterator is ListItr, the static type is iterator, so it can only be called. The following listIterator can call all methods because it is of type listIterator!

Method calls are at the JVM level. For those who don’t know the rules of Java method calls, check out this article:Java JVM runtime stack structure and method invocation detailed.

Since the ListIterator iterator adds many methods, I’ll show the source code for the key methods in the backward travers-delete example above:

/** * The inner class ListItr implements the ListIterator interface, and thus has more methods than those that have the Iterator interface. * For example add(), set(), let's take a look at the forward Iterator method */
private class ListItr implements ListIterator<E> {
    /** * The last node returned */
    private Node<E> lastReturned;
    /** * Next node to be returned */
    private Node<E> next;
    /** * Index of the next node to be returned */
    private int nextIndex;
    /** * expectedModCount = modCount, used to detect concurrent modifications */
    private int expectedModCount = modCount;

    /** * constructor *@paramIndex represents the index of the first element returned from the list iterator, that is, the index */ of the element from which the iteration began
    ListItr(int index) {
        // Get the next node to be returned. If index == size then the next node to be returned is null(because indexes are counted from 0);
        // Otherwise, use the node(index) method to find the next node to be returned
        next = (index == size) ? null : node(index);
        // Get the index of the next node to be returned, and make it equal to index
        nextIndex = index;
    }

    /** * Whether there is a next node *@returnTrue - Yes false- No */
    public boolean hasNext(a) {
        // Return true if the index of the next node to be returned is less than size, indicating that there are still nodes that have not been iterated
        // Otherwise return false, indicating that the iteration is complete
        return nextIndex < size;
    }

    /** * Get the next node *@returnThe value of the next node */
    public E next(a) {
        /* Detect "concurrent changes "*/
        checkForComodification();
        /* Check whether there are still nodes that can be obtained */
        if(! hasNext())throw new NoSuchElementException();
        // Set the last node returned to point to the next node
        lastReturned = next;
        // The next node points to the next node
        next = next.next;
        // The index of the next node to be returned increases by 1
        nextIndex++;
        // Return the value of the last node returned
        return lastReturned.item;
    }

    /** * Remove the next node */
    public void remove(a) {
        /* Detect "concurrent changes "*/
        checkForComodification();
        LastReturned refers to null when you create an iterator and use this method directly. LastReturned cannot be used before next() and cannot be used continuously after remove()
        if (lastReturned == null)
            throw new IllegalStateException();
        /* Get the next node to the last node returned */
        Node<E> lastNext = lastReturned.next;
        /* Remove the reference between the lastReturned node and the list, and subsequent nodes link to the original node */
        unlink(lastReturned);
        /* if the next node is equal to the last node returned */
        if (next == lastReturned)
            // Then the reference to the next node refers to the node next to the last node returned. In fact, this is used for reverse iteration traversal, not positive iteration traversal
            next = lastNext;
        else
            // Otherwise, the index of the next node to be returned is decrement by 1. This is actually (next) for the positive order iterated traversal, which is not used for the reverse order traversal
            nextIndex--;
        // Set the reference to the last returned node to null
        lastReturned = null;
        / / due to call the external class unlink method, thus modCount certainly since increased by 1, in order to ensure that do not appear "ConcurrentModificationException" exception, finally will expectedModCount also from 1-6
        expectedModCount++;
    }

    / * * * testing "concurrent modification", if there is a throw ConcurrentModificationException * /
    final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

4.2.2 ListIterator instance resolution

Here’s a look at the source code and the above use case to show how back-traversal of ListItertor iterators in LinkedList works.

  1. The preparatory work
    1. We first create a linked list whose element nodes are 1 — 2 — 3.
    2. Then create an instance of the ListItertor iterator, which is actually the returned ListItr object. In the constructor of the ListItr object, since index and size are equal to 3, so next=null, nextIndex=3, When lastReturned= NULL, expectedModCount is initialized equal to modCount. Then start the loop, starting with the hasPrevious () method. Obviously nextIndex=3>0 is true, so enter the body of the loop.
  2. First cycle
    1. Next comes the previous() method, which gets the last element (because it’s in reverse order) and begins with a series of “concurrent changes” checks, which obviously pass here. Then since next equals null, lastReturned = next = last node, where the last node is 3. NextIndex — then it becomes 2. Then return the value of lastReturned, which returns 3.
    2. If there is no remove, then there is only previous() in the loop, then we go to the second loop, nextIndex=2>0, and then continue with previous(), this time because next is not equal to NULll, Set lastReturned = next = next. Prev, where the next. Prev node is 2. NextIndex — then it becomes 1. Then return the value of lastReturned, which returns 2. Then the loop continues until the 1 node is iterated, at which point nextIndex=0, does not satisfy the condition of greater than 0, then the loop iterated through the end! Therefore, the principle of reverse loop traversal is still very simple, it maintains a nextIndex traversal on a subtraction, when equal to 0, the collection of reverse iteration traversal is completed!
    3. Now, let’s go back to the case, and then we have the remove method, and first we have a series of concurrent modification checks that we can pass. LastReturned is not null because lastReturned=3 nodes in the previous method. Next= null, and then call unlink to remove the relationship between lastReturned and the list. At this point, the list node becomes 1 — 2. Next is lastReturned, and just to show you, if we’re going backwards, we’re going to return true, if we’re going forwards we’re going to return false, so we’re going backwards, so we’re going to return true, and then next = lastNext=null, Then lastReturned = null, and finally expectedModCount++, because will unlink methods modCount since 1, in order to prevent abnormal ConcurrentModificationException, So here the expectedModCount is also incremented by 1.
    4. At the end of the loop, we see that next returns 3, which is the value of 3 nodes at index 2. Remove removes 3 nodes from the list, and finally nextIndex=2, next=null, lastReturned=null, ExpectedModCount is also equal to modCount.
  3. Then start the second cycle
    1. The first is the hasNext() method, which indicates that nextIndex=2>0 is still true, so it enters the body of the loop.
    2. Next comes the previous() method, which gets the last element (because it’s in reverse order) and begins with a series of “concurrent changes” checks, which obviously pass here. Then, since next equals null, lastReturned = next = last node, which is 2 since last node 3 has been deleted. NextIndex — then it becomes 1. Then return the value of lastReturned, which returns 2.
    3. Next comes the remove method, which begins with a series of “concurrent modification” checks that can be passed. LastReturned is not null because lastReturned=2 nodes in the previous method. Next= null, and then call unlink to remove the relationship between lastReturned and the list node. At this point the list node becomes 1. Next= lastNext=null, then lastReturned =null, and finally expectedModCount++, Make expectedModCount and modCount always equal.
    4. NextIndex =1, next=null, lastReturned=null, next=null, lastReturned=null, next=null, lastReturned=null, ExpectedModCount is also equal to modCount.
  4. Then start the third cycle
    1. The first is the hasNext() method, which indicates that nextIndex=1>0 is still true, so it enters the body of the loop.
    2. Next comes the previous() method, which gets the last element (because it’s in reverse order) and begins with a series of “concurrent changes” checks, which obviously pass here. Then, since next equals null, lastReturned = next = last node, which is 1 since last node 2 has been deleted. NextIndex — then it becomes 0. Then return the value of lastReturned, which returns 1.
    3. Next comes the remove method, which begins with a series of “concurrent modification” checks that can be passed. Then determine if lastReturned is equal to null, which is not null because lastReturned=1 node in the previous method. Next= null, and then call unlink to remove the relationship between lastReturned and the list. At this point the list has no nodes. Next= lastNext=null, then lastReturned =null, and finally expectedModCount++, Make expectedModCount and modCount always equal.
    4. NextIndex =0, next=null, lastReturned=null, next=null, lastReturned=null, next=null, lastReturned=null ExpectedModCount is also equal to modCount.
  5. Then start the fourth cycle
    1. NextIndex =0; nextIndex=0; nextIndex=0;

Conclusion: As we can see, the inverse deletion idea of the LinkedList ListIterator iterator is the same as the deletion idea of the ArrayList iterator iterator, that is, always go to the head of the list. The loop condition is always nextIndex=0 and the size of the comparison, delete a size to reduce 1, when the size is equal to 0, the end of the natural loop, traversal – delete operation end, can see its principle is relatively simple!

5 concludes

LinkedList is based on the LinkedList of linear table Java implementation, its principle is relatively simple, in fact, the principle of linear table is not very difficult.

LinkedList is a dual-end Queue based on a LinkedList. In JDK1.6, ArrayDeque is added. This class also implements the Deque interface, which can be used as a “dual-end Queue” to implement a Stack or Queue.

ArrayDeque internal deque is realized by using variable array, using two external references to keep the queue head node and end node access, remove queue end elements at the same time do not move the other elements, but the location of the mobile reference, which form a circular queue, to be able to reuse array space (allow team head index greater than of the index value). Compared to the use of a LinkedList to achieve dual-end queue LinkedList comprehensive efficiency better! At the same time, if used to implement the Stack, then compared to the Stack’s overall efficiency is also better! But ArrayDeque does not support null elements!

We’ll cover more collections later, such as basic collections like Stack, TreeMap, HashMap, LinkedHashMap, HashSet, TreeSet, and more advanced concurrent collections in the JUC package. If you want to learn the collection of source code to follow my column updates!

If you don’t understand or need to communicate, you can leave a message. Also hope to like, collect, follow, I will continue to update a variety of Java learning blog!