LinkedList underlying source code

LInkedList Bottom source

sketch

• There are two data structures in the data structure , Linear list and chain storage structure ( Linked list )、
• Sequential storage structure :Vector,Stack,ArrayList
• Chain storage structure ：linkedList,Queue

Inherited AbstartSequentialList Realized List,Deque,Coneable,Serializable

List aggregate ,Deque deque ,Coneable clone ,Serializable serialize

Create persistent objects ,LinkedList The elements in are nodes , The real data is stored in Node in

Add and delete operations are very fast ( Complexity O(1)), The operation of checking and modifying is relatively slow

linkedList The operation of single thread safety , Multithreading is not safe

Internal interface method

list Methods of interface existence

public interface List<E> extends Collection<E> {
    ...
    //  increase 
    boolean add(E e);
    void add(int index, E element);
    //  Delete 
    boolean remove(Object o);
    E remove(int index);
    //  Change 
    E set(int index, E element);
    //  check 
    E get(int index);
    ...
}

Linkedlist Member variables of

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    
    //  Serialize unique representation  UID
    private static final long serialVersionUID = 876323262645176354L;
    
    // LinkedList Size , In fact, it is the number of storage elements in the bidirectional linked list maintained internally 
    transient int size = 0;

    //  Head node , Pointer or reference to the first node , The default is  null
    transient Node<E> first;

    //  Tail node , Pointer or reference to the last node , The default is  null
    transient Node<E> last;
    ...
    
}

transient Prevent serialization ,

There are linked list lengths , Head node , Tail node

Constructors

  public LinkedList() {
    }
     No arguments structure 
    
  public LinkedList(Collection<? extends E> c) {
        //  Point to a parameterless constructor 
        this();
        addAll(c);
    }  
     There are parametric structures 
     Constructs a list collection containing the specified elements 

Inside Node node

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

• because LInkedList It's a two-way list , Therefore, from the following Node Two pointer data of the node , A node pointing up , A node pointing down , is equivalent to ArrayList In the source next and province

there Node It has to be static ,Node stay LInkedList Class is an inner class , If not used static modification , that Node Class is an ordinary inner class , stay java After instantiation, a common inner class in , By default, it will cause the reference of external classes , This may cause memory leakage

First step ：E item Stored elements 　next Point to next node ,prev Point to the previous node , Construction method of inner class

increase add Method ()

 public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
      
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    
    

add(int index, E element) First add Method two parameters ,index Is the subscript parameter ,element For element parameters

• The first step is to use checkPositionIndex Method , Check whether the current node location exists , If it doesn't exist , Throw an exception

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

 Judge the position subscript of the element 
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

• The second step is to compare the subscript position with the set length , there index Should be pointer , Expand the capacity of the tail of the linked 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++;
    }

At the end of the linked list, expand the capacity by tail interpolation

• Step 3 if not equal

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    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++;
}

In the linked list, the broken chain is added, and the data is regenerated into new nodes

• Step four ：nextIndex Here is the backward pointer ,expectedModCount Pointer to the current element

boolean add(E e) Judge the tail node

addAll Method

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

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

        Node<E> pred, succ;
        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 (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;
    }

boolean addAll()

addAll The object is Collection Collection object for , The return value is the following method

First, check whether the subscript conforms to , Copy the obtained set as Object type

Get the length of the array , And judge , Is it equal to ０, If it is equal to ０, Then the set is modified in the process of adding data

Define the pre node and post node , Then judge whether it is the tail of the linked list , If it is , Appending data at the end of the linked list

The rear node of the tail must be null, The front node is the end of the team , If it is not at the end of the linked list , In the middle of the linked list , Take out index node , And as a successor node ,index The front node of , As a node precursor

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

Then cycle to increase , by for Loop through groups , Point to the insertion operation of nodes in turn , Do type conversion , If the predecessor node is empty , be newNode Is the head node , Otherwise pred Of next The node of

