Data storage - single linked list

Data storage - single linked list

All codes are stored on gitee. See the following table for all source codes of this knowledge point: source code

First of all, we need to know what is a linked list through Baidu Encyclopedia Linked list We can know the definition of linked list: linked list is a discontinuous and non sequential storage structure on the physical storage unit, and the logical order of data elements is realized through the pointer link order in the linked list. The linked list is composed of a series of nodes (each element in the linked list is called a node), which can be generated dynamically at run time. Each node consists of two parts: one is the data field that stores the data element, and the other is the pointer field that stores the address of the next node. Compared with the linear table sequential structure, the operation is complex. Because it does not have to be stored in order, the complexity of the linked list can reach O(1) when inserting, which is much faster than that of another linear list sequential table, but it takes O(n) time to find a node or access a node with a specific number, while the corresponding time complexity of the linear table and the sequential table are O(logn) and O(1) respectively.

From this passage, we can know several knowledge points:

  • Discontinuous
  • Non sequential
  • Connected by pointer
  • High search time complexity
  • Low insertion time complexity

Single linked list

The source code of the single linked list is located in (source code / src/cn/tansanqinger/linked/SingleLinkedDemo.java)

Add data

First, let's look at the single linked list. The so-called single linked list can only read data from the beginning to the end, or add data at the end. All data are connected in a straight line.

[the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-0r2x1qhu-1601877874394) (C: \ users \ c3h2 \ appdata \ roaming \ typora \ typora user images \ image-20201005095613183. PNG)]

These are two nodes. They are connected by address, which means that the memory address of the next node is stored on the previous node, so that the previous node can obtain the next node through the node, which realizes the connection between multiple data. However, it should be noted that these connections are not continuous, because each node is random when opening up memory space, so they are not continuous. At the same time, because there is no data sorting processing, the order cannot be displayed. Some of my friends may not have touched C and C + +, so it may be easier for me to describe the pointer with memory address.

So how to achieve this?

First, let's look at how to save data

interface ISingleLink<T>{
    void add(T data);//Add data
}
class SingleLinkImpl<T> implements ISingleLink<T>{
    private Node root;//Starting address of linked list
    private Node end;//The last position of the linked list
    private int size;//Length of linked list
    public void add(T data){
        Node node = new Node(data);
        if(this.root==null){
            this.root = node;//Give the first node to the starting head of the linked list
            this.end = node;//The tail node is also the first
        } else {
            this.end.node = node;//The Node of the tail Node stores the next Node
            this.end = node;//Tail node backward
        }
        this.size++;//Linked list length + 1
    }
    private class Node<T>{
        private T data;//Save data
        private Node node;//Store the address of the next node
        private Node(T data){
            this.data = data;
        }
    }
}

Then the next step is to read the data. How to read it? First, we need to traverse all the data through the root node, root, and then return it through an array.

First, we need to add two methods to the ISingleLink interface:

interface ISingleLink<T>{
    void add(T data);//Add data
    int size();//Return linked list length
    T[] toArray();//Return data
}

The final results are as follows:

public int size() {
    return this.size;//Return linked list length
}

public T[] toArray() {
    if (this.size == 0) {//no data
        return null;
    } else {
        Object result[] = new Object[this.size];//Open array length
        Node list = root;
        int i = 0;
        while (list != null) {//Loop traversal
            result[i++] = list.data;
            list = list.node;
        }
        return (T[]) result;//Return results
    }
}

The next step is to check whether the linked list is available

public class  SimgleLinkDemo{
    public static void main(String[]args){
        SingleLinkImpl<String> singleLink=new SingleLinkImpl<>();
        singleLink.add("A");
        singleLink.add("B");
        singleLink.add("C");
        System.out.println(singleLink.size());
        System.out.println(Arrays.toString(singleLink.toArray()));
        }
}

The execution result is: [the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-kd3oti22-1601877874407) (C: \ users \ c3h2 \ appdata \ roaming \ typora \ typora user images \ image-20201005113159442. PNG)]

Delete data

A complete linked list should have four items of addition, deletion, modification and query. We have just completed the addition. Next, let's look at the deletion. First, let's analyze the principle

First, we want to delete a data. The first thing we need to do is find it. But one thing we need to pay attention to is that because we use a linked list, the two nodes are associated through addresses. If we want to delete a linked list, we should find its previous node. If we directly find the node to be deleted, we have to step back. But this is a one-way linked list. There is no way to find its upper node through a node. How do we delete this data after we find it? In fact, we only need to know how to add data to complete this problem. Because we delete a linked list, compared with removing a node in the linked list, the method used is nothing more than the address of the previous node, which is the address of the next node of the deleted node. Generally speaking, it means skipping it.

[the external chain image transfer fails, and the source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-lxmdp7qw-1601877874414) (C: \ users \ c3h2 \ appdata \ roaming \ typora user images \ image-20201005114425686. PNG)]

Knowing the principle, the next step is to realize it. First, add the T remove(int index) method in the interface. This method returns the deleted data. Of course, it can also not return.

