Foreword

In the previous section, we implemented the single-linked list and the double-linked list by hand. In this section, we will look at how the source code is implemented and what can be optimized compared to manual implementation.

LinkedList source code analysis

Through the explanation of the principle of the double linked list in the previous section, we also know that the implementation of the double linked list algorithm has the following characteristics by comparing the following figure.

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_0.png

1. Each link in the linked list is an object (also called an element, a node, etc.). 2. Each object contains a reference (address) to the position of the next object. 3. The predecessor node in the linked list points to the head of the linked list, and the subsequent nodes in the linked list point to the null, indicating the tail of the linked list. 4. The link list can grow and shrink dynamically at run time (program run time, after compilation), and is limited only by available physical memory.

Let’s first take a look at what actionable methods LinkedList provides us, as follows:

 

 

        LinkedList <String> list = new LinkedList ();

        // Add elements to the tail node 
        list.add ("str" );
         // Add elements to the specified index node 
        list.add (1, "str" );
         // Add elements to the head node 
        list.addFirst ("first" ) ;
         // Add elements to the tail node 
        list.addLast ("last" );

        // Returns the specified index element 
        list.get (1 );
         // returns the head node element 
        list.getFirst ();
         // returns the tail node element 
        list.getLast ();

        // Add elements to the tail node 
        list.offer ("str" );
         // Add elements to the head node 
        list.offerFirst ("str" );
         // Add elements to the tail node 
        list.offerLast ("str");

 

 

First let’s see what variables are defined in LinkedList. First, the operation of the node element defines the node inner class in this class, because the node class is not used elsewhere. This is no different from the node class defined in the previous section.

 

 

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

 

 

Let’s take a look at the definition of the linked list as follows:

 

 

public  class LinkedList <E>
     extends AbstractSequentialList <E>
     implements List <E>, Deque <E> , Cloneable, java.io.Serializable
{

    // link list length 
    transient  int size = 0 ;

    // Linked list head node 
    transient Node <E> first;

    // Linked list tail node 
    transient Node <E> last;

    // Constructor 
    public LinkedList () {
    }

    // Constructor passes a collection for conversion 
    public LinkedList (Collection <? Extends E> c) {
         this ();
        addAll (c);
    }
}

 

 

The doubly linked list class we defined above inherits the corresponding class and implements the corresponding interface. We summarize it through a graph, as follows:

 

Then, as shown in the previous figure and the previous section, we explained the basic principles of the double linked list. We first give the characteristics of the double linked list in the source code, as follows:

1. Can be used as a queue, deque or a stack. Because List has been implemented as a queue, and Queue and Deque interfaces have also been implemented as double-ended queues or stacks. 2. All elements are allowed and can contain duplicates and NULL. LinkedList maintains the insertion order of elements. 4. Non-thread safe. If multiple threads access the linked list at the same time, and if one thread structurally modifies the list, you must synchronize externally and use Collections.synchronizedList (new LinkedList ()) to get the synchronized linked list. 5. Iterators support Fail-Fast, which may throw ConcurrentModificationException. 6. RandomAccess interface is not implemented. So it doesn’t support random access to elements, we can only access elements sequentially.

Since we implemented its basic principles in the previous section, implementing a double-linked list in java just provides us with more operable methods, such as inserting elements at the head and tail nodes, which is the same. Here we do not The source code has been posted one by one. The insertion of elements at the specified index is better than ours. In the previous section, we used the loop traversal method for the inserted elements at the specified index. At the same time, we only used the successor node. In Java, it How is it handled? Let’s analyze the source code:

 

 

// Specified index insert element 
public  void add ( int index, E element) {
         // Check if the insert index position exceeds the boundary, otherwise throw an exception 
        checkPositionIndex (index);

        // If the insertion index and the linked list are equal in length, insert the tail node 
        if (index == size)
            linkLast (element);
        else 
            // Otherwise insert an element at the specified index 
            linkBefore (element, node (index));
}

 

 

Next, let’s continue to see if it is not the insertion of the tail node, then insert the specified index position, how does it handle it?

 

 

// Insert element after node succ 
void linkBefore (E e, Node <E> succ) {
     // Define the precursor node of succ node 
    final Node <E> pred = succ.prev;
     // Instantiate the node to insert the element 
    final Node <E> newNode = new Node <> (pred, e, succ);
     // The predecessor node of the inserted element is succ 
    succ.prev = newNode;
     if (pred == null )
         // If the predecessor of succ is null , Indicating that the head node is the head node 
        first = newNode;
     else 
        // Other nodes that are to be inserted into the node with the specified index are the nodes that insert the element 
        pred.next = newNode;
    size ++ ;
    modCount ++ ;
}


