LinkedList

LinkendList is a two-way linked list and implements the Deque ue interface, which can be used as a queue. Although LinkendList is a linear structure, the data is not stored as a linear interface, but as data and address of the next node in each node, Cloneable interface, copy support, and java.io.Serializable support serialization and deserialization.

• Cloneable , Serializable interface through train: Analysis of ArrayList source code of java framework collection List subinterface

• Data structure through train: Analysis of sequential storage structure and chain storage structure of data structure, with pictures and texts, and it has risen again

• Queue through train : Queue of linear data structure (Queue)

Deque

Deque is the abbreviation of double ended queue, which supports the insertion and removal of elements at both ends, and is customarily called double ended queue. Most deque implementations have no fixed limit on the number of elements they may contain, but the interface supports capacity-limited deques as well as deques with no fixed-size limit

Deque also extends the Queue interface. When Deque is used as a queue, it will produce FIFO (first in, first out) behavior. Elements are added at the end of the deque and removed from the beginning.

The function of the double-ended queue is that it can be added from the head of the queue or added from the tail of the queue, and it can be obtained from the tail of the queue or obtained from the head of the queue.

Comparison of Deque and Queue methods

You can see that LinkendList is a collection, a queue, and a stack, but when we use it, we always reference it with a specific interface because we have the interface specification code The level of abstraction is higher, and the methods defined by the interface itself represent a specific purpose.

// Not recommended spelling:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// Recommended spelling:
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");

It can be seen that a principle of abstract-oriented programming is: try to hold interfaces instead of specific implementation classes.

LinkendList constructor

  // The number of nodes in the current list
  transient int size = 0;
  // first node
  transient Node<E> first;
  // last node 
  transient Node<E> last;
    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

Common methods of LinkendList

addAll()

    public boolean addAll(int index, Collection<? extends E> c) {
        // Check if subscript is out of bounds
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        // The collection to be added is empty, return directly
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        // The insertion position is the same as the number of the current list, expressed as tail insertion 
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            // Find the node where index is located 
            succ = node(index);
            // the previous node where index is located
            pred = succ.prev;
        }
        
        // Traverse the collection to be added and insert one by one
        for (Object o : a) {
            // Create a new node with pred as the previous node, value e, and null as the next node
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            // If pred is empty, it means inserting at the head
            if (pred == null) 
                // That is to say, the newly created node is the first node
                first = newNode; 
            else // pred is not empty, indicating that it is inserted in the middle or at the end
                // The next node of pred is connected to the newly created node
                pred.next = newNode; 
            // Insert one by one
            pred = newNode; 
        }
        // If succ is empty, it means inserting at the end
        if (succ == null) { 
            // So the last element inserted is the last element
            last = pred;
        } else { // succ is not empty, indicating that it is inserted in the middle
            // The last inserted element is connected to the following paragraph
            pred.next = succ;
            // The first element of the following paragraph is connected to the previous paragraph
            succ.prev = pred;
        }
        // Quantity Consolidation
        size += numNew;
        // Modifications +1
        modCount++;
        return true;
    }

Check array subscript out of bounds method

private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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

I saw the very familiar exception IndexOutOfBoundsException, just check it according to the size of the linked list

time complexity

addAll() belongs to a shallow copy method, which traverses the elements of one set to another set through a for loop, so the time complexity is O(N)

add()

public boolean add(E e) {
  linkLast(e);
  return true;
}

public void add(int index, E element) {
  // Check whether index is out of bounds, as analyzed above
  checkPositionIndex(index);

  // The insertion position is the same as the current number, indicating that it is a tail insertion
  if (index == size) 
    linkLast(element);
  else
    linkBefore(element, node(index));
}

public void addFirst(E e) {
  linkFirst(e);
}

public void addLast(E e) {
  linkLast(e);
}

It can be seen that the methods linkBefore() linkFirst() linkLast() are mainly called, so we will analyze these methods next

// Insert an element before a node
void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  // Get the previous node of succ
  final Node<E> pred = succ.prev; 
  // Create a new node, connect behind the previous node in succ
  final Node<E> newNode = new Node<>(pred, e, succ);
  // connect succ behind newNode
  succ.prev = newNode; 
  // If the previous node of succ is empty, it means that succ is the head node
  if (pred == null) 
    // Directly set newNode as the head node
    first = newNode; 
  else // If the previous node of succ is not empty, it means that succ is the middle or tail node
    // Associate the previous node of succ to newNode
    pred.next = newNode; 
  size++;
  modCount++;
}

linkFirst() and linkLast() have similar logic, so analyze linkFirst

