Analysis of the internal principle of LinkedList

notes ： Analyzed in this article LinkedList The source code is based on Java 1.8 .

Header

List Collection , It was analyzed before ArrayList , There's still LinkedList Not analyzed . Then take advantage of today's free , Just put LinkedList Let's talk about the internal principle of .

LinkedList Is an ordered and repeatable set of elements , The bottom layer is based on bidirectional linked list . Because it is a linked list , Therefore, there is no dynamic capacity expansion step .

Source code analysis

Construction method

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

Copy

One of the construction methods is default , The other is to pass in a collection , And then call addAll Method to add all the elements of the collection .

Node

LinkedList As a linked list , Then there must be nodes , Let's look at the definition of nodes ：

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

Copy

Each node contains the previous node prev And the next node next ,item That is, the elements to be stored in the current node .

add(E e)

    public boolean add(E e) {
        //  Add elements directly to the end of the team 
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        //  Save the original tail node of the linked list ,last  Global variable , Used to represent the tail element 
        final Node<E> l = last;
        //  For this element  e  Create a new node 
        final Node<E> newNode = new Node<>(l, e, null);
        //  Set the new node as the end of the queue 
        last = newNode;
        //  If the original tail element is empty , Then it means that the original whole list is empty , Assign the new node to the head node 
        if (l == null)
            first = newNode;
        else
        //  The original tail node is followed by the newly generated node 
            l.next = newNode;
        //  Number of nodes  +1
        size++;
        modCount++;
    }

Copy

stay linkLast(E e) in , First, judge whether the original tail node is empty . If the tail node is empty , Then it means that the original list is empty . The header node will also point to this element ; If it's not empty , Add directly to the back .

Actually in first Before , And one for null Of head node .head Node next It's just first node .

add(int index, E element)

    public void add(int index, E element) {
        //  Check  index  Is it beyond the index range 
        checkPositionIndex(index);
        //  If appended to the tail , Then follow  add(E e)  The same 
        if (index == size)
            linkLast(element);
        else
        //  Otherwise, it is inserted in other positions 
            linkBefore(element, node(index));
    }

Copy

stay add(int index, E element) It mainly depends on linkBefore(element, node(index)) The method . Notice that there's one node(index) , I wonder what I did ？

    Node<E> node(int index) {
        // assert isElementIndex(index);
        //  If  index  In the first half , Traverse from front to back to get  node
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //  If  index  In the second half , Traverse from back to front to get  node
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

Copy

It turned out to be for indexing index Corresponding node , The algorithm is optimized in speed .

obtain Node after , I'm going to call it linkBefore(element, node) .

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //  preservation  index  The front node of the node 
        final Node<E> pred = succ.prev;
        //  Create a new target node 
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        //  If it is inserted at the beginning 
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

Copy

This code is very similar to the previous one , Students who understand the insertion of linked list nodes should be very easy 了 .

addAll(Collection<? extends E> c)

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

Copy

stay addAll(Collection<? extends E> c) Internal direct call is addAll(int index, Collection<? extends E> c) .

    public boolean addAll(int index, Collection<? extends E> c) {
        // index  Index range judgment 
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        //  Save the previous front and rear nodes 
        Node<E> pred, succ;
        //  Determine whether to insert at the tail or at other positions 
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            //  If the previous node is empty , It means it's inserted in the head 
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

Copy

addAll(int index, Collection<? extends E> c) In fact, it is equivalent to many times add(int index, E element) operation , Add the internal loop to the linked list .

get(int index)

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

Copy

Called inside node(index) Method , and node(index) The method has been analyzed above . Is to judge whether it is in the first half or the second half , Then traverse to get .

remove(int index)

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

Copy

remove(int index) Called in unlink(Node<E> x) Method to remove the node .

    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 you want to delete a header node , Then set the head node as the next node 
        if (prev == null) {
            first = next;
        } else {
            //  Set the... Of the previous node of this node  next  For this node  next
            prev.next = next;
            x.prev = null;
        }
        //  If you want to delete the tail node , Then set the tail node to the previous node 
        if (next == null) {
            last = prev;
        } else {
            //  Set the next node of this node  prev  For this node  prev
            next.prev = prev;
            x.next = null;
        }
        //  Set up  null  value ,size--
        x.item = null;
        size--;
        modCount++;
        return element;
    }

Copy

remove(Object o)

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

Copy

remove(Object o) The code of is to traverse the linked list , Then get the same value and put it unlink(x) 了 . as for unlink(Node<E> x) Code for , It has been analyzed above .

set(int index, E element)

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        //  Set up  x  The value of the node is the new value , Then return the old value 
        x.item = element;
        return oldVal;
    }

Copy

clear()

    public void clear() {
        //  Traversing the linked list , Then delete and empty one by one 
        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++;
    }

Copy

Footer

LinkedList be relative to ArrayList Come on , The source code will be a little more complex . Because it involves linked lists , So there will be prev and next Points . But calm down and read , It's still understandable .

The source code of the basic collection class is almost the same , So far, a total of ArrayList、LinkedList、HashMap and HashSet Four classes .

Later, if you are free, there will be more collection classes for source code parsing , Then work hard .