When the cycle ends , If the post node is null, Explain that at this time, it is added at the end of the team , Otherwise, it will be added to the heap , You need to update the pre node and post node , Then modify the quantity

node Method , First, take out index node , If index Less than size/2/, Search from the head , Assign the header node to x, And then we're going to iterate , If index Greater than or equal to size/2 Then traverse from the back , And then test index Is the location of the legal

addFirst(E e) Add the element to the end of the connector

 public void addFirst(E e) {
        linkFirst(e);
    }
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++;
    }

First, create a new node , And take the head node as the successor node , Then judge , If the end of the linked list is empty , be last Also point to this node , otherwise , Point the forward pointer of the head node to the new node , That is to say, the next element

addLast(E e) Add the element to the end of the linked list

public void addLast(E e) {
        linkLast(e);
    }

How to get data get

public E get(int index) {
        // Check index Whether the scope is in size within 
        checkElementIndex(index);
        // call Node(index) Go find index Corresponding node Then return its value 
        return node(index).item;
    }

Check idnex Whether in size in , call Node(index) find index Corresponding node And the return value

Get the data method of the header node getFirst

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
public E element() {
        return getFirst();
    }
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
 
public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

getFirst An exception will be thrown when the header node is empty , and element For internal use getFirst Method ;peek and peekFirst Method returns when the header node is empty null

• First step ： Define the head node , Throw an exception if it is empty , And return to the current node
• The second step ： Return to the first node

Get the data of the tail node getLast()

public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
 public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;

First step ：getLast() Define the tail node , If it is empty , Throw an exception , And return to the current node

The difference between the two is whether to throw an exception or return when the tail node is empty null

Get from the object index Method

int index(Object o)

Go over it from the beginning

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            // Traverse from the beginning 
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            // Traverse from the beginning 
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

• First step ： Define pointer position ( For the initial ０)
• The second step ： Judge whether the incoming object is null , When the incoming node is not empty , Traversal , Define a new node equal to the first node , Judge whether the Condition node is not empty , Traversing nodes keeps going backwards , Then judge , If the traversal current node is empty , Then return the pointer position , When the incoming node is empty , ditto

int lastIndexOf(Object o)： From the tail traversal to find

public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            // Traversing from the tail 
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            // Traversing from the tail 
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

contains(Object o)： Check the object o Whether it exists in the linked list

public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

from indexOf() It can be seen that if there is no such Object Returns the -1

Delete method

remove() ,removeFirst(),pop(): Delete header node

public E pop() {
        return removeFirst();
    }
public E remove() {
        return removeFirst();
    }
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

removeLast(),pollLast(): Delete tail node

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

remove(Object o): Deletes the specified element