// Insert an element into the head node
private void linkFirst(E e) {
  final Node<E> f = first; // current first node
  // A new node is created, with null as the previous node, e as the value, and the current first node as the next node
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode; // Set the newly created node as the first node
  if (f == null) // The current first node is empty, indicating that the list is empty
    last = newNode; // So the last node is the currently inserted node
  else // The current first node is not empty, indicating that the list is not empty
    f.prev = newNode; // The node inserted on the connection at the head of the current list
  size++;
  modCount++;
}

time complexity

The add() method has three ways of adding, head insertion, tail insertion, middle insertion, head insertion and tail time complexity being O(1), because the previous node does not need to be found through traversal, but time complexity is O(N), because you need to call node(int index) to find the element corresponding to the subscript, and then insert after it

get()

public E get(int index) {
  // Check whether index is out of bounds, as analyzed above
  checkElementIndex(index);
  return node(index).item;
}

Node<E> node(int index) {
  // If index is less than half of size, search from the beginning 
  if (index < (size >> 1)) {
    Node<E> x = first;
    // Find from the beginning until i == index
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else { // If index is greater than half of size, search from the end
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

getFirst() and getLast()

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

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

time complexity

The time complexity of the get() method is also described separately, because the LinkendList implementation holds the head and tail elements, so it can be obtained directly, and time complexity is O(1), but if it is obtained from the subscript, then the element corresponding to the subscript must be retrieved through traversal, and time complexity is O(N)

remove()

public E remove(int index) {
  // Check if index is out of bounds
  checkElementIndex(index);
  return unlink(node(index));
}

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

public E removeLast() {
  final Node<E> l = last;
  if (l == null)
    throw new NoSuchElementException();
  return unlinkLast(l);
}

It can be seen that the remove() method is similar to the add() method, and it also calls unlink() unlinkFirst() unlinkLast() respectively, which means to delete a node, delete the head node, and delete the tail node.

E unlink(Node<E> x) {
  // assert x != null;
  // Get the element of the current node
  final E element = x.item;
  // get to the next node
  final Node<E> next = x.next; 
  // get the previous node
  final Node<E> prev = x.prev; 
  // If the previous node of the current node is empty, it is the head node
  if (prev == null) { 
   // Just set the next node as the first node
    first = next;
  } else { // Not empty, indicating that it is an intermediate node or a tail node
    // Connect the previous node to the next node
    prev.next = next; 
    
    x.prev = null; 
  }

  if (next == null) { // If the next node of the current node is empty, it means the tail node
    // The tail node is removed, so make the previous node the tail node
    last = prev; 
  } else { // Not empty, indicating that it is an intermediate node
    // Connect the previous node to the next node
    next.prev = prev; 
     // The current node disconnects from the next node
    x.next = null;
  }
  // The current node element is set to be empty, which is convenient for GC
  x.item = null; 
  size--;
  // Modifications +1
  modCount++;
  return element;
}

private E unlinkFirst(Node<E> f) {
  // assert f == first && f != null;
  // Get the element of the current node
  final E element = f.item;
  // Get the next element of the current node
  final Node<E> next = f.next; 
  f.item = null;
  f.next = null; // help GC
  // Set the next node of the current node as the head node
  first = next;
  // If the next node is empty, the linked list has only one node
  if (next == null)
    // clear tail node
    last = null; 
  else // Otherwise, there are other nodes
    // The next node is already set as the head node
    // So clear the association with the previous node
    next.prev = null; 
  size--; // quantity: 1
  modCount++;
  return element;
}

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

time complexity

Deleted time complexity is O(1), find the precursor and successor nodes that need to be deleted directly, then point the pointer of the precursor node of the deleted element to the succeeding node, because it is a two-way Chain table, so you can directly manipulate the precursor node if it's not a singly linked list

clear()

public void clear() {
  // Iterate over and set all to be empty
  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++;
}

time complexity

It is not difficult to see from the implementation of the code that the time complexity of the clear() method is O(N), because it traverses and then empties the elements in turn, so the time complexity is O(N)

More methods can be viewed https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html

summary

LinkendList is a linear structure from the physical structure, and a chain storage structure from the logical structure. Although it is a linear structure, it is not stored in a linear order, but is stored scattered in memory. It establishes the connection between nodes through pointers, and implements Deque, which also indicates that it is a two-way Chain table. In the source code, it does not see how it handles thread security issues. So it's also a thread-insecure chain table, and you don't see null elements that aren't allowed to be inserted or duplicated, so it's a chain table that allows duplicate elements as well as null elements.