Foreword

In the previous two sections, we introduced ArrayList in detail. The first is to implement the ArrayList data structure by hand, but to analyze the ArrayList source code to see the built-in implementation. As for the content of the collection, as always, we continue to learn the collection of LinkedList. Then go and see how the LinkedList source code is implemented, let’s get started.

Getting started with LinkedList

LinkedList uses a double-linked list data structure to store data. Unlike ArrayList, ArrayList is a linear structure in the true physical sense, and LinkedList is also a linear linked list. It only needs to manually link the data of the nodes before and after. However, the double-linked list and the single-linked list are only different in structure, but the double-linked list has one more precursor node, and there is no difference in the other. So what exactly is a double-linked list? Such examples are everywhere in our daily life. For example, our music player should be considered more visual, as follows:

Java_entry_series_[8]_Principles_of_doubly_linked_list_algorithm_0.png

Custom implementation of single linked list

Next, we implement a single-linked list, and then transform the single-linked list into a double-linked list. We see the player above. The single-linked list only has fewer predecessors, but there are successor nodes (as written above), so we need to define a node. , And then on this node there is a reference to the next node (a pointer in C or C ++), and the data stored by the current node, so we define the following generic node class:

 

 

public  class Node <T> {

    // Current node value 
    public T data;

    // Subsequent node 
    public Node next;

    public Node (T data) {
         this .data = data;
    }
}

 

 

The next step is to define a linked list to manipulate the above node classes and store data. Here we do a little simpler, there will be a head node and a tail node in the linked list. Here, we operate by the head node, and wait for us to upgrade to the double linked list Then we define the tail node, so there are two variables, the head node and the length of the linked list, in the singly linked list, as follows:

 

 

public  class MyLinkedList <T> {

    // head node 
    private Node head;

    // link list element length 
    private  int length;

}

 

 

Warm reminder: I wo n’t give you a drawing to demonstrate here. I ’ll make up for it by myself. If I feel like I ’m going around, I can understand it by drawing on the drawing board or paper. First we need to consider the head and tail nodes, that is, the first song and the last song in the player, and then add songs to the specified position and form a song list by concatenating next. Stringed. Then we finish adding the first song to the player list. At this time, we should think about whether the head node has added the first song. If it does not exist, then instantiate the head node directly. If the first node already exists, Song, we will re-instantiate a song, and then assign the reference of the first song it has added to the newly added song next, so we have the following method:

 

 

// Add to the head node 
public  void addToHead (T data) {
         if (head == null ) {
            head = new Node (data);
        } else {
            Node temp = head;
            head = new Node (data);
            head.next = temp;
        }
        length ++ ;
}

 

 

Alright, put the newly added song in the first song. We’re completely done. Then we add the last song to the song list. At this time, do we know that it is the last song? This is the last song, and this is the basis of judgment. I don’t need to explain it too much, so there are the following methods:

 

 

// Add to the tail node 
public  void addToTail (T data) {
        Node temp = head;
         while (temp.next! = Null ) {
            temp = temp.next;
        }
        temp.next = new Node (data);
        length ++ ;
}

 

 

The determination of the single linked list is here. We can only loop through to find the last one, and then add the corresponding song, so when the amount of data is large enough, we can think of its performance. Next is the most important piece. We want to add songs under the specified song. At this time, it involves finding the corresponding song index and adding data.

 

 

    // Add to the specified index element 
    public  void add ( int index, T data) {
         if (index <0 ) {
             throw  new RuntimeException ("illegal index" );
        }
        if (index> length) {
             throw  new RuntimeException ("out of index boundary" );
        }
        if (head == null || index == 0 ) {
            addToHead (data);
            return ;
        }
        // Head node 
        Node temp = head;
         //         Node holder next to the specified index 
;
         for ( int i = 0; i <index-1 && temp.next! = Null ; i ++ ) {
            temp = temp.next;
        }
        // the specified node is not the next node is inserted into the index 
        Holder = temp.next;
         // the specified index node to be inserted next node i.e. node 
        temp.next = new new the Node (Data);
         // the specified index of the next node in the list The node reference points to the specified node to be inserted (in this case, the node under the specified index is the node to be inserted, and then the next node is the node to be inserted) 
        temp.next.next = holder;
        length ++ ;
    }

 

 

The next step is to find the element according to the specified index. I won’t explain it, just go to the code, as follows

 

 

    // Find elements based on index 
    public T find ( int index) {
         if (index <0 ) {
             throw  new RuntimeException ("illegal index" );
        }
        if (length == 0 || index> length) {
             throw  new RuntimeException ("out of index boundary" );
        }
        Node temp = head;
         for ( int i = 0; i <index; i ++ ) {
            temp = temp.next;
        }
        return (T) temp.data;
    }

 

 

Finally, the old rule rewrites the toString method to print the linked list data, as follows:

 

 

    // link list element size 
    public  int size () {
         return length;
    }

    @Override
    public String toString () {
        StringBuilder sb = new StringBuilder ();
        Node temp = head;
         while (temp! = Null ) {
            sb.append (temp.data);
            sb.append ( "," );
            temp = temp.next;
        }
        if (sb.charAt (sb.length ()-1) == ',' ) {
            sb.delete (sb.length () -1 , sb.length ());
        }
        return sb.toString ();
    }

 

 

Finally, let’s add a song to the player list for a test, let’s go, as follows:

 

 

public  class Main {

