LinkedList underlying structure

(1) The LinkedList bottom layer maintains a two-way linked list, which is an ordered set
(2) LinkedList maintains two attributes, first and last, which point to the first node and the last node respectively
(3) The Node object maintains three attributes: prev, next and item. Prev points to the previous Node, next points to the next Node, and item stores data.
(4) The addition and deletion of LinkedList elements are not completed through arrays, which is efficient

add() method

(1) add() adds the first element (element = 1), and here is the test code

LinkedList<Object> objects = new LinkedList<>();
        objects.add(1);
        objects.add(8);

(2) Put the debug breakpoint in the LinkedList. At this time, the number of elements is size = 0, and the first node and the last node are null

objects = {LinkedList@522} "[]"
 size = 0
 first = null
 last = null
 modCount = 0

(3) When the debug is executed to objects.add(1), the Force Step Into forcibly enters the source code. Here is a boxing (int - > integer)

public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

(4) Step Out and then Force Step Into is the add() method. The most important step of this method is linkLast(e), where e is the element to be added

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

(5) Jump into the linkLast(e) method and know that last = null, so pass l = null into the Node constructor and execute the second line of code final Node newnode = new Node < > (L, e, null); Jump into Node() constructor

/**
     * Links e as last element.
     */
    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++;
    }

(6) Node (reference prev of the previous node, element, reference next of the next node), known l = null, i.e. Node(null, 1, null)

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

(7) New a new node, newNode = new node < > (null, 1, null), and the reference of the new node is LinkedList$Node@531 , then assign the newNode to the tail node last, enter if(l == null), and finally assign the newNode to the first node first, so the newNode, first and last point to this node at the same time. Therefore, when there is only one node, the first node is the tail node


At this time, the forward and backward pointing is still empty

newNode (slot_3) = {LinkedList$Node@531} 
 item = {Integer@530} 1
  value = 1
 next = null
 prev = null

(7) When the first element is added, there is only one node. If the second element is added, a two-way linked list will be formed, because adding the second element will create a node at the bottom layer. Then, the bottom layer can connect the two nodes to form a two-way linked list by changing the forward and backward directions of the two nodes

objects = {LinkedList@522} "[1]"
 size = 1
 first = {LinkedList$Node@531} 
  item = {Integer@530} 1
  next = null
  prev = null
 last = {LinkedList$Node@531} 
  item = {Integer@530} 1
  next = null
  prev = null
 modCount = 1

(8) Add a second element (element = 8)

(9) Here, we directly look at the execution process of the linkLast() method. At this time, last points to the first node, assign last to the prev of the second node of new, and the second node will point to the first node. Then, judging by if, l is not empty, so we assign the reference of the second node to the next of the first node, and the first node points to the second node through next, Bidirectional linked list formation

debug information

objects = {LinkedList@522} "[1, 8]"
 size = 2
 first = {LinkedList$Node@530} 
  item = {Integer@551} 1
  next = {LinkedList$Node@539} 
  prev = null
 last = {LinkedList$Node@539} 
  item = {Integer@535} 8
  next = null
  prev = {LinkedList$Node@530} 
 modCount = 2

Through the linkLast() method, you can see that the reference of the second node is newNode= {LinkedList$Node@539 }, it can be seen from the information displayed by debug that the next of the first node storing element 1(item = 1) also points to this reference. Because there are only two nodes temporarily, the first node points to the first node object and the last node points to the second node, which can be obtained according to the program, The prev of the first node is not assigned when it is created, and the next of the second node is empty because node newnode = new node < > (L, e, null) when the node object is created; Next is null by default. The popular understanding is that there are no node objects before and after these two nodes, so there is no need to point to them. Therefore, the first node is first = null and the tail node is last = null