public T remove(int index) {
    if(this.size==0 || this.size<=index || index<0){//Eliminate interference
        return null;
    } else if(index == 0){
        Object data = this.root.data;
        this.root = this.root.node;//Move the root node backward
        this.size--;//Linked list length - 1
        return (T)data;
    } else {
        Node list = root;//Get linked list
        while(index>1){ //Here, we cycle through the judgment of index to reduce variables
            list = list.node;//Pointer backward
            index --;
        }
        Node dataNode = list; //Used to get the value to delete
        Object data = dataNode.node.data;
        list.node = list.node.node;
        this.size--;
        return (T)data;
    }
}
//test
public static void main(String[]args){
    SingleLinkImpl<String> singleLink=new SingleLinkImpl<>();
    singleLink.add("A");
    singleLink.add("B");
    singleLink.add("C");
    System.out.println(singleLink.remove(0));
    System.out.println(singleLink.size());
    System.out.println(Arrays.toString(singleLink.toArray()));
}

[the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-yvartnze-1601877874421) (C: \ users \ c3h2 \ appdata \ roaming \ typora \ typora user images \ image-20201005121351211. PNG)]

Modify data

The modification of the linked list is similar to the above operations. The data to be modified is found first, and then the data is replaced to keep the structure of the linked list unchanged. Now let's add T set(int index, T data) method to the interface. The overall code is:

public T set(int index, T data) {
    if(this.size==0 || this.size<=index || index<0){//Eliminate interference
        return null;
    } else {
        Node list = root;//Get linked list
        while(index>0){
            list.node = list.node.node;
            index--;
        }
        Object dataNode = list.data;
        list.data = data;
        return (T)dataNode;
    }
}
//Test code
public static void main(String[]args){
    SingleLinkImpl<String> singleLink=new SingleLinkImpl<>();
    singleLink.add("A");
    singleLink.add("B");
    singleLink.add("C");
    System.out.println(singleLink.set(0,"D"));
    System.out.println(singleLink.size());
    System.out.println(Arrays.toString(singleLink.toArray()));
}

[the external chain image transfer fails, and the source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (IMG uhehcrbh-1601877874424) (C: \ users \ c3h2 \ appdata \ roaming \ typora user images \ image-20201005134454218. PNG)]

Query data

The query data has been written when adding data, but it is an overall query. Now we need to query a single data. First, add the T put(int index) method to the interface.

The implementation of the overall code is similar to the modified data, as follows:

public T put(int index) {
    if(this.size==0 || this.size<=index || index<0){//Eliminate interference
        return null;
    } else {
        Node list = root;//Get linked list
        while(index>0){
            list.node = list.node.node;
            index--;
        }
        return (T)list.data;
    }
}

summary

So far, the addition, deletion, modification and query of single linked list have been completed. It can also be found through the writing of code. In fact, compared with array, the amount of code is larger and the speed of querying data is slower, but the speed of deleting data is faster than array, so the developers need to consider how to select linked list and array.

The following is an example of my code optimization. You can also download the source code directly from gitee.

package cn.tansanqinger.linked;
import java.util.Arrays;
interface ISingleLink<T> {
    void add(T data);//Add data
    int size();//Return linked list length
    T[] toArray();//Return data
    T remove(int index);//Delete data
    T set(int index, T data);//Modify data
    T put(int index);//Query data
}
class SingleLinkImpl<T> implements ISingleLink<T> {
    private Node root;//Starting address of linked list
    private Node end;//The last position of the linked list
    private int size;//Length of linked list
    public void add(T data) {
        Node node = new Node(data);
        if (this.root == null) {
            this.root = node;//Give the first node to the starting head of the linked list
            this.end = node;//The tail node is also the first
        } else {
            this.end.node = node;//The Node of the tail Node stores the next Node
            this.end = node;//Tail node backward
        }
        this.size++;//Linked list length + 1
    }
    public int size() {
        return this.size;//Return linked list length
    }
    public T[] toArray() {
        if (this.size == 0) {//no data
            return null;
        } else {
            Object result[] = new Object[this.size];//Open array length
            Node list = root;
            int i = 0;
            while (list != null) {//Loop traversal
                result[i++] = list.data;
                list = list.node;
            }
            return (T[]) result;//Return results
        }
    }
    @Override
    public T remove(int index) {
        if(index == 0){
            Object data = this.root.data;
            this.root = this.root.node;//Move the root node backward
            this.size--;//Linked list length - 1
            return (T)data;
        } else{
            Node list = value(index-1);
            if(list!=null){
                Node dataNode = list; //Used to get the value to delete
                Object data = dataNode.node.data;
                list.node = list.node.node;
                this.size--;
                return (T)data;
            }
        }
        return null;
    }
    @Override
    public T set(int index, T data) {
        Node list = value(index);
        if(list!=null){
            Object dataNode = list.data;
            list.data = data;
            return (T)dataNode;
        }
        return null;
    }
    @Override
    public T put(int index) {
        Node list = value(index);
        if (list!=null){
            return (T)list.data;
        }
        return null;
    }
    private Node value(int index){
        if(this.size==0 || this.size<=index || index<0){//Eliminate interference
            return null;
        } else {
            Node list = root;//Get linked list
            while(index>0){
                list.node = list.node.node;
                index--;
            }
            return list;
        }
    }
    private class Node<T> {
        private T data;//Save data
        private Node node;//Store the address of the next node

        private Node(T data) {
            this.data = data;
        }
    }
}
public class  SimgleLinkDemo{
    public static void main(String[]args){
        SingleLinkImpl<String> singleLink=new SingleLinkImpl<>();
        singleLink.add("A");
        singleLink.add("B");
        singleLink.add("C");
        System.out.println(singleLink.remove(1));
        System.out.println(singleLink.size());
        System.out.println(Arrays.toString(singleLink.toArray()));
    }
}

Tags: Java linked list Singly Linked List

Posted by gskurski on Fri, 13 May 2022 15:12:04 +0300