Detailed explanation of the underlying implementation and principle of LinkedList data structure

[[420549]]

Preface

In daily development, collections are a data structure that we often use. Of course, there is not only one kind of collection, and there is no so-called best collection, only the most suitable one;

Of course, as senior programmers, we must not only know how to use it, but also understand the principles behind it;

Today we will talk about the underlying implementation and principle of LinkedList

1. Introduction to LinkedList

 public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io. Serializable  
 {
    //length
 transient int   size = 0;
 //Point to the head node
 transient Node<E> first ;
 //Point to the end node
 transient Node<E> last ;
 }

1. Overview of LinkedList

LinkedList implements both List interface and Deque counterparts, which means it can be regarded as a sequential container, a queue, and a stack.

In this way, linkedList is simply invincible. When you need to use a stack or a queue, you can consider using LinkedList. On the one hand, Java officials have stated that they do not recommend the use of the Stack class. What's more regrettable is that there is no class called Queue in Java (it's just the name of an interface).

Regarding stacks or queues, ArrayDeque is now the first choice, which has better performance than LinkedList (when used as a stack or queue);

The implementation of LinkedList determines that all operations related to the following table are linear time, and deleting elements at the beginning or end only takes constant time. In pursuit of efficiency, LinkedList is not synchronized. If multiple threads need to access it concurrently, you can first use Collections.synchronizedList() method to wrap it.

2. Data Structure

Inheritance

 java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractList<E>
            java.util.AbstractSequentialList<E>
                java.util.LinkedList<E>

Implementing the interface

 Serializable , Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Basic Properties

• transient int size = 0; //The number of elements stored in LinkedList
• transient Node first; //head node
• transient Node last; //tail node
• Collection interface: The Collection interface is the root node of all collection classes. Collection represents a rule, and all classes that implement the Collection interface follow this rule.

Inherited classes and implemented interfaces

• List interface: List is a sub-interface of Collection. It is a collection with ordered elements (maintaining the order of elements in the order of insertion), repeatable, and nullable
• AbstractCollection class: The skeleton implementation class of the Collection interface, which minimizes the workload required to implement the Collection interface
• AbstractList class: a skeleton implementation class of the List interface, minimizing the workload required to implement the List interface
• Cloneable interface: Classes that implement this interface can explicitly call the Object.clone() method to legally copy fields of the class instance. If the Object.clone() method is called on an instance that does not implement the Cloneable interface, a CloneNotSupportException will be thrown. Normally, classes that implement the Cloneable interface will override Object.clone() with a public method.
• Serializable interface: Implementing this interface indicates that the class can be serialized and deserialized. Detailed explanation of query serialization
• Deque interface: Deque defines a linear Collection that supports inserting and deleting elements at both ends. Deque is actually the abbreviation of "double ended queue". Most implementations of the Deque interface do not limit the number of elements, but this queue supports both implementations with capacity restrictions and implementations without capacity restrictions. For example, LinkedList is an implementation with capacity restrictions, and its maximum capacity is Integer.MAX_VALUE
• AbstractSequentialList class: Provides a skeleton implementation of the List interface, minimizing the work required to implement this interface supported by "continuous access" data storage (such as linked lists). For random access data (such as arrays), AbstractList should be used in preference to the AbstractSequentailList class.

2. Analysis of underlying source code

LinkedList is implemented by a doubly linked list. Since it is a linked list, its random access efficiency is lower than that of ArrayList, and its sequential access efficiency is relatively high. Each node has a predecessor (a pointer to the previous node) and a successor (a pointer to the next node).

The effect is as follows:

The source code is marked as follows:

