In this chapter, we’ll take a quick look at LinkedList. If you have any questions, please contact me at [email protected]. Ask for directions of various gods, thank you.

Note: This article is based on JDK1.8 and provides a brief explanation of some of the common methods used in LinkedList.

1. LinkedList profile

LinkedList is a LinkedList type of data structure that supports efficient insert and delete operations. It implements a Deque interface that makes LinkedList queue like. The underlying data structure implemented by the LinkedList class is a two-ended LinkedList.

Two: data structure chart analysis



As can be seen from the figure, the LinkedList data structure uses a bidirectional LinkedList structure, with a head node and a tail node. The precursor node of the first node is null, and the successor node of the last node is null. Each of these nodes has two Pointers to precursor and successor nodes, which means that we don’t have to scale up our LinkedList to add or modify it like an ArrayList does.

Three: inheritance relationship analysis

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.SerializableCopy the code
  • AbstractSequentialList. AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList He uses the get, set, add, and remove methods based on iterators.
  • Implement the List interface, indicating that he can carry out queue operations
  • Implement the Deque interface and use the LinkedList as a double-ended queue
  • If the Cloneable interface is implemented, cloning can be performed
  • Implement Serializable interface, indicating that can be serialized

Four: source code analysis

1: member variable

// Transient variable will not be serialized transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item ! = null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */ transient Node<E> last;Copy the code

The member variables of LinkedList are simple, with only three. Where size represents the actual number of elements in the list.

According to the notes and the data structure diagram above, it can be seen that:

  • When the linked list is empty, both first and last must be empty.
  • When the list is not empty, the precursor of FIRST must be empty, and first.item must not be empty. Last must be empty, and last.item must not be empty.

2: inner class

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) {this.item = element; this.next = next; this.prev = prev; }}Copy the code

3: Construction method

// Build an empty list publicLinkedList() {} /** * construct a list containing set C ** @param c The collection whose elements are to be placed into this list * @throws NullPointerExceptionif the specified collection is null
 */ 
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}Copy the code

4: Common methods

  • Add elements to the first node
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}Copy the code

Then, call Node to create a new Node. The new Node is regarded as the new first. At this time, if the previous first is empty, it indicates that the linked list is empty before insertion, and the newly inserted Node is not only the first Node but also the last Node. So last points to the newly inserted newNode.

If the previous first is not empty, then leave last untouched and set the precursor node of FIRST to the new node. At this point, the original first node is the second node in the linked list.

Finally, insert successfully, increase the number of linked list nodes by one

Note: Fail-fast mechanism

The modCount variable records the number of times the current list has been modified. We know that the LinkedList is thread unsafe and that the iterator initialization assigns this value to the expectedModCount of the iterator as it traverses the list. During iteration, test whether the modCount is equal to the expectedModCount. If the modCount is not equal, it indicates that other threads have modified it. So will throw ConcurrentModificationException. So when traversing non-thread-safe data structures, try to use iterators.

Important: Adding elements to a linked list

public boolean addAll(Collection<? extends E> c) {
    returnaddAll(size, c); } public Boolean addAll(int index, Collection<? Extends E> c) {extends E> c) {extends E> c) {index>=0 and index is less than or equal to the number of nodes in the current list. Object[] a = c.toarray (); Int numNew = a.length;if (numNew == 0)
            return false; Node<E> pred, succ; // If the inserted node is the end of the list, the preceding node is the last node, and the subsequent nodes are emptyif (index == size) {
            succ = null;
            pred = last;
        } else{succ = node(index); Pred = succ.prev; pred = succ.prev; } // Iterate over the arrayfor (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o; // create a newNode Node<E> newNode = newNode <>(pred, E, null); // Insert before the first elementif (pred == null)
                first = newNode;
            elsePred. Next = newNode; Pred = newNode; pred = newNode; pred = newNode; If succ is empty, the inserted node is behind the last node in the listif (succ == null) {
            last = pred;
        } else{// Now we need to concatenate the second half of the list. Next = succ; pred = succ; pred = succ; pred = succ; succ.prev = pred; } // List length increment size += numNew; // increase the number of operations modCount++;return true;
    }Copy the code

Gets the node at the specified location

// We can see that the LinkedList is optimized for this search. Instead of blindly traversing the entire list, we determine whether the coordinate to be searched is near the first or the last node. 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;
        returnx; }}Copy the code

Deletes an element (the element is not empty

E unlink(Node<E> x) { // assert x ! = null; Final E element = x.tem; // Final E element = x.tem; // Store the subsequent nodes of the Node to be deleted. Final Node<E> next = x.next; Final Node<E> prev = x.rev; // If the previous node of the node to be deleted is empty, the node to be deleted is the header node. // Set the next node of the node to be deleted as the header.if (prev == null) {
        first = next;
    } elsePrev. next = next; x.prev = null; } // If the node to be deleted is a tail nodeif (next == null) {
        last = prev;
    } else{ next.prev = prev; x.next = null; } x.item = null; // Element length minus size--; ModCount++;return element;
}Copy the code

Delete the first node in the LinkedList (private)

Private E unlinkFirst(Node<E> f) {// Assert f == first && f! = null; // Stores the value of the node to be deleted, which is used to return the value of the node to be deleted with = final E element = F.tem; // Store the subsequent nodes of the Node to be deleted. Final Node<E> next = f.next; // set f and its next to null f.tem = null; f.next = null; //helpFirst = next; first = next; // Check whether next is empty. If next is empty, the original list has only one nodeif(next == null) // Last = null;elsePrev = null; // Next is already the head node, so set the precursor node of the head node to null. // List element count minus one size--; ModCount++;return element;
}Copy the code

Delete the last node of the LinkedList. (This object is not empty

private E unlinkLast(Node<E> l) { // assert l == last && l ! = null; // Save the value of the element to be deleted to return final E Element = L.tem; // Save the precursor Node of the element to be deleted. Final Node<E> prev = l.prev; // Set the contents of the node to be deleted to null l.tem = null; l.prev = null; //helpLast = prev; last = prev; // Check whether prev is empty. If it is empty, the original list has only one nodeif (prev == null)
            first = null;
        else// Set the next node of the last node to null. Next = null; size--; modCount++;return element;
    }Copy the code

Tool function

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

    /**
     * Removes and returns the last element from this list.
     *
     * @return the last element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }Copy the code

Five:

We can see that LinkedList does not need to be expanded as ArrayList does when adding and removing elements. To find an element based on its location, you don’t fetch it directly, as you would in an ArrayList. So LinkedList is more suitable for situations where there are frequent additions and deletions, but not many lookups.

The same optimization that determines whether an element is near the top node or the tail node can be used in everyday code

LinkedList is not thread-safe, and we try to use iterators during traversal