JDK collection source code LinkedList parsing

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

The three basic attributes are transiently decorated with the keyword so that they are not serialized.

public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }// Appends all elements in the specified collection to the end of this list
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
// Inserts all elements from the specified collection into the collection starting at the specified location
public boolean addAll(int index, Collection<? extends E> c) {// Inserts all elements from the specified collection into the collection starting at the specified location
    checkPositionIndex(index);// check if index >= 0 && index <= size
    Object[] a = c.toArray();// Convert the collection to an array of type Object
    int numNew = a.length;// Get the length of the array
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    if (index == size) {// When the index to be inserted is at the last element of the list
        succ = null;// The current node is empty
        pred = last;// The first node of the collection to be joined is the last node of the original list
    } else {
        succ = node(index);// Get the index position of the node
        pred = succ.prev;// The precursor points to the previous node of the index node
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)// If the precursor is NULL, the current node is at the head of the list
            first = newNode;// Make the head node equal to the newly created node
        else
            pred.next = newNode;// The tail pointer of the precursor node points to the head node
        pred = newNode;// Pred moves forward and backward
    }
    if (succ == null) {// The index is at the end of the original list
        last = pred;// The tail node points directly to the end of the spliced completion list
    } else {
        pred.next = succ;// The back-end node of pred is succ
        succ.prev = pred;// The precursor of suCC is pred
    }
    size += numNew;// Number of elements in the set +numNew
    modCount++;// Set changes +1
    return true;
}
// Returns the (non-empty) node at the specified element index.
Node<E> node(int index) {
    if (index < (size >> 1)) {// If the index is in the first half of the list element
        Node<E> x = first;// Locate index from the beginning node
        for (int i = 0; i < index; i++)
            x = x.next;// Move the pointer to index
        return x;// Return the contents of this object
    } else {// If the index is in the last half of the list element
        Node<E> x = last;// Locate the index position from the tail node
        for (int i = size - 1; i > index; i--)
            x = x.prev;// Move the pointer to index
        return x;// Return the contents of this object}}Copy the code

Given by two no-parameter constructors, this is an unbounded two-ended queue.

/** * adds the element */ to the header
private void linkFirst(E e) {
    final Node<E> f = first;/ / the first node
    final Node<E> newNode = new Node<>(null, e, f);// Create a new node, next of which is the first node
    first = newNode;// make the new node the new first node
    if (f == null)// Determine if the element is the first to be added
        last = newNode;// If so, set last to the new node
    else// If not, set the prev pointer of the original first node to the new node
        f.prev = newNode;// The first node is preceded by the new node
    size++;// The number of elements increases by 1
    modCount++;// The number of changes added by 1 indicates that this is a fail-fast set
}
Copy the code

LinedList, as a collection, needs to add elements elsewhere in the middle. This is done using the following method:

// Add the element at the specified index position
public void add(int index, E element) {
    checkPositionIndex(index);// Determine if the boundary is crossed,
    if (index == size)// If index is a position after the last node of the queue
        linkLast(element);// Add the new node directly after the last node
    else// Otherwise call linkBefore() to add nodes in the middle
        linkBefore(element, node(index));
}
Returns the (non-empty) node at the specified element index.
Node<E> node(int index) {
    // Because it is doubly linked
    if (index < (size >> 1)) {// If the index is in the first half of the list element
        Node<E> x = first;// Locate index from the beginning node
        for (int i = 0; i < index; i++)
            x = x.next;// Move the pointer to index
        return x;// Return the contents of this object
    } else {// If the index is in the last half of the list element
        Node<E> x = last;// Locate the index position from the tail node
        for (int i = size - 1; i > index; i--)
            x = x.prev;// Move the pointer to index
        return x;// Return the contents of this object}}void linkBefore(E e, Node<E> succ) {// Insert element e before the non-empty node succ
    // succ is the successor of the node to be added
    final Node<E> pred = succ.prev;// Find the front node of the node to be added
    final Node<E> newNode = new Node<>(pred, e, succ);// Create a new node between its front node and its successor
    succ.prev = newNode;// Modify the leading pointer to the new node
    if (pred == null)// Check whether the front node is empty
        first = newNode;// If it is null, it is the first element to be added
    else// Otherwise, change next of the front node to the new node
        pred.next = newNode;
    size++;// Change the number of elements in the set
    modCount++;// The number of set changes is increased by 1
}
Copy the code

LinkedList to add elements in the middle of the implementation principle is a typical double LinkedList to add elements in the middle of the process!

As shown in figure:

• Adding elements at the beginning and end of the queue is efficient, O(1) time
• It is inefficient to add elements in the middle. First, we need to find the nodes at the insertion position, and then modify the Pointers of the nodes before and after. The time complexity is O(n).

public E removeFirst(a) {// remove throws an exception if no element is present
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {// Delete the first node
    // assert f == first && f ! = null;
    final E element = f.item;// The element value of the first node
    final Node<E> next = f.next;// Next pointer to the first node
    f.item = null;
    f.next = null; // Assist GC collection
    first = next;// make next of the first node as the new first node
    if (next == null)// If there is only one element, delete it and set last to null
        last = null;
    else// Otherwise, set next's leading pointer to null
        next.prev = null;
    size--;// The number of elements is reduced by 1
    modCount++;// The number of changes is increased by 1
    return element;// Returns the deleted element
}
Copy the code

public E remove(int index) {// Delete the intermediate node at index
    checkElementIndex(index);// Check for overbounds
    return unlink(node(index));// Delete the index node
}

/** * Delete node x. */
E unlink(Node<E> x) {
    // assert x ! = null;
    final E element = x.item;// The element value of x
    final Node<E> next = x.next;// the post-node of x
    final Node<E> prev = x.prev;// The front node of x
    if (prev == null) {// If the front node is empty
        first = next;// specify the first node, so that first points to the node after x
    } else {// Otherwise change next of the front node to the back node of x
        prev.next = next;
        x.prev = null;// the prefix of x is empty
    }
    if (next == null) {// If the back node is empty
        last = prev;// Last points to the front node of x
    } else {// Otherwise, change the prev of the rear node to the front node of X
        next.prev = prev;
        x.next = null;// x is null after x
    }
    x.item = null;// Empty the element value of x to assist GC
    size--;// The number of elements is reduced by 1
    modCount++;// The number of changes is increased by 1
    return element;// Returns the deleted element
}
Copy the code

PollFirst (), pollLast(), peekLast(), peekFirst(), pollFirst(), pollLast(), peekFirst(), and so on. The implementation principle is the same. Here are two simple examples:

// poll returns null if there are no elements
public E pollFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : unlinkFirst(f);
}
// poll returns null if there are no elements
public E pollLast(a) {
    final Node<E> l = last;
    return (l == null)?null : unlinkLast(l);
}
Copy the code

The three methods for deleting elements are typical double-linked list deletion methods, and the general process is shown in the figure below:

• Removing elements at the beginning and end of the queue is efficient and takes O(1) time.
• It is inefficient to delete elements in the middle. First, it is necessary to find the node at the deleted position, and then modify the pointer before and after. The time complexity is O(n).

1) LinkedList is a List implemented as a double-linked List; 2) LinkedList is also a double-ended queue, with queue, double-ended queue, stack characteristics; 3) The LinkedList is very efficient in adding and deleting elements at the beginning and end of the queue, and the time complexity is O(1); 4) Adding and deleting elements in the middle of LinkedList is inefficient, and the time complexity is O(n); 5) LinkedList does not support random access, so accessing non-queue elements is inefficient; 6) LinkedList equals ArrayList + ArrayDeque in function;

ArrayList represents a typical implementation of List, LInkedList represents a typical implementation of Deque, and LInkedList implements List.