public class LinkedList<E>extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io. Serializable  
 {
 transient int   size = 0; //The number of elements stored in LinkedList
 transient Node<E> first ; //head node
 transient Node<E> last ; // tail node
 //Constructor, create an empty list
 public LinkedList() {
 }
 //Add a specified collection to LinkedList, complete initialization first, then call the add operation
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
 //Insert the head node
    private void linkFirst(E e) {
 final Node<E> f = first ; //Assign the head node to the f node
 //new a new node, this node's data = e, pre = null , next - > f
        final Node<E> newNode = new Node<>( null , e, f);
 first = newNode; //Copy the newly created node address to first  
 if (f == null ) //f == null , indicating that the LinkedList is empty at this time
 last = newNode; //Assign the newly created node to last  
 else  
 f.prev = newNode; //Otherwise f.prev points to newNode
 size ++;
 modCount++;
 }
 //Insert the tail node
 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++;
 }
 //Insert the e node before the succ node and modify the predecessor and successor between each node
    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++;
 }
 //Delete the head node
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null ;
        final E element = f.item;
        final Node<E> next = f. next ;
 f.item = null ;
        f. next = null ; // help GC
 first = next ;
 if ( next == null )
 last = null ;
 else  
 next .prev = null ;
 size --;  
 modCount++;
 return element;
 }
 //Delete the tail node
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null ;
        final E element = l.item;
        final Node<E> prev = l.prev;
 l.item = null ;
        l.prev = null ; // help GC
 last = prev;
 if (prev == null )
 first = null ;
 else  
            prev.next = null ;
 size --;  
 modCount++;
 return element;
 }
 //Delete the specified node
 E unlink(Node<E> x) {
 // assert x != null ;
        final E element = x.item;
 final Node<E> next = x.next ; //Get the predecessor of the specified node
 final Node<E> prev = x.prev; //Get the successor of the specified node
 if (prev == null ) {
 first = next ; //If the predecessor is null , it means this node is the head node
 } else {
 prev.next = next ; //The successor node of the predecessor node points to the successor node of the current node
 x.prev = null ; //The predecessor of the current node is empty
 }
 if ( next == null ) { //If the successor node of the current node is null , it means that this node is the tail node
 last = prev;
 } else {
 next .prev = prev; //The predecessor of the successor node of the current node points to the predecessor node of the current node
 x.next = null ; //The successor of the current node is empty
 }
 x.item = null ; //The element of the current node is set to null , waiting for garbage collection
 size --;  
 modCount++;
 return element;
 }
 //Get the first node information in LinkedList
 public E getFirst() {
        final Node<E> f = first ;
 if (f == null )
            throw new NoSuchElementException();
 return f.item;
 }
 //Get the last node information in LinkedList
 public E getLast() {
        final Node<E> l = last ;
 if (l == null )
            throw new NoSuchElementException();
 return l.item;
 }
 //Delete the head node
 public E removeFirst() {
        final Node<E> f = first ;
 if (f == null )
            throw new NoSuchElementException();
 return unlinkFirst(f);
 }
 //Delete the tail node
 public E removeLast() {
        final Node<E> l = last ;
 if (l == null )
            throw new NoSuchElementException();
 return unlinkLast(l);
 }
 //Set the added element as the head node of LinkedList
 public void addFirst(E e) {
 linkFirst(e);
 }
 //Set the added element as the tail node of LinkedList
 public void addLast(E e) {
 linkLast(e);
 }
 //Judge whether LinkedList contains the specified element
 public boolean contains (Object o) {
 return indexOf(o) != -1;
 }
 // Return the number of elements in the List
 public   int   size () {
 return   size ;
 }
 //Add elements to the end of LinkedList
 public boolean add (E e) {
 linkLast(e);
 return   true ;
 }
 //Delete the specified element
 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 ;
 }
 //Add the elements in the collection to the List
 public boolean addAll(Collection<? extends E> c) {
 return addAll( size , c);
 }
 //Insert all elements in the collection into the List, starting from the specified position
 public boolean addAll( int   index , Collection<? extends E> c) {
        checkPositionIndex( index );
 Object[] a = c.toArray(); //Convert the collection into an array
 int numNew = a.length; //Get the number of elements in the collection
 if (numNew == 0) //There is no element in the collection, return false  
 return   false ;
 Node<E> pred, succ;
        if ( index == size ) {
 succ = null ;
 pred = last ;
 } else {
 succ = node( index ); //Get the node element at position index and assign it to succ
 pred = succ.prev;
 }
 for (Object o : a) { //Traverse the array to insert. Modify the predecessor and successor of the node
            @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 ;
 }
 //Delete all elements in the List
 public void clear() {
 // Clearing all   of the links between nodes is   "unnecessary" , but:
        // - helps a generational GC if the discarded nodes inhabit
        // more than one generation
 // - is sure to   free memory even if there is a reachable Iterator
 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++;
 }
 //Get the element at the specified position
 public E get( int   index ) {
        checkElementIndex( index );
 return node( index ).item;
 }
 //Prevent the node from being in the specified position
 public E set ( int   index , E element) {
        checkElementIndex( index );
        Node<E> x = node( index );
 E oldVal = x.item;
 x.item = element;
 return oldVal;
 }
 //Place the node at the specified location
 public void add ( int   index , E element) {
        checkPositionIndex( index );
 if ( index == size )
            linkLast(element);
 else  
            linkBefore(element, node( index ));
 }
 //Delete the element at the specified position
 public E remove( int   index ) {
        checkElementIndex( index );
 return unlink(node( index ));
 }
 // Check if the index is legal
    private boolean isElementIndex( int   index ) {
 return   index >= 0 && index < size ;
 }
 // Check if the location is legal
    private boolean isPositionIndex( int   index ) {
 return   index >= 0 && index <= size ;
 }
 //Index overflow information
    private String outOfBoundsMsg( int   index ) {
 return   "Index: " + index + ", Size: " + size ;
 }
 // Check if the node is legal
    private void checkElementIndex( int   index ) {
        if (!isElementIndex( index ))
            throw new IndexOutOfBoundsException(outOfBoundsMsg( index ));
 }
 // Check if the location is legal
    private void checkPositionIndex( int   index ) {
        if (!isPositionIndex( index ))
            throw new IndexOutOfBoundsException(outOfBoundsMsg( index ));
 }
 //Return the node information of the specified location
 //LinkedList cannot be accessed randomly, and the corresponding node can only be found by traversing
 //In order to improve efficiency, the current position is first judged from the middle position of the number of elements. If it is smaller than the middle position,
 //Start traversing from the head node, if it is greater than the middle position, start traversing from the tail node
 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;
 }
 }
 // Returns the position of the first occurrence of the specified element
 public   int indexOf(Object o) {
 int   index = 0;
 if (o == null ) {
 for (Node<E> x = first ; x != null ; x = x. next ) {
                if (x.item == null )
 return   index ;
 index ++;
 }
 } else {
 for (Node<E> x = first ; x != null ; x = x. next ) {
                if (o.equals(x.item))
 return   index ;
 index ++;
 }
 }
 return -1;
 }
 // Return the position of the last occurrence of an element
 public   int lastIndexOf(Object o) {
 int   index = size ;
 if (o == null ) {
 for (Node<E> x = last ; x != null ; x = x.prev) {
 index --;  
                if (x.item == null )
 return   index ;
 }
 } else {
 for (Node<E> x = last ; x != null ; x = x.prev) {
 index --;  
                if (o.equals(x.item))
 return   index ;
 }
 }
 return -1;
 }
 // Pop up the value of the first element
 public E peek() {
        final Node<E> f = first ;
 return (f == null ) ? null : f.item;
 }
 //Get the first element
 public E element() {
 return getFirst();
 }
 // Pop up the first element and delete it
 public E poll() {
        final Node<E> f = first ;
 return (f == null ) ? null : unlinkFirst(f);
 }
 //Delete the first element
 public E remove() {
 return removeFirst();
 }
 //Add to the end
 public boolean offer(E e) {
 return   add (e);
 }
 //Add to the header
 public boolean offerFirst(E e) {
 addFirst(e);
 return   true ;
 }
 //Insert to the last element
 public boolean offerLast(E e) {
 addLast(e);
 return   true ;
 }
 //Queue operation
 //Try to pop the first element, but do not delete the element
 public E peekFirst() {
        final Node<E> f = first ;
 return (f == null ) ? null : f.item;
 }
 //Queue operation
 //Try to pop the last element without deleting it
 public E peekLast() {
        final Node<E> l = last ;
 return (l == null ) ? null : l.item;
 }
 // Pop up the first element and delete it
 public E pollFirst() {
        final Node<E> f = first ;
 return (f == null ) ? null : unlinkFirst(f);
 }
 // Pop up the last element and delete it
 public E pollLast() {
        final Node<E> l = last ;
 return (l == null ) ? null : unlinkLast(l);
 }
 //If the queue is added to the head
 public void push(E e) {
 addFirst(e);
 }
 //Delete the first node from the queue
 public E pop() {
 return removeFirst();
 }
 //Delete the first occurrence of the specified element
 public boolean removeFirstOccurrence(Object o) {
 return remove(o);
 }
 //Delete the last occurrence of the specified element
 public boolean removeLastOccurrence(Object o) {
 if (o == null ) {
 for (Node<E> x = last ; x != null ; x = x.prev) {
                if (x.item == null ) {
                    unlink(x);
 return   true ;
 }
 }
 } else {
 for (Node<E> x = last ; x != null ; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
 return   true ;
 }
 }
 }
 return   false ;
 }
 //Traversal method
 public ListIterator<E> listIterator( int   index ) {
        checkPositionIndex( index );
 return new ListItr( index );
 }
 //Internal class, implementing the ListIterator interface
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned = null ;
        private Node<E> next ;
        private int nextIndex;
        private int expectedModCount = modCount;
 ListItr( int   index ) {
            // assert isPositionIndex( index );
 next = ( index == size ) ? null : node( index );
            nextIndex = index ;
 }
 public boolean hasNext() {
 return nextIndex < size ;
 }
 public E next () {
            checkForCommodification();
 if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next ;
 next = next . next ;
 nextIndex++;
 return lastReturned.item;
 }
 public boolean hasPrevious() {
 return nextIndex > 0;
 }
 public E previous() {
            checkForCommodification();
            if (!hasPrevious())
                throw new NoSuchElementException();
            lastReturned = next = ( next == null ) ? last : next .prev;
 nextIndex --;  
 return lastReturned.item;
 }
 public   int nextIndex() {
 return nextIndex;
 }
 public   int previousIndex() {
 return nextIndex - 1;
 }
 public void remove() {
            checkForCommodification();
            if (lastReturned == null )
                throw new IllegalStateException();
            Node<E> lastNext = lastReturned. next ;
            unlink(lastReturned);
            if ( next == lastReturned)
 next = lastNext;
 else  
 nextIndex --;  
            lastReturned = null ;
            expectedModCount++;
 }
 public void set (E e) {
            if (lastReturned == null )
                throw new IllegalStateException();
            checkForCommodification();
            lastReturned.item = e;
 }
 public void add (E e) {
            checkForCommodification();
            lastReturned = null ;
            if( next == null )
 linkLast(e);
 else  
                linkBefore(e, next );
 nextIndex++;
            expectedModCount++;
 }
        final void checkForCommodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
 }
 }
 //Static inner class, create 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;
 }
 }
 /**
 * @since 1.6
 */
 public Iterator<E> descendingIterator() {
 return new DescendingIterator();
 }
 /**
     * Adapter to provide descending iterators via ListItr.previous
 */
    private class DescendingIterator implements Iterator<E> {
        private final ListItr itr = new ListItr( size ());
 public boolean hasNext() {
 return itr.hasPrevious();
 }
 public E next () {
 return itr.previous();
 }
 public void remove() {
 itr.remove();
 }
 }
    @SuppressWarnings( "unchecked" )
    private LinkedList<E> superClone() {
 try {
 return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
 }
 }
 /**
     * Returns a shallow copy of this {@code LinkedList}. (The elements
     * themselves are not cloned.)
 *
     * @ return a shallow copy of this {@code LinkedList} instance
 */
 public Object clone() {
        LinkedList<E> clone = superClone();
 // Put clone into   "virgin" state
        clone.first = clone.last = null ;
 clone.size = 0;
 clone.modCount = 0;
        // Initialize clone with our elements
 for (Node<E> x = first ; x != null ; x = x. next )
            clone.add (x.item);
 return clone;
 }
 public Object[] toArray() {
        Object[] result = new Object[ size ];
 int i = 0;
 for (Node<E> x = first ; x != null ; x = x. next )
            result[i++] = x.item;
 return result;
 }
    @SuppressWarnings( "unchecked" )
 public <T> T[] toArray(T[] a) {
 if (a.length < size )
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size );
 int i = 0;
 Object[] result = a;
 for (Node<E> x = first ; x != null ; x = x. next )
            result[i++] = x.item;
 if (a.length > size )
            a[ size ] = null ;
 return a;
 }
    private static final long serialVersionUID = 876323262645176354L;
 //Write the object to the output stream
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
 // Write out   any hidden serialization magic
        s.defaultWriteObject();
 // Write out   size  
 s.writeInt( size );
 // Write out   all elements in the proper order .
 for (Node<E> x = first ; x != null ; x = x. next )
            s.writeObject(x.item);
 }
 //Read the object from the input stream
    @SuppressWarnings( "unchecked" )
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
 // Read   in   any hidden serialization magic
        s.defaultReadObject();
 // Read   in   size  
 int   size = s.readInt();
 // Read   in   all elements in the proper order .
 for ( int i = 0; i < size ; i++)
            linkLast((E)s.readObject());
 }
 }

