Java LinkedList source code analysis (picture)

Overall introduction

LinkedList implements both the List interface and the Deque interface, which means that it can be regarded as both a sequential container and a queue(Queue), and can also be regarded as a stack. From this point of view, LinkedList is simply an all-around champion. When you need to use a stack or queue, the first thing you should consider is LinkedList. Because Java has officially stated that it is not recommended to use the Stack class, and it is recommended to use LinkedList. What is even more regrettable is that there is no class called Queue in Java (it is an interface name).

The bottom layer of LinkedList is implemented through a doubly linked list. This section will focus on the maintenance process of the doubly linked list when inserting and deleting elements, that is, the solution between Function related to the List interface, while the knowledge related to Queue, Stack and Deque will be discussed in the next section. Each node of a doubly linked list is represented by the inner class Node. LinkedList references through first and last to point to the first and last elements of the linked list respectively. Note that there is no so-called dummy variable here. When the linked list is empty, first and last both point to null.

//Node内部类
private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

The implementation of LinkedList determines that all operations related to subscripts are linear time, and deleting elements at the beginning or end only requires constant time. In order to pursue efficiency, LinkedList does not implement synchronization (synchronized). If concurrent access by multiple threads is required, you can first use the Collections.synchronizedList() method to wrap it.

Method Analysis

add()

add() method has two versions, one is add(E e), this method is in LinkedList Insert elements at the end, because last points to the end of the linked list, and inserting elements at the end takes constant time. You only need to simply modify a few related references; the other is add(int index, E element). This method is to insert an element at the specified table below. You need to first find the specific position through linear search, and then Modify the relevant references to complete the insertion operation.

Combined with the above picture, we can see that the logic of add(E e) is very simple. The logic of

//add(E e)
public boolean add(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空，这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

add(int index, E element) is slightly complicated and can be divided into two parts. 1. First find the location to be inserted according to the index; 2. Modify the reference and complete the insertion. operate.

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

The node(int index) function in the above code is a little tricky, because the linked list is bidirectional, you can search from the beginning to the back, or you can search from the end to the front. The specific direction to look for depends on the condition index < (size >> 1), that is, whether the index is close to the front end or the back end.

remove()

remove()The method also has two versions, one is to delete the first element that is equal to the specified elementremove( Object o), the other is to delete the element at the specified index remove(int index).

#Both deletion operations require 1. First finding the reference of the element to be deleted, 2. Modifying the relevant reference to complete the deletion operation. When looking for a reference to a deleted element, remove(Object o) calls the element's equals method, while remove(int index) uses the subscript Counting, both ways has linear time complexity. In step 2, both revome() methods are completed through the unlink(Node x) method. Here you need to consider the boundary case when the deleted element is the first or last one.

//unlink(Node x)，删除一个Node
E unlink(Node x) {
    final E element = x.item;
    final Node next = x.next;
    final Node 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;//let GC work
    size--;
    return element;
}

get()

get(int index)Get the reference to the element at the specified index by calling the node(int index mentioned above ) method implementation.

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

set(int index, E element)The method modifies the element at the specified subscript to the specified value, and also first passes the node (int index)Find the reference corresponding to the element in the table below, and then modify the value of item in Node.

public E set(int index, E element) {
    checkElementIndex(index);
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

The above is the detailed content of Java LinkedList source code analysis (picture). For more information, please follow other related articles on the PHP Chinese website!