• preface

LinkedList is one of the common data structures, but many students have only heard of LinkedList, do not know what is a LinkedList, so this article will guide you to write a LinkedList, the source code will be a little different from the official, but the idea is about the same, and then lead you to read the official source code

To ease the source code and simplify generic code, handwritten LinkedList can only add String data

  • What is a linked list?

You can think of it as putting some data in order, holding hands and each data is a node, and all the nodes are connected together to form a linked list

  • Node definition of LinkedList

LinkedList is a double-linked list, so it has a left node and a right node. Let’s define an entity class that can be understood as a node

    /** * Node entity class */
    private static class NodeBean {
        NodeBean leftNode; / / the left node
        String value; // Node value
        NodeBean rightNode; / / right node
    }
Copy the code

  • How are nodes connected?

After looking at the above picture, we should probably know the method of connecting two nodes, we just need:

Right node = node 2. Left node = node 1Copy the code

Let’s first implement the add method of the linked list. The add method actually joins two nodes:

    /** * Add value */
    public void add(String value) {
        // Get the last node.
        NodeBean lastNode = this.lastNode;
        Create a new node
        NodeBean newNode = new NodeBean();
        // Assign a value to the node
        newNode.value = value;
        // The left node is the last node.
        newNode.leftNode = lastNode;
        // Add node, so the right node is null, can not write
        newNode.rightNode = null;
        // Change the last node of the member variable to the current new node
        this.lastNode = newNode;
        // Check whether the head node is empty
        if (this.firstNode == null) {
            // If it is null, the current node is the first node and the head node must be set to the current node
            this.firstNode = newNode;
        }else{
            // If not empty, you need to point the right node of the previous node to the current node
            // Two nodes are connected if:
            // 1. The right node of the previous node points to the current node
            // 2. The left node of the current node points to the previous node
            lastNode.rightNode = newNode;
        }
        // List length +1
        size++;
    }
Copy the code

  • How do I disconnect a node?

When two nodes are disconnected, the right node of the previous node points to the left node of the next node, and the left node of the next node points to the right node of the previous node

Note the direction of the arrow in the figure below, so that node 2 can be directly disconnected, and node 1 is directly connected to node 3. It is also obvious that the list can be added and deleted quickly, and only the front and back nodes can be disconnected

Let’s take a look at the code for the disconnected node:

Left node = NULL node 2. Right node = null node 1. Right node = node 3 Node 3. Left node = node 1 This disconnects the current node and reconnects the listCopy the code

Now we implement the remove(index) method to remove the specified node according to the index:

    /** * delete the value */
    public void remove(int index){here the code finds the node by index. To simplify the code, please ignore the code here to find the node by index. ***indexNode = find a node by index (index)// Get the left, right, and value of this node
        NodeBean leftNode = indexNode.leftNode;
        NodeBean rightNode = indexNode.rightNode;

        // Check whether the left node is empty. If it is empty, the current node is the first node (head node)
        if (leftNode == null) {
            this.firstNode = indexNode;
        }else{
            // The left node is not empty, you need to disconnect your own left node
            indexNode.leftNode = null;
            // Connect the right node of the previous node to the next node
            leftNode.rightNode = rightNode;
        }

        // Check whether the right node is empty. If it is empty, it is the last node (tail node)
        if (rightNode == null) {
            this.lastNode = indexNode;
        }else{
            // The right node is not empty, you need to disconnect your own right node
            indexNode.rightNode = null;
            // Connect the left node of the next node to the previous node
            rightNode.leftNode = leftNode;
        }

        // The current node value is null
        indexNode.value = null;
        size--;
    }
Copy the code

  • Find nodes by index

1. Select * from index; 2. Select * from index; 4. For each loop, move one node back from the beginningCopy the code

Now let’s implement the following get(index) method to get the top node by index:

    /** * Get the value of the node by index */
    public String get(int index){
        // Because the list has no index, it can only be searched one by one
        // Get the first node of the list (head node)
        NodeBean firstNode = this.firstNode;
        for (int i = 0; i < index; i++) {
            // Each loop moves one node back from the beginning
            firstNode = firstNode.rightNode;
        }
        // In order to simplify the code and make it easier to understand, we do not consider the case where tempNode is null
        return firstNode.value;
    }
