Simple simulation of the implementation of two-way chain table in idle time, when you consolidate your knowledge and deepen your understanding, many people say that you can't bear eight-part articles, which is normal, because you can't understand its principle without experiencing the bottom implementation, so you can easily forget it when you have a dry back eight-part articles.

Introduction to Chain List

LinkedList, which is a two-way Chain table, is a common list in a collection where each node holds the data of the upper and lower nodes, allowing us to traverse them in the reverse and forward direction.

Chain List Simulation

Needless to say, we started simulating and looked at the bottom of the LinkedList and knew that when using LinkedList, data is not stored directly in the LinkedList, but encapsulated using its internal class Node (source code display):

// LinkedList's Internal Node Class
private static class Node<E> {
    E item; // Stored element Ontology
    Node<E> next; // Next node of the node where the element is located
    Node<E> prev; // The previous node of the node where the element is located
    
    // The constructor of a node
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

So all we have to do is implement the overall structure of the list first (here I implement the class name myself and add Sim to distinguish it)

// LinkedList Chain List Simulation Class
public class LinkedListSim {
    // First node of chain table
    NodeSim first;
    // End of chain list
    NodeSim last;
    // Record the length of the chain table
    int size;

    // Node node impersonation class (setter/getter implementation omitted)
    private static class NodeSim { 
        Object date; // Element Ontology
        NodeSim next; // Last Node
        NodeSim prev; // Next Node

        @Override
        public String toString() {
            return "NodeSim{" +
                    "prev=" + prev +
                    ", next=" + next +
                    ", data=" + data +
                    '}';
        }
    }
}

A simple two-way chain table simulation class is completed. In fact, it is not complex to simulate the structure of a chain table, but if there is only one chain table structure, it is not enough, so it is worthless to not use it.

crud

increase

To make the chain table flexible, we need to make it have basic CRUD operations, first implement its add() method

/**
 * Add Elements
 * @param data Elements to be added
 */
public void add(Object data) {
    // Encapsulate data as Node node
    NodeSim node = new NodeSim();
    node.setData(data);
    // If first is null, the first element is added
    if (first == null) {
        // Because it is the first element, the first and last nodes are all it, and it has no upper and lower nodes
        node.setPrev(null);
        node.setNext(null);
        first = node;
        last = node;
    } else {
        // Otherwise, the element has been added
        node.setPrev(last); // The current tail node is the previous node of the new element
        node.setNext(null); // This node is the end node so there is no next node
        // The next node of the current endpoint changes to that node
        last.setNext(node);
        // Current End Changed to New End
        last = node;
    }
    size ++;
}

After implementing the add() method, we test it with debug to see if the element can be successfully saved. We break the breakpoint here and use the debug interface to see if the first node is "a" and the end node is "c"

When the breakpoint goes down a step, that is, when all the data is added, we find that the data saved by the first and last nodes in the chain table is as expected. To be sure, we open the next node of the first node and the prev node of the end node to see if it is the intermediate element "b"

As shown in the diagram, as expected, each node that stores elements correctly saves its upper and lower nodes

                

Find

We know that LinkedList and ArrayList look up in a completely different way, depending on how they are implemented at the bottom. ArrayList uses arrays at the bottom, so the feature is to support random subscript access, whereas LinkedList is implemented at the bottom as a chain table, which does not support subscript access. Can java provide us with subscript lookup for LinkedList, why?

The reason is simple: LinkedList's subscript lookup is not really through subscripts, but traverses the current node's next node one by one from the first node until the target result is obtained after traversing to index

(Because a list of chains, except first and last, does not directly know where the node is in the list, it can only start with first or last)

First and last node

Well, after talking about the native LinkedList, let's implement the lookup class api for our own chain list. We know that there are two key attributes in the LinkedList chain table, first and last, which store the first and last nodes of the whole chain table directly, so no matter how long the chain table is, when we only want to get the first and last nodes, it's as efficient and time consuming (so it's very fast to get directly).

/**
 * Get the first node element
 * @return First Node Element
 */
public Object getFirst() {
    return first.getData();
}

/**
 * Get End Element
 * @return End element
 */
public Object getLast() {
    return last.getData();
}

Chain List Length

Viewing the number (length) of elements in a collection is also a required function, but it is very simple for a chain table, simply returning the size in the attribute

/**
 * Get Link List Length
 * @return Chain List Length
 */
public int getSize() {
    return size;
}

Subscript Lookup

It is impossible for a collection to look only at its length or at its end and end nodes, so we need it to support subscript lookup (not real subscripts).

/**
 * Gets the element through the subscript
 * @param index The element subscript
 * @return This element
 */
public Object get(int index) {
    // If the lookup subscript is 0, the first node is found, and the first node is returned directly
    if (index == 0) {
        return getFirst();
    } else if (index == (size - 1)) {
        //If Find Subscript is Chain List Total Length-1 then Find End, Return to End
        return getLast();
    }

    // Get Chain Header Element
    NodeSim node = first;
    for (int i = 0; i < index; i++) {
        node = node.getNext(); // Take the next node of this node
    }
    // Target elements are obtained by traversing through index next s
    return node.getData();
}

test

After implementing several key api s, we'll do a unified test to see if we get the right results

(I won't debug it for convenience, just print it)

test data

LinkedListSim link = new LinkedListSim();
    link.add("a");
    link.add("b");
    link.add("c");
    link.add("d");
    link.add("e");
    link.add("f");

test1

Get the chain length getSize() and get the first and last node getFirst()/getLast()

System.out.println("Chain list length:" + link.getSize());
System.out.println("First element:" + link.getFirst());
System.out.println("Tail element:" + link.getLast());

Result Display

 test2

Gets an index element specified in the chain table

System.out.println("Get the element with subscript 0:" + link.get(0)); // It's equivalent to getting the first node
System.out.println("Get the element with subscript 3:" + link.get(3));

We know that index=0 represents the first element of the set (the first node in the chain table), which has been optimized in the get() method implementation above, and when we look for it, if index equals the first and last nodes, we can simply go back to the first and last nodes.

Simulation Complete

In this LinkedList chain table simulation, I have carried out a simple addition and lookup operation. Have you been inspired? If in doubt you can leave your frustration in the comments, if you have any insights you can try to challenge yourself to implement and test changes and deletions to see if you can do it on your own