public boolean remove(Object o) {
        // If the deleted object is null
        if (o == null) {
            // Traverse from the beginning 
            for (Node<E> x = first; x != null; x = x.next) {
                // Element found 
                if (x.item == null) {
                   // Remove the found element from the linked list 
                    unlink(x);
                    return true;
                }
            }
        } else {
            // Traverse from the beginning 
            for (Node<E> x = first; x != null; x = x.next) {
                // Element found 
                if (o.equals(x.item)) {
                    // Remove the found element from the linked list 
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

unlink(Node x) Method ：

E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;// Get the successor node
final Node prev = x.prev;// Get the precursor node

    // Delete precursor pointer 
    if (prev == null) {
        first = next;// If the deleted node is the head node , Make the head node point to the successor node of the node 
    } else {
        prev.next = next;// Point the successor node of the precursor node to the successor node 
        x.prev = null;
    }
 
    // Delete subsequent pointer 
    if (next == null) {
        last = prev;// If the deleted node is the tail node , Make the tail node point to the precursor node of the node 
    } else {
        next.prev = prev;
        x.next = null;
    }
 
    x.item = null;
    size--;
    modCount++;
    return element;
}

The essence is to delete a node , Then connect the original predecessor node with the original successor node

remove(int index)： Deletes the element at the specified location

public E remove(int index) {
        // Check index Range 
        checkElementIndex(index);
        // Delete node 
        return unlink(node(index));
    }

After some study and testing , The following conclusions are drawn ： These methods start from the beginning of design , From the set Collections, queue Queue, Stack Stack, deque Deque, So they are semantic , It is not recommended to categorize it as adding / Delete .

• add and remove It's a pair. , Derived from Collection;
• offer and poll It's a pair. , Derived from Queue;
• push and pop It's a pair. , Derived from Deque, Its essence is stack （Stack Class for some historical reasons , The use of , Use Deque Instead of ）;
• offerFirst/offerLast and pollFirst/pollLast It's a pair. , Derived from Deque, Its essence is double ended queue .

Then why these methods , All appear in LinkedList/Deque What about China? , That is caused by their inheritance , Please look at the chart below. .

image.png

Pay attention to the enclosed part , Interface Deque Inherited all the above methods , And category LinkedList All the above methods have been realized .
notes ： For historical reasons , stay Java in , The official does not recommend the use of Stack class , But use Deque Instead of , in other words , Interface Deque It is the aggregation of stack and double ended queue .

Said so much , What is the difference between these methods ？ In fact, we can quickly distinguish and remember their differences from their origins .

• add/remove From set , So add it to the end of the team , Remove... From the team leader ;
• offer/poll From queue （ fifo => The tail into the head ）, So add it to the end of the team , Remove... From the team leader ;
• push/pop From stack （ First in, then out => Head in and head out ）, So add it to the head of the team , Remove... From the team leader ;
• offerFirst/offerLast/pollFirst/pollLast From a double ended queue （ Both ends can enter or exit ）, According to the literal meaning ,offerFirst Add to the head of the team ,offerLast Add to the end of the team ,pollFirst Remove... From the team leader ,pollLast Delete from the end of the team .
  summary ：
• add/offer/offerLast Add a tail , The three methods are equivalent ;
• push/offerFirst Add team leader , The two methods are equivalent .
• remove/pop/poll/pollFirst Delete team head , The four methods are equivalent ;
• pollLast Delete end of team .

Although some methods are equivalent , But when we use it , It is suggested to use different methods according to the purpose , For example, you want to put LinkedList As a collection list, Then we should use add/remove, If you want to use it as a queue , Then use offer/poll, If used as a stack , Then use push/pop, If used as a double ended queue , Then use offerFirst/offerLast/pollFirst/pollLast. Use according to semantics , It won't happen ： I want to delete the tail of the team , As a result, the head of the team was deleted .

Out => The tail into the head ）, So add it to the end of the team , Remove... From the team leader ;

• push/pop From stack （ First in, then out => Head in and head out ）, So add it to the head of the team , Remove... From the team leader ;
• offerFirst/offerLast/pollFirst/pollLast From a double ended queue （ Both ends can enter or exit ）, According to the literal meaning ,offerFirst Add to the head of the team ,offerLast Add to the end of the team ,pollFirst Remove... From the team leader ,pollLast Delete from the end of the team .
  summary ：
• add/offer/offerLast Add a tail , The three methods are equivalent ;
• push/offerFirst Add team leader , The two methods are equivalent .
• remove/pop/poll/pollFirst Delete team head , The four methods are equivalent ;
• pollLast Delete end of team .

Although some methods are equivalent , But when we use it , It is suggested to use different methods according to the purpose , For example, you want to put LinkedList As a collection list, Then we should use add/remove, If you want to use it as a queue , Then use offer/poll, If used as a stack , Then use push/pop, If used as a double ended queue , Then use offerFirst/offerLast/pollFirst/pollLast. Use according to semantics , It won't happen ： I want to delete the tail of the team , As a result, the head of the team was deleted .