We know that arrays require a contiguous chunk of memory to store data, and that two elements of an array that are logically contiguous are also physically contiguous. A linked list, on the other hand, does not require a contiguative memory space. Instead, it uses Pointers to string together a set of scattered memory blocks. We call this block of memory a Node.

In order to string all the nodes together, each node in the list, in addition to storing data, needs to store a pointer to the next node. So the list has two storage areas, in which the storage domain of data is called the data domain, and the storage domain of the next node storage location is called the pointer domain.

Singly linked lists

We add a node before the first node, called the head node. The data field of the head node can store no information, or it can store additional information such as the length of the list. The head node is used to record the base address of the list, and with the head node we can iterate through the whole list. The final node is called the tail node, and its pointer field next points not to the next node, but to the NULL address NULL.

How nodes are represented in Java

class Node {
  Item item;
  Node next;
}
Copy the code

A Node object contains two instance variables, one for the data field Item and the other for the pointer field Node.

Like arrays, linked lists support find, insert, and delete operations.

Single linked list lookup operation

Since the data in a linked list is not stored contiguously, we cannot directly calculate the corresponding memory address from the first address and the subscript, as in an array. The linked list can only find the corresponding node according to the head node one by one backward traversal.

For example, if we want to find the node with index 1 in the linked list above (node A, b and C with index 0, 1, 2), we only need to walk backwards 2 times according to the head node.

Node node(int index) {
    Node tmp = head;
    for(int i = 0; i <= index; i++) {
        tmp = tmp.next;
    }
    return tmp;
}
Copy the code
Insertion of a single linked list

Normally, we append elements to the end of a linked list. The process is simple, as follows:

First, according to the head node in order to find the tail node traversal, the pointer field of the tail node to the new node.

public boolean add(Integer item) {
    Node newNode = new Node(item, null);
    // TMP points to the header node
    Node tmp = head;

    while(tmp.next ! =null) {
        tmp = tmp.next;
    }
    tmp.next = newNode;
    size++;

    return true;
}

Copy the code

If we need to insert a node at the specified index of the list, for example, insert a node at index 1, that is, insert a node between node A and node B, the procedure is as follows:

First of all, according to the head node to find the node a, the pointer field of a node points to aa, and then the pointer field of AA node points to b.

public boolean add(int index, Integer item) {
    if(index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
    Node newNode = new Node(item, null);

    Node tmp = head;
    // Find the node of the index before the specified index
    for(int i = 0; i < index; i++) {
        tmp = tmp.next;
    }
    // Specify the original node at the index position
    Node node = tmp.next;

    tmp.next = newNode;
    newNode.next = node;
    size++;

    return true;
}
Copy the code
The deletion of a single linked list

To delete a node from the specified index position, for example, b, the process is as follows:

According to the head node in turn backward traversal, find the node a before node B, the pointer field next of node A points to the node C after node B.

public Integer remove(int index) {
    this.checkIndex(index);
    // Find the node before the node to delete
    Node tmp = head;
    for(int i = 0; i < index; i++) {
        tmp = tmp.next;
    }
    // The node to be deleted
    Node node = tmp.next;
    // The pointer field of the previous node points to the next node with the deleted node
    tmp.next = node.next;

    size--;

    Integer val = node.item;
    node.item = null;

    return val;
}
Copy the code

The above single linked list search, insert and delete operation complete code is as follows:

public class SingleLinkedList {

    / / head node
    private Node head;

    // The actual number of elements in the list
    private int size;

    public SingleLinkedList(a) {
        this.head = new Node();
        this.size = 0;
    }

    /** * Insert element * at the end of the list@param item
     * @return* /
    public boolean add(Integer item) {
        Node newNode = new Node(item, null);
        // TMP points to the header node
        Node tmp = head;

        while(tmp.next ! =null) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
        size++;

        return true;
    }

    /** insert element * at the specified index@paramIndex starts from 0 *@param item
     * @return* /
    public boolean add(int index, Integer item) {
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        Node newNode = new Node(item, null);

        Node tmp = head;
        // Find the node of the index before the specified index
        for(int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        // Specify the original node at the index position
        Node node = tmp.next;

        tmp.next = newNode;
        newNode.next = node;
        size++;

        return true;
    }

    /** * returns the element * at the specified position@param index
     * @return* /
    public Integer get(int index) {
        this.checkIndex(index);

        Node node = this.node(index);
        return node.item;
    }

    /** * delete node * at the specified index position@param index
     * @return* /
    public Integer remove(int index) {
        this.checkIndex(index);
        // Find the node before the node to delete
        Node tmp = head;
        for(int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        // The node to be deleted
        Node node = tmp.next;
        // The pointer field of the previous node points to the next node with the deleted node
        tmp.next = node.next;

        size--;

        Integer val = node.item;
        node.item = null;

        return val;
    }


    /** * change the value of the node * at the specified position@param index
     * @param item
     * @return* /
    public Integer set(int index, Integer item) {
        this.checkIndex(index);
        Node node = this.node(index);
        Integer oldVal = node.item;
        // Replace with the new value
        node.item = item;

        return oldVal;
    }

    /** * Iterates over elements */
    public void list(a) {
        Node tmp = head;
        while(tmp.next ! =null) { tmp = tmp.next; System.out.println(tmp.item); }}/** * return number of linked list elements *@return* /
    public int size(a) {
        return size;
    }

    Node node(int index) {
        Node tmp = head;
        for(int i = 0; i <= index; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }

    private void checkIndex(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); }}private static class Node {

        private Integer item;

        private Node next;

        public Node(a) {}public Node(Integer item, Node next) {
            this.item = item;
            this.next = next; }}}Copy the code

“More exciting content please follow the public geekymv, like please share with more friends oh”