1. Construction method

 LinkedList()
 LinkedList(Collection<? extends E> c)

LinkedList has no concept of length, so there is no problem of insufficient capacity, so there is no need to provide a constructor to initialize the size. Therefore, two methods are provided, one is a no-parameter constructor to initialize a LinkedList object, and the other is a constructor that converts the specified collection element into a LinkedList.

2. Add nodes

 public boolean add (E e) {
 linkLast(e);
 return   true ;
 }
 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++;
 }

From the source code, we can see that the adding process is as follows:

• Record the current end node by constructing another pointer l pointing to the end node
• Generate a new node: Note that since it is added at the end of the linked list, next is null
• last points to the new node
• There is a judgment here. My understanding is to judge whether it is the first element (when l==null, it means there is no node in the linked list).
• Then it is easy to understand this judgment. If it is the first node, use first to point to this node. If not, the next of the current node points to the newly added node.
• Increase the size: Add element "D" to the LinkedList["A","B","C"] mentioned above. The process is roughly as shown in the figure:

3. Delete nodes

LinkedList provides two methods to delete nodes

 //Method 1. Delete the node at the specified index
 public E remove( int   index ) {
 // Check if the index is correct
    checkElementIndex( index );
 //There are two steps here, first locate the node by index, second delete the node
 return unlink(node( index ));
 }
 //Method 2. Delete the node with the specified value
 public boolean remove(Object o) {
 // Check if the deleted element is null  
 if (o == null ) {
 //If it is null , traverse and delete
 for (Node<E> x = first ; x != null ; x = x. next ) {
            if (x.item == null ) {
 unlink(x);
 return   true ;
 }
 }
 } else {
 //If it is not a traversal deletion
 for (Node<E> x = first ; x != null ; x = x. next ) {
            if (o.equals(x.item)) {
 unlink(x);
 return   true ;
 }
 }
 }
 return   false ;
 }

