Preface: The source code of ArrayList is analyzed, and the reason why the average performance of inserting and deleting elements is poor is also analyzed. This introduction is more suitable for insertion and deletion of container LinkedList, of course, the latter has its own limitations.

1. Analysis of Function and Basic Meaning

1. LinkedList implements the List and Deque interfaces, allowing all elements to be empty. All methods in this class are not thread-safe, and of course jdk provides a way to translate them into thread-safe lists.
   List list = Collections.synchronizedList(new LinkedList(...));
2. Like Array List, LinkedList's iteration method is fail-fast, that is, when the Iterator of the array has been generated, changing the list's interface will cause an error at compile time and throw a Concurrent ModificationException.

2. Interclass dependencies

3. Relevant fields

1. Number of elements in list
   transient int size = 0;
2. The first element of the list
   transient Node<E> first;
3. The last element of the list
   transient Node<E> last;

4. Construction Method

1. Create a linked list

public LinkedList() {
} 

1. Create linked lists and pass in collections at the same time

/**
  * Constructor, passing in a set
  * @param c
  */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

5. internal class

LinkedList defines the Node class to represent the meaning of each node, mainly including the value of the node and the pointers of the front and back nodes.

/**
  * The nodes in the linked list include three attributes: value, front node and back node.
  * @param <E>
  */
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;
    }
}

6. Detailed description of common methods

LinkedList itself provides many methods for adding, deleting and searching linked lists. This time, we will not analyze each method in detail, but enumerate some common methods to find their commonalities.
From the relationships in the above classes, you can see that LinkedList itself implements two interfaces of List and Queue, so there are many methods with the same functions.
Look at the list of interfaces:
Deque interface:

List interface:

But in the implementation of the two interface methods, LinkedList itself is used to customize the method, such as getting the first element, adding elements, deleting elements, etc., where inserting code slices.

1. Insert elements at the beginning

/**
  * Insert element e into the head of the list
  */
 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++;
 }

2. Insert elements to the end of the list

/**
  * Insert element e at the end of the list
  */
 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++;
 }

3. Insert the element before the specified element

/**
  * Insert element e in front of non-empty element succ
  */
 void linkBefore(E e, Node<E> succ) {
     // Make sure succ is not empty
     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++;
 }

4. Delete the element preceding the specified element

/**
  * Unlink the front node of the non-empty node f
  */
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;
}

5. Elements after deleting specified elements

/**
  * Cancel the node after the associated non-empty node l
  */
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;
}

6. Delete the specified element

/**
  * Delete node x
  */
 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;
 }

7. Find the element corresponding to index

Call get(index), but this method actually gets the value subscribed to index through node(index). From the second method, we can see that java first judges the size of index and size/2, which is used to judge whether to traverse from behind or from before.

/**
  * Get the element at the subscript index
  * @param index
  * @return
  */
 public E get(int index) {
     checkElementIndex(index);
     return node(index).item;
 }

/**
  * Get the element at index
  * Firstly, the size of index and median is determined by dichotomy, and then the lookup is carried out.
  * @param index
  * @return
  */
 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;
     }
 }

The other methods are to call these seven basic methods to make specific implementation, are based on this change.
Only need to master these methods.

7. summary

As mentioned in the previous article, ArrayList is inefficient to add and delete, but efficient to retrieve.
LinkedList, on the contrary, is more efficient because it does not need to move the underlying array data, and its underlying is linked list implementation. It only needs to modify the node pointer of the linked list.
The query needs to locate the target node through traversal, and then compare one by one, which is inefficient.