当前位置:网站首页>Brief analysis of LinkedList source code

Brief analysis of LinkedList source code

2020-11-09 22:19:27 Think about it

1 LinkedList brief introduction

LinkedList It's an implementation <font color="red">List Interface </font> and <font color="red">Deque Interface </font> Of <font color="red"> Double ended linked list </font>.

<img src="https://img-blog.csdnimg.cn/20201108105348736.png" />

LinkedList Inherited from AbstractSequentialList, Realized ListDequeCloneablejava.io.Serializable Interface .

LinkedList Realized List Interface , It shows that it can insert and delete the linked list efficiently .
LinkedList Realized Deque Interface , That can be LinkedList Used as a double-ended queue .
LinkedList It's done Cloneable Interface , That overrides the function clone(), Be able to clone .
LinkedList Realized java.io.Serializable Interface , It means LinkedList Support serialization , Can transmit data through serialization .

LinkedList Not thread safe , If you want to make LinkedList Become thread safe , Static classes can be called Collections Class synchronizedList Method

List list=Collections.synchronizedList(new LinkedList(...));

2 Member attribute

//  Total nodes 
transient int size = 0;
//  Head node 
transient Node<E> first;
//  Tail node 
transient Node<E> last;

You can find LinkedList It is based on bidirectional linked list , Use Node Store linked list node information .

    private static class Node<E> {
        E item;// Node values 
        Node<E> next;//  The subsequent nodes 
        Node<E> prev;//  Precursor node 

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

therefore LinkedList The structure is as follows :

3 Construction method

//  The construction method of empty parameter , Only objects are generated 
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    //  First construct an empty linked list 
    this();
    //  add to Collection The elements in 
    addAll(c);
}

4 Common methods

4.1 Additive elements

add(E e) : Add elements to the end of the list

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

    /**
     *  Linking makes e As the last element .
     */
    void linkLast(E e) {
        //  Find the current tail node 
        final Node<E> l = last;
        //  Build new nodes , The precursor node of this node is the last tail node 
        final Node<E> newNode = new Node<>(l, e, null);
        //  The newly created node is used as the end node of the current linked list 
        last = newNode;
        if (l == null)
            first = newNode;//  If the tail node is empty , So the list is empty , Then take the newly built node as the head node 
        else
            l.next = newNode;//  If it's not empty , Then set the post node of the tail node before adding as our new tail node 
        size++;
        modCount++;
    }

add(int index,E e): Add the element in the specified position

public void add(int index, E element) {
        checkPositionIndex(index);//  Check index index Is it in [0-size] Between 

        if (index == size)
            linkLast(element);//  Add to the end of the list 
        else 
            linkBefore(element, node(index));//  Insert into index In front of the node of the indicated position 
    }
    
    /**
     *  Insert a new node in front of the specified node 
     */
    void linkBefore(E e, Node<E> succ) {
        //  Take out the previous node at the specified location 
        final Node<E> pred = succ.prev;
        //  Build new nodes ,pred The precursor node of the specified location ,succ The specified location ,e It's the added element 
        final Node<E> newNode = new Node<>(pred, e, succ);
        //  The predecessor node of the specified node points to the node to be inserted .
        succ.prev = newNode;
        //  If the predecessor node of the specified location is empty , That is, the designated location succ It's the head node , namely newNode Set as head node 
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode; //  Not empty , The post node of the previous node in the original position is set as the new node .
        size++;
        modCount++;
    }

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

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;//  Check index index Is it in [0-size] Between 
    }

addAll(Collection c ): Insert the collection elements into the linked list

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

