LinkedList source code analysis

LinkedList The bottom layer is based on linked list , Adding or deleting does not require moving data , So it's very efficient . But the efficiency of querying and modifying data is low , You can't quickly locate the data according to the subscript like an array , You need to traverse the data one by one .

data structure

LinkedList It is a structure based on linked list , The main core is Node node , Source code is as follows ：

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

The structure is shown in the following figure ：

This is a double linked list structure , Yes prev Leading pointer and next Post pointer .

And the first node first、 Caudal node last、 length size:

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

Add data

LinkedList There are two ways to add elements ：add(E e) and **add(int index,E e)**.

• add(E e) Add data at the end of the linked list
• add(int index,E e) Add data at the specified linked list location

add(E e)

add Method is called linkLast Method :

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

linkLast Indicates that the specified element is added at the end of the linked list ：

void linkLast(E e) {
    //  Record the original tail node  
    final Node<E> l = last;
    //  Create a new node , The front node of the new node is the original tail node 
    final Node<E> newNode = new Node<>(l, e, null);
    //  Update tail node 
    last = newNode;
    if (l == null)
        //  The tail node is empty , Update the header node 
        first = newNode;
    else
        //  The tail is not empty , The original trailing node is the new node 
        l.next = newNode;
    // size  and  modCount  Self increasing   
    size++;
    modCount++;
}

• Record the original tail node l
• Create a new node , The front node points to the original tail node .
• If l It's empty , Update the header node
• Update tail node
• If l Not empty ,l The post pointer to the new node

If the original tail node is empty , Create a node directly , This node is last and first node . If the original tail node is not empty , Create a new node , The front of the new node points to the original last, The original last Of next Point to a new node .

add(int index,E e)

This method is to add elements to the specified position of the linked list , The subscript of the linked list is the same as that of the array , Also from the 0 From the beginning :

Have a look first add(int index, E element) Method

public void add(int index, E element) {
    //  Check if the subscript is out of range 
    checkPositionIndex(index);
    if (index == size)
        //  The subscript is equal to size, Add directly to the end of the list 
        linkLast(element);
    else
        // 
        linkBefore(element, node(index));
}

checkPositionIndex Determine if the subscript is out of bounds ,index >= 0 && index <= size index Whether in 0 ~ size Within limits .

If index be equal to size, and add(E e) Same operation , Are added at the end of the linked list . If index Less than size, call linkBefore Method , Insert a node into the middle of the linked list . First of all to see node Method ：

Node<E> node(int index) {
    // assert isElementIndex(index);
    // size >> 1  Express  size  Moves to the right one , Namely  size/2 size Half of 
    // index  Less than  size  Half of , Traverse back from the first node 
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    // index  Greater than  size  Half of , Traverse forward from the last node     
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

node() The way is to find index Corresponding node node .

For example, a length of 5 The linked list of :

node(1) from first node （ The first 0 Nodes ） Go back through one , That is to say 1 Corresponding node . node(3) from last node （ The first 4 Nodes ） Go ahead and traverse a , That is to say 3 Corresponding node .

Find the node by subscript , The linked list generally needs to be traversed , You need to traverse half of the linked list at most , It mainly uses the characteristics of double linked list , You can traverse from front to back , You can traverse from back to front .

size>>1 Express size/2, Judge index Is it in the first half or the second half of the linked list , If you traverse back from the first node in the first half , If you traverse forward from the last node in the second half ,, This traverses at most size Half of , Avoid traversing the entire linked list . find index After the node under , Look again linkedBefore Method :

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //  Record the front node  pred
    final Node<E> pred = succ.prev;
    //  Create a new node , New nodes pre Point to  pred,next Point to succ node 
    final Node<E> newNode = new Node<>(pred, e, succ);
    // succ pre Point to a new node 
    succ.prev = newNode;
    //  If pred It's empty , Express succ It's the first node , The new node is assigned to the first node 
    if (pred == null)
        first = newNode;
    else
    // pred Of next  Point to a new node 
        pred.next = newNode;
    size++;
    modCount++;
}

• Record succ The front node of the node pred.
• The new node , pre Point to pred, next Point to succ.
• succ Of pre Point to a new node .
• If pred by null, Indicates that the first node is succ, Assign a node to first node .
• If pred Not for null, pred Of next Point to a new node .

For example, a length of 5 The linked list of , The subscript for 1 Add data to the location of ：

get data

Data acquisition mainly includes get、getFirst、getLast.

get The method is mainly through node Method subscript node , Get the item data .

getFirst Method to get Head node Of item.

getLast Method to get Caudal node Of item.

Delete data

remove(Object o)

Remove the first matching element from the list

public boolean remove(Object o) {
    //  Judge whether it is null
    if (o == null) {
        //  Traverse node 
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        //  Traverse node
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Deletes the specified element , You need to determine whether the element is null.

• If null, Just use x.item == null Sentence judgment .
• If not for null, Just use o.equals(x.item) Sentence judgment .

Then call unlink Method ：

E unlink(Node<E> x) {
    // assert x != null;
    //  Record nodes element、next and prev
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // prev by null,next  Assign to the first node  
    if (prev == null) {
        first = next;
    } else {
        // prev Of next Point to next node 
        prev.next = next;
        // x node prev Set as null
        x.prev = null;
    }
    // next by null,prev Assign as tail node 
    if (next == null) {
        last = prev;
    } else {
        // next Of prev Point to prev
        next.prev = prev;
        // x node next Set as null
        x.next = null;
    }
    // x.item Set as null
    x.item = null;
    //  The length decreases 
    size--;
    modCount++;
    return element;
}

Pictured , To delete 1 Data node ：

remove(int index)

Delete the data of the specified subscript ：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

First, through node Find the node corresponding to the subscript , Call again unlink Delete the data .