Copy the code

  • conclusion

  1. There are connections between each node of the linked list. If you add a new node, you only need to insert it directly, so == new linked list is fast ==
  2. To disconnect a node from a list, you only need to reconnect the nodes before and after the list, so the list == delete quickly ==
  3. The linked list has no index, so the search needs to loop through the list, so the == query is slow

  • MyLinkedList complete code:

public class MyLinkedList {
    private int size; // The length of the current list
    private NodeBean firstNode; / / head node
    private NodeBean lastNode; / / end nodes

    /** * Add value */
    public void add(String value) {
        // Get the last node first
        NodeBean lastNode = this.lastNode;
        Create a new node
        NodeBean newNode = new NodeBean();
        // Assign a value to the node
        newNode.value = value;
        // The left node is the last node.
        newNode.leftNode = lastNode;
        // Add node, so the right node is null, can not write
        newNode.rightNode = null;
        // Change the last node of the member variable to the current new node
        this.lastNode = newNode;
        // Check whether the head node is empty
        if (this.firstNode == null) {
            // If it is null, the current node is the first node and the head node must be set to the current node
            this.firstNode = newNode;
        }else{
            // If not empty, you need to point the right node of the previous node to the current node
            // Two nodes are connected if:
            // 1. The right node of the previous node points to the current node
            // 2. The left node of the current node points to the previous node
            lastNode.rightNode = newNode;
        }
        // List length +1
        size++;
    }

    /** * delete the value */
    public void remove(int index){
        // Find the node corresponding to the current index
        // Because the list has no index, it can only be searched one by one
        // Get the first node of the list (head node)
        NodeBean indexNode = this.firstNode;
        for (int i = 0; i < index; i++) {
            // Each loop moves one node back from the beginning
            indexNode = indexNode.rightNode;
        }
        // Get the left, right, and value of this node
        NodeBean leftNode = indexNode.leftNode;
        NodeBean rightNode = indexNode.rightNode;

        // Check whether the left node is empty. If it is empty, the current node is the first node (head node)
        if (leftNode == null) {
            this.firstNode = indexNode;
        }else{
            // The left node is not empty, you need to disconnect your own left node
            indexNode.leftNode = null;
            // Connect the right node of the previous node to the next node
            leftNode.rightNode = rightNode;
        }

        // Check whether the right node is empty. If it is empty, it is the last node (tail node)
        if (rightNode == null) {
            this.lastNode = indexNode;
        }else{
            // The right node is not empty, you need to disconnect your own right node
            indexNode.rightNode = null;
            // Connect the left node of the next node to the previous node
            rightNode.leftNode = leftNode;
        }

        // The current node value is null
        indexNode.value = null;
        size--;
    }

    /** * Get the value of the node by index */
    public String get(int index){
        // Because the list has no index, it can only be searched one by one
        // Get the first node of the list (head node)
        NodeBean firstNode = this.firstNode;
        for (int i = 0; i < index; i++) {
            // Each loop moves one node back from the beginning
            firstNode = firstNode.rightNode;
        }
        // In order to simplify the code and make it easier to understand, we do not consider the case where tempNode is null
        return firstNode.value;
    }

    /** * get the list length */
    public int getSize(a){
        return this.size;
    }

    /** * Node entity class */
    private static class NodeBean {
        NodeBean leftNode; / / the left node
        String value; // Node value
        NodeBean rightNode; / / right node}}Copy the code

  • Focus on

  • If you read the above add delete check method, you can fully understand, you can continue to read
  • If you don’t understand, please copy the complete code above into the editor and explore it yourself

== If the above code understands, congratulations! Now you should be able to read the official source ==

  • Official Code parsing

  • Node entity class

    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; }}Copy the code

Code comparison

  • Insert the 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++;
    }
Copy the code

Code comparison

  • Disconnect the node

    E unlink(Node<E> x) {
        // assert x ! = null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
Copy the code

Code comparison

  • The final summary

  • If you can now read the three official methods, try reading the rest of them yourself, such as ==unlinkFirst() and linkFirst()==
  • Read the source code is not terrible, as long as you understand the source code ideas, suddenly enlightened