// Get the node with the specified index 
Node <E> node ( int index) {

    // If the index position is less than half the length of the linked list, the index element is cyclically searched from the head node to the subsequent node 
    if (index <(size >> 1 )) {
        Node <E> x = first;
         for ( int i = 0; i <index; i ++ )
            x = x.next;
         return x;
    } else {
         // Otherwise, the index element is searched in a loop from the tail node to the predecessor node 
        Node <E> x = last;
         for ( int i = size-1; i> index; i-- )
            x = x.prev;
         return x;
    }
}

 

 

It can be seen from the above that we manually specified the index insertion element in the previous section, which is more clever and better performance in java, because the specified index and the half of the length of the linked list can be used as the basis for judgment to find the specified index faster node. By looking at the source code, we will find that the add corresponding offer method is inserted into the tail node, the addFirst corresponding offerFirst is inserted into the head node, and the addLast corresponding offerLast is inserted into the tail node.

. As long as we understand the basic principles of the algorithm, it is actually very simple to look at the source code, it is just a comparison to see if there is a better way to implement it. We have stopped here for source code analysis. Here we need to emphasize that one of the characteristics of the double-linked list is the fast failure mechanism and Fail-Fast. Here we use examples to illustrate.

Fail-Fast VS Fail-Safe

Fast iteration fails-When we try to modify the internal structure of the collection while iterating, it throws ConcurrentModificationException, which is a failed fast iterator. Let’s look at the following example

 

 

        LinkedList <String> listObject = new LinkedList <> ();

        listObject.add ( "ram" );
        listObject.add ( "mohan" );
        listObject.add ( "shyam" );
        listObject.add ( "mohan" );
        listObject.add ( "ram" );

        Iterator it = listObject.iterator ();

        while (it.hasNext ()) {
            listObject.add ( "raju" );
            System.out.println (it.next ());
        }

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_1.png

Before discussing further, we analyze why this exception occurs, and we notice the problem of the exception stack starting from the next () method. In the next () method, there is another method checkForComodification (), which throws a ConcurrentModificationException according to certain conditions. Next, let’s see what happens in the next () and checkForComodification () methods.

 final  void checkForComodification () {
             if (modCount! = expectedModCount)
                 throw  new ConcurrentModificationException ();
 }

Inside the checkForComodification () method, if modcount is not equal to expectedModCount, a ConcurrentModificationException (extended RuntimException) is thrown. According to the above, when we execute listObject.add (“raju”) in the loop, the value of modCount becomes 6 but the value of expectedCount is still 5, which is why we get ConcurrentModificationException. So it seems that we encountered a problem in the next () method when iterating. Obviously this processing method is undoubtedly correct. If we don’t use the next method to print elements, we use the enhanced for loop to try.

 

 

        LinkedList <String> listObject = new LinkedList <> ();

        listObject.add ( "ram" );
        listObject.add ( "mohan" );
        listObject.add ( "shyam" );
        listObject.add ( "mohan" );
        listObject.add ( "ram" );

        for (String s: listObject) {
            listObject.add ( "raju" );
            System.out.println (s);
        }

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_2.png

We still get ConcurrentModificationException  by using the enhanced for loop , why is this? We did not use Iterator for iteration. From the stack information as above, we know that even if we use the enhanced for loop, the internal next () method will be called. In JDK 1.5, some new classes (CopyOnWriteArrayList, CopyOnWriteArraySet, ConcurrentHashMap, etc.) will not throw ConcurrentModificationException, even if we modify the structure of List, Set or Map during iteration. These classes are used to clone or copy the collection Object.

 

 

        List <String> listObject = new CopyOnWriteArrayList <> ();

        listObject.add ( "ram" );
        listObject.add ( "mohan" );
        listObject.add ( "shyam" );
        listObject.add ( "mohan" );
        listObject.add ( "ram" );

        Iterator it = listObject.iterator ();

        while (it.hasNext ()) {
            listObject.add ( "raju" );
            System.out.println (it.next ());
        }

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_3.png

Next we summarize the differences between Fail-Fast and Fail Safe, as follows:




Serial numberFail FastFail Safe