From the source code, we can see that both methods are deleted through unlink()

• Get the current value of the element to be deleted, a reference to the node before it, and a reference to the node after it.
• Determine whether the deleted node is the first node. If so, first moves backward. If not, point the previous node of the current node, next, to the next node after the current node.
• Determine whether the deleted node is the last node. If so, move last forward. If not, point the prev of the node after the current node to the node before the current node.
• Set the value of the current node to null
• The size is reduced and the value of the deleted node is returned

3. Differences between ArrayList and LinkedList

1. Bottom-level implementation: ArrayList is implemented as an array, while LinkedList is implemented as a doubly linked list structure;

2. Interface implementation: Both implement the List interface and are linear list implementations. ArrayList implements RandomAccess to support random element access, while LinkedList implements Deque to be used as a queue.

3. Performance: ArrayList needs to copy the original array when adding or deleting elements, while LinkedList only needs to move the pointer to find elements. ArrayList supports random element access, while LinkedList can only traverse one node at a time.

4. Thread safety: All are thread unsafe;

5. The performance of inserting and deleting in LinkedList is better than that in ArrayList. This is because ArrayList needs extra overhead to move and copy elements when inserting and deleting elements (but the traversal and deletion shown in the removeElements2 method is very fast. This method deletes from the end, without moving or copying elements, so the speed is very fast);

6.ArrayList is inferior to LinkedList in terms of performance in querying elements;

Summarize

LinkedList is a very powerful class that can be used as a List collection, a double-ended queue, and a stack. LinkedList uses a linked list at the bottom to store the elements in the collection, so the performance of random access is poor, but the performance of insertion and deletion is very good.

This article is reproduced from the WeChat public account "Android Development Programming"