Java language description -- Design and implementation of single linked list -- data structure

Data structure -- Design and implementation of single linked list

First understand its definition:
Single linked list: if each node is set with only one pointer member pointing to the subsequent node, such a linked list is called linear one-way linked list, or single linked list for short.
What is a pointer member? In the linked list, each node contains not only the information of the element itself (called data member), but also the information of the logical relationship between the elements.
Pointer member: a node contains the address information of subsequent nodes or the address information of predecessor nodes, which is called pointer member.
Similar to the pointer in C language, the pointer in C language stores the address value; However, the concept of pointer does not exist in Java. The pointer members here store the references of subsequent nodes or precursor nodes, and the references still store their corresponding address values. Different concepts and the same functions.

After understanding the concept of single linked list, let's look at the corresponding diagram:
The single linked list has only one header node and does not store data when initializing the header node. There is only one next node pointing to null:


For each node head, s, s1... I don't directly use the box instead. My understanding is that each new node object contains all the contents of its corresponding construction method by default. When you want to find and add content to the construction method, the memory space allocated by the corresponding object is also more. The use of ellipse embedded boxes here is also based on my own understanding. For my understanding of constructors, see Last issue , the article contains my understanding of the constructor and the implementation of the sequence table.

Then we will learn how to establish connections between members of a single linked list. There are two specific ways to establish connections:
Table building by head inserting method: the corresponding diagram is:


The picture text is a little small, you can zoom in. The process is all in the picture

Corresponding code:

//Establishing single linked list by head interpolation
    public void GreatLoneList(Object[] a){
        LoneListOne<Object> s;
        for (int i = 0; i < a.length; i++) {
            s = new LoneListOne<>(a[i]);
            s.next = head.next;
            head.next = s;
        }
    }

Table building by tail interpolation method: the corresponding diagram is:

Corresponding code:

//Creating tables by tail interpolation
    public void GreatLoneListEnd(Object[] a){
        LoneListOne<Object> s,t;
        t = head;
        for (int i = 0; i < a.length; i++) {
            s = new LoneListOne<>(a[i]);
            t.next = s;
            t = s;
        }
        t.next = null;
    }

Tail interpolation is more in line with our usual operation, and its code is also more concise

After understanding the implementation principle and method of single linked list, we can focus on the implementation of all basic modules of the whole single linked list:
Three classes need to be created to realize the single linked list, and the specific functions will be explained later Write a class to establish node structure:

class LoneListOne<Object>{
    Object data;
    LoneListOne<Object> next;
    //Establish a single chain header node model
    public LoneListOne(){
        next = null;
    }
    //Establish the data node model of single linked list
    public LoneListOne(Object d){
        data = d;
        next = null;
    }
}