    public  static  void main (String [] args) {
        MyLinkedList <Integer> list = new MyLinkedList <> ();
         // Add element 11 to the head node 
        list.addToHead (11 );
        System.out.println (list);

        // Add element 15 to the tail node 
        list.addToTail (15 );
        System.out.println (list);

        // Add element 12 to the head node 
        list.addToHead (12 );
        System.out.println (list);

        // Add element 13 to the head node 
        list.addToHead (13 );
        System.out.println (list);

        // Add element 8 to the tail node 
        list.addToTail (8 );
         // Add element 7 to the tail node 
        list.addToTail (7 );
        list.add ( 2, 9 );
        System.out.println (list);

        // Add element 9 at index 2 
        list.add (2, 9 );
        System.out.println (list);

        // Delete the element with index 4 
        list.delete (4 );
        System.out.println (list);
    }
}

 

 

Java_entry_series_[8]_Principles_of_doubly_linked_list_algorithm_1.png

Custom implementation of double linked list

With the preparation of the single-linked list as above, it is very easy to implement the double-linked list again, but it only adds the predecessor node and the tail node in the linked list. Going forward, we add the predecessor node to the node class, as follows:

 

 

public  class Node <T> {

    // Current node value 
    public T data;

    // predecessor node 
    public Node previous;

    // Subsequent node 
    public Node next;

    public Node (T data) {
         this .data = data;
    }
}

 

 

Similarly, we add the tail node field to the linked list class, as follows:

 

 

public  class MyLinkedList <T> {
     // head node 
    private Node head;

    // Tail node 
    private Node tail;

    // link list element length 
    private  int length;
}

 

 

Similarly, when adding songs to the first position, we also need to initialize the head node at this time, but this time there is a tail node, it does not matter. At this time, the head node is the tail node. We encapsulate a method to initialize the head node and the tail node. as follows:

 

 

 // Initialize the head and tail nodes 
    void initHead (T data) {
         // Initialize the head node 
        head = new Node (data);
         // At this time, the tail node is the head node 
        tail = head;
}

 

 

Then when adding songs to the head node, there is only one more predecessor node, and a corresponding line of code is added, that is, the predecessor node to which the first song has been added is assigned to the first song to be added, as follows:

 

 

    // Add elements to the head node 
    public  void addToHead (T data) {
         if (head == null ) {
            initHead (data);
        } else {
            Node temp = head;
            head = new Node (data);
            head.next = temp;
            temp.previous = head;
        }
        length ++ ;
    }

 

 

When adding songs to the last position, it is slightly different from the above single-linked list. The single-linked list is directly traversed. Here we define the tail node, so you can directly manipulate the tail node, as follows:

 

 

    // Add to the tail node 
    public  void addToTail (T data) {
         if (size () == 0 ) {
            initHead (data);
        } else {
            Node temp = tail;
            tail = new Node (data);
            temp.next = tail;
            tail.previous = temp;
        }
        length ++ ;
    }

 

 

Next is the core method of adding the specified index element. In fact, it is very simple. I have written the comments for you, but I still do n’t understand.

 

 

    // Add the specified index element 
    public  void add ( int index, T data) {
         if (index <0 ) {
             throw  new RuntimeException ("illegal index" );
        }
        if (index> length) {
             throw  new RuntimeException ("out of index boundary" );
        }
        if (head == null || index == 0 ) {
            initHead (data);
            return ;
        }
        // Head node 
        Node temp = head;
         // Defines to get the next node 
        holder of the specified index node ;
         for ( int i = 0; i <index-1 && temp.next! = Null ; i ++ ) {
            temp = temp.next;
        }
        // The next node of the current node 
        holder = temp.next;
         // The next node to be added 
        temp.next = new Node (data);
         // The successor node of the inserted node is the current node next node 
        temp.next.next = holder;
         // The current node's next precursor node is the insert node 
        temp.next.next.previous = temp.next;
        length ++ ;
    }

 

 

Whether it’s the most important thing to add or delete, we need to think clearly about who the predecessor node and the successor node are pointed to when adding and deleting. If you think about this problem, there will be nothing. Go with you, delete method:

 

 

    // Delete the specified index element 
    public  void delete ( int index) {
         if (index <0 ) {
             throw  new RuntimeException ("illegal index" );
        }
        if (length == 0 || index> length) {
             throw  new RuntimeException ("out of index boundary" );
        }
        Node temp = head;
         for ( int i = 0; i <index-1 && temp.next! = Null ; i ++ ) {
            temp = temp.next;
        }
        temp.next.next.previous = temp;
        temp.next = temp.next.next;
        length - ;
    }

 

 

In order to verify the code we have written, we print out the predecessor and successor nodes of the corresponding node, as follows:

 

 

    public  int size () {
         return length;
    }

    @Override
    public String toString () {
        StringBuilder sb = new StringBuilder ();
        Node temp = head;
         while (temp! = Null ) {
            sb.append (temp.data);
            sb.append ( "," );
             if (temp.previous! = null && temp.next! = null ) {
                System.out.println (temp.previous.data + "<-(" + temp.data + ")->" + temp.next.data);
            }
            temp = temp.next;
        }
        if (sb.charAt (sb.length ()-1) == ',' ) {
            sb.delete (sb.length () -1 , sb.length ());
        }
        return sb.toString ();
    }

 

 

The console test data is the same as in the singly linked list, and the result data is as follows (of course, we can print the corresponding node predecessor and successor nodes to verify it. It is also broad. I also verified it here, so there are no problems):

Java_entry_series_[8]_Principles_of_doubly_linked_list_algorithm_2.png

Summary

In this section, we have implemented single-linked and double-linked lists through handwritten code. It is still very simple. In the next section, we analyze the LinkedList source code in detail. Thank you 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/11455832.html