1.
Fail fast applied to collection objects
Apply to clones or collections of copies.


2.
When iterating, we will throw ConcurrentModificationException when modifying the collection elements
Will not throw any exception


3.
Requires less memory
Requires additional memory


4.
When ArrayList, HashSet, HashMap, etc. are used
When CopyOnWriteArrayList, ConcurrentHashMap, etc. are used


Converting Arrays to LinkedList

Let’s see how to convert an array to a LinkedList or how to convert a Linkedlist to an array in Java.

 

 

        LinkedList <String> linkedList = new LinkedList <> ();

        linkedList.add ( "A" );
        linkedList.add ( "B" );
        linkedList.add ( "C" );
        linkedList.add ( "D" );

        // 1. LinkedList to Array 
        String array [] = new String [linkedList.size ()];
        linkedList.toArray (array);

        System.out.println (Arrays.toString (array));

        // 2. Array to LinkedList 
       LinkedList <String> linkedListNew = new LinkedList <> (Arrays.asList (array));

        System.out.println (linkedListNew);

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_4.png

LinkedList sort

We can use the Collections.sort () method to sort the linked list. For custom sorting of objects, we can use the Collections.sort (linked List, comparator) method. as follows:

 

 

        LinkedList <String> linkedList = new LinkedList <> ();

        linkedList.add ( "A" );
        linkedList.add ( "C" );
        linkedList.add ( "B" );
        linkedList.add ( "D" );

        // Unsorted 
        System.out.println (linkedList);

        // 1. Sort the list 
        Collections.sort (linkedList);

        // Sorted 
        System.out.println (linkedList);

        // 2. Custom sorting 
        Collections.sort (linkedList, Collections.reverseOrder ());
        linkedList.sort (Collections.reverseOrder ());

        // Custom sorted 
        System.out.println (linkedList);

 

 

Java_Entry_Series_[9]_LinkedList_source_code_analysis_5.png

LinkedList VS ArrayList

In the Java LinkedList class, the operation is fast because no conversion is required, basically all the add and delete methods provide very good performance O (1). The time complexity of LinkedList common methods is summarized as follows:

  • add (E element): O (1).
  • get (int index) and add (int index, E element): O (N).
  • remove (int index): O (N).
  • Iterator.remove (): O (1).
  • ListIterator.add (E element): O (1).

Earlier we also analyzed the ArrayList source code in detail. As follows, we analyze and compare LinkedList and ArraryList in detail, as follows:

1. ArrayList uses dynamic expansion to adjust the size of the array. LinkedList is implemented using doubly linked lists. 2. ArrayList allows random access to its elements, while LinkedList does not. It can only access the nodes in the linked list in order, so accessing specific nodes will be slow. 3. LinkedList also implements the Queue interface, which adds more methods than ArrayList, such as offer, peek, poll, etc. 4. Compared with LinkedList, ArrayList is slower in adding and removing, but faster in get, because if the array is full in LinkedList, you do not need to adjust the size of the array and copy the contents to the new array. 5. LinkedList has more memory overhead than ArrayList, because in ArrayList, each index holds only the actual object, but in the case of LinkedList, each node holds the data and address of the successor node and the predecessor node.

In summary, LinkedList seems useless, so when can we use LinkedList? I think it can be considered from the following three aspects

1. No random access to any particular element is required. 2. Need to insert and delete frequently. 3. Not sure how many items are in the linked list.

Summary

In this section, we analyze the LinkedList source code slightly, and then compare the advantages and disadvantages of ArrayList and LinkedList, and when should we use LinkedList. Except in rare cases, LinkedList is unlikely to be used in most cases. Well, in this section we go to So far, in the next section we enter Hashtable. Thanks for reading, see you in the next section.

 

Java entry series [1] string creation method

Java entry series [2] string features

Java entry series [3] stringbuilder string buffer

Java entry series [4] packaging class

Java entry series [5] inheritance abstract classes interfaceson

Java entry series [6] Principles of dynamic array

Java entry series [7] collection arraylist

Java entry series [8] principles of doubley linked list alogrithm

Java entry series [9] linkedlist source code analysis

Java entry series [10] Hash algorithm principle

Java entry series [11] Hashtable source code analysis

Java entry series [12] Hashcode and equals

Java entry series [13] Principles of the read-black tree algorithmn method

Java entry series [14] Hashmap source code ananlysis

Orignal link:https://www.cnblogs.com/CreateMyself/p/11503548.html