The head node does not store data initially, and only has a null pointer member null.

  1. II Write another class to initialize the header node and realize the basic functions of the single linked list (add, delete, modify and query):
  • 1. Create a header node:
  •  //Create header node
        LoneListOne<Object> head = new LoneListOne<>();
    
  • 2. Code implementation of header insertion method:
  • //Establishing single linked list by head interpolation
        public void GreatLoneList(Object[] a){
            LoneListOne<Object> s;
            for (int i = 0; i < a.length; i++) {
                s = new LoneListOne<>(a[i]);
                s.next = head.next;
                head.next = s;
            }
        }
    
    3. Code implementation of tail interpolation method:
    //Creating tables by tail interpolation
        public void GreatLoneListEnd(Object[] a){
            LoneListOne<Object> s,t;
            t = head;
            for (int i = 0; i < a.length; i++) {
                s = new LoneListOne<>(a[i]);
                t.next = s;
                t = s;
            }
            t.next = null;
        }
    
  • 4. Find the length of the single linked list:
  • //Find the length of linear table
        public int size(){
            LoneListOne<Object> p = head;
            int count = 0;
            while(p.next!=null){
                count++;
                p = p.next;
            }
            return count;
        }
    
  • 5. The code implements adding elements to the single linked list:
  • //Add: add an element to the end of the single linked list
        public void Add(Object e){
            LoneListOne<Object> p = head;
            LoneListOne<Object> s = new LoneListOne<>(e);
            while(p.next!=null){
                p = p.next;
                p.next = s;
            }
        }
    
  • 6. The code implements the deletion of elements in the single linked list: when deleting an element, first find the location of its node, and then change its direction
    1). Find node
  • //Find the node with sequence number i and prepare for deletion
        public LoneListOne<Object> geti(int i){
            LoneListOne<Object> p = head;
            int j = -1;
            while(j<i){
                j++;
                p = p.next;
            }
            return p;
        }
    

    2). Delete element

    //Delete: delete the ith element in the single linked list
        public void Delete(int i,Object e){
            if (i<0 ||i>size()-1) {
                throw new IllegalArgumentException("element i Not within the valid range!");
            }
            LoneListOne<Object> p = geti(i-1);
            p.next = p.next.next;
        }
    
  • 7. The code realizes the element modification in the single linked list: find the node and change the element
  • //Change: set the element with serial number i in the linear table to e
        public void SetElem(int i,Object e){
            if(i<0||i>size()-1){
                throw new IllegalArgumentException("element i Not within the valid range!");
            }
            LoneListOne<Object> p = geti(i);
            p.data = e;
        }
    
  • 8. The code realizes the search of elements in the single linked list:
  •  //Search: find the node with sequence number i and return the element with sequence number i in the linear table
        public Object getElem(int i){
            LoneListOne<Object> p = head;
            int j = -1;
            while(j<i){
                j++;
                p = p.next;
            }
            return p.data;
        }
    
  • 9. The code returns all elements in the single linked list: the principle is to traverse each node and assign the data data in each node to the string
  • //Convert all elements in the single linked list into strings and return
        public String ToString(){
            String ans = "";
            LoneListOne<Object> p = head.next;
            while(p!=null){
                ans+=p.data+" ";
                p=p.next;
            }
            return ans;
        }
    
    The above codes are implemented in the class LoneListTwo {} generic class
    Create a LoneListTwo object in the main class and call the method to realize its basic functions:
    public class LoneList {
        public static void main(String[] args) {
            Integer[] a={1,2,3,4,5};
            LoneListTwo<Object> loneListTwo = new LoneListTwo<>();
            loneListTwo.GreatLoneList(a);
            String s = loneListTwo.ToString();
            System.out.println("Output single linked list:"+s);
            loneListTwo.GreatLoneListEnd(a);
            String s1 = loneListTwo.ToString();
            System.out.println("Output single linked list:"+s1);
        }
    
    }
    
    The complete code is as follows:
    package com.other;
    
    class LoneListOne<Object>{
        Object data;
        LoneListOne<Object> next;
        //Establish a single chain header node model
        public LoneListOne(){
            next = null;
        }
        //Establish the data node model of single linked list
        public LoneListOne(Object d){
            data = d;
            next = null;
        }
    }
    class LoneListTwo<Object>{
        //Create header node
        LoneListOne<Object> head = new LoneListOne<>();
        //Establishing single linked list by head interpolation
        public void GreatLoneList(Object[] a){
            LoneListOne<Object> s;
            for (int i = 0; i < a.length; i++) {
                s = new LoneListOne<>(a[i]);
                s.next = head.next;
                head.next = s;
            }
        }
        //Creating tables by tail interpolation
        public void GreatLoneListEnd(Object[] a){
            LoneListOne<Object> s,t;
            t = head;
            for (int i = 0; i < a.length; i++) {
                s = new LoneListOne<>(a[i]);
                t.next = s;
                t = s;
            }
            t.next = null;
        }
        //Find the length of linear table
        public int size(){
            LoneListOne<Object> p = head;
            int count = 0;
            while(p.next!=null){
                count++;
                p = p.next;
            }
            return count;
        }
        //Add: add an element to the end of the single linked list
        public void Add(Object e){
            LoneListOne<Object> p = head;
            LoneListOne<Object> s = new LoneListOne<>(e);
            while(p.next!=null){
                p = p.next;
                p.next = s;
            }
        }
        //Find the node with sequence number i and prepare for deletion
        public LoneListOne<Object> geti(int i){
            LoneListOne<Object> p = head;
            int j = -1;
            while(j<i){
                j++;
                p = p.next;
            }
            return p;
        }
        //Delete: delete the ith element in the single linked list
        public void Delete(int i,Object e){
            if (i<0 ||i>size()-1) {
                throw new IllegalArgumentException("element i Not within the valid range!");
            }
            LoneListOne<Object> p = geti(i-1);
            p.next = p.next.next;
        }
        //Change: set the element with serial number i in the linear table to e
        public void SetElem(int i,Object e){
            if(i<0||i>size()-1){
                throw new IllegalArgumentException("element i Not within the valid range!");
            }
            LoneListOne<Object> p = geti(i);
            p.data = e;
        }
        //Search: find the node with sequence number i and return the element with sequence number i in the linear table
        public Object getElem(int i){
            LoneListOne<Object> p = head;
            int j = -1;
            while(j<i){
                j++;
                p = p.next;
            }
            return p.data;
        }
        //Convert all elements in the single linked list into strings and return
        public String ToString(){
            String ans = "";
            LoneListOne<Object> p = head.next;
            while(p!=null){
                ans+=p.data+" ";
                p=p.next;
            }
            return ans;
        }
    
    }
    public class LoneList {
        public static void main(String[] args) {
            Integer[] a={1,2,3,4,5};
            LoneListTwo<Object> loneListTwo = new LoneListTwo<>();
            loneListTwo.GreatLoneList(a);
            String s = loneListTwo.ToString();
            System.out.println("Output single linked list:"+s);
            loneListTwo.GreatLoneListEnd(a);
            String s1 = loneListTwo.ToString();
            System.out.println("Output single linked list:"+s1);
        }
    
    }
    

    The results are as follows:

    What is mainly written here is the implementation principle of single linked list. I did not call all methods in the main class. Readers can copy the code to try. When you understand the principle, you can try to create it independently.

    All the generic classes I created here use Object. In fact, it is not necessary to define lonelisone class and LoneListTwo class in this way. At the same time, Object modification variables can also be replaced with corresponding wrapper classes. The advantage of creating wrapper classes is that they can refer to any type when you are not sure what data type to use.

    As mentioned earlier, when an object is created and initialized, it will have all the contents in the corresponding construction method by default. 1. So the first class is to create the "shape" of each node. Why create another LoneListTwo class to implement its method? The initialized object can call all members and member methods in this class. If these node objects are created in the lonelisone class, the newly created node, such as s callable node head, is certainly unreasonable. In this way, the created node is not a linked list, but a "monster". So why should the function create a LoneListTwo class object in the main class LoneList and use it to call various methods? Of course, this is the object-oriented feature of Java. You can also merge the LoneListTwo class with the main class LoneList. Implement these functions in a class. Lack of rigor, for personal understanding only

    If you think the content is slightly acceptable, please leave your

Tags: Java data structure linked list

Posted by pheagey on Sat, 30 Apr 2022 20:18:10 +0300