public boolean addAll(int index, Collection<? extends E> c) {
        // 1、 Check index Whether the scope is in size within 
        checkPositionIndex(index);

        // 2、 Save the data of the set in the object array 
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        // 3、 The precursor node and successor node of the insertion position are obtained 
        Node<E> pred, succ;
        //  If the insertion position is tail , The precursor node is last, The subsequent nodes are null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //  otherwise , call node() Method to get the successor node , And then we get the precursor node 
        else {
            succ = node(index);
            pred = succ.prev;
        }

        // 4、 Traversing data and inserting data into 
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //  Create a new node 
            Node<E> newNode = new Node<>(pred, e, null);
            //  If the insertion position is at the head of the list 
            if (pred == null)
                //  Point the previous node backward newNode
                first = newNode;
            else
                pred.next = newNode;
            //  stay if-else outside , If there is no such sentence ,pred A node is a fixed node , So the nodes need to be replaced in each cycle 
            pred = newNode;
        }

        //  If the insertion position is at the tail , Reset last node 
        if (succ == null) {
            last = pred;
        }
        //  The inserted list is linked to the previous list 
        else {
            pred.next = succ;
            succ.prev = pred;
        }

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

addFirst(E e): Add elements to the head of the list

 public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        //  Find the current head node 
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//  The new node , Take the front node as the successor node 
        //  The new node is the head node 
        first = newNode;
        //  If the list is empty ,last Nodes also point to new nodes 
        if (f == null)
            last = newNode;
        //  otherwise , Point the leading pointer of the preceding node to the new node , That is to say, the next element 
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

addLast(E e): Add elements to the end of the list , And add(E e) The method is the same

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

4.2 Look for the element

get(int index): Returns data according to the specified index

public E get(int index) {
        //  Check index Is it in a legal position 
        checkElementIndex(index);
        //  call Node(index) Go find index Corresponding node Then return its value item
        return node(index).item;
    }

Get the header node (index=0) Data method :

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

difference :
getFirst() and element() Method will be used when the linked list is empty , Throw an exception ;

element() The internal part of the method is to use getFirst() Realized . They will be when the list is empty , Throw out NoSuchElementException .

Get tail node (index=-1) Data method :

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

Difference between them :
getLast() Method when the linked list is empty , Will throw out NoSuchElementException; and peekLast() It's just going back to null.

4.3 Remove elements

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

difference : removeLast() When the linked list is empty NoSuchElementException;pollLast() Method returns null.

remove(Object o): Deletes the specified element

public boolean remove(Object o) {
        //  If you want to delete the object as 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;
    }

When deleting the specified object , Just call remove(Object o) that will do , However, this method will only delete one matching object at a time , If you delete the matching object , return true, otherwise false.

unlink(Node<E> x) Method : Delete the specified node

E unlink(Node<E> x) {
        final E element = x.item;
        //  obtain x Successor node 
        final Node<E> next = x.next;
        //  obtain x The precursor node of 
        final Node<E> prev = x.prev;

        // x It's the head node 
        if (prev == null) {
            //  If the deleted node is the head node , Make the head node point to the successor node of the node 
            first = next;
        } else {
            //  Point the successor node of the precursor node to x Successor node 
            prev.next = next;
            //  Delete x The front of 
            x.prev = null;
        }

        // x It's the tail node 
        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;
        }
        
        //  Delete the content of the specified node 
        x.item = null;
        size--;
        modCount++;
        return element;
    }

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

4.4 Modifying elements

set(int index, E element) Method : Modify the specified node element

    public E set(int index, E element) {
        //  Check for out of line 
        checkElementIndex(index);
        //  Find nodes by index 
        Node<E> x = node(index);
        // oldVal Store what needs to be changed 
        E oldVal = x.item;
        x.item = element;
        //  Returns the value before the change 
        return oldVal;
    }

5 ArrayList And LinkedList similarities and differences

similarities and differences ArrayList LinkedList
Whether thread safety is guaranteed no no
Whether insertion and deletion are affected by the location of the element yes no
Whether to support fast random access yes no
Is it implemented RandomAccess Interface yes no
Underlying data structure Object Array Double linked list (JDK1.6 It was a circular list ,JDK1.7 The loop was canceled )
Memory footprint The expansion mechanism leads to list A certain amount of space will be reserved at the end of the list Each element costs extra to store the next / The space of the precursor

Reference resources

LinkedList Source code analysis ( One )

LinkedList Source code analysis ( Two )

版权声明
本文为[Think about it]所创,转载请带上原文链接,感谢