Simple linked list of data structure

This data structure suddenly comes to mind when doing the algorithm problem of power button, and it is necessary to record it

1. Define a Link class and a Node class, where the Node class is the internal class of the Link class (avoiding repeated getter and setter methods)
The purpose of the Link class is to create nodes
The purpose of Node class is to Link data and nodes, and Node can only be called for Link, which needs to be defined as private
Another Factory class is defined to call the client. It returns an instance of the Link class

2. The node class needs to contain the following properties:
(1) Object data: used to store data
(2) Node next: the user stores the data pointing to the next node
Constructor is to assign data
3. Add 1 additional function to add elements to the list
(1) it is clear that appending data should be completed in the Link class
(2) first declare the root node in the Link class
(3) if there is no incoming data, return directly without any operation
(4) for stored data, you need to create a new Node, a new Node object, and then give the Node object to the Node class for processing
In step 4 of (5), the storage node data should start from root. If root is empty, the storage data is root. Just assign the new node to root
If not, the new Node should be handled by the Node class, starting from the root Node
The node class (6) receives the newNode object from the Link class, and performs the following processing:
Determine whether the next value of root is null. If yes, assign the newnode to root.next
If it is not empty, then recursively, next is root.next.next
Add a data and handle the node relationship after the above completion
The test procedure is:
//
public class TestLinkDemo {
    public static void main(String[] args) {
        Link all = Factory.getInstance();
        all.add("AAA");
        all.add("BBB");
        all.add("CCC");
    }
}
//
4. Add a function to get the number of data in the linked list
(1) define the attribute in the Link class, count the number
(2) define a method to get count, which is the number of returned data
Define isEmpty() method to determine whether the list is empty
5. Add a function to convert the linked list into an object array
A linked list (1) is a dynamic array. The return type is Object[] data. Each data is obtained in order. Therefore, a cursor needs to be defined
In the (2) Link class, first of all, you need to determine whether the length of the list is zero. If it is zero, it returns a null value. If it is not zero, you need to traverse the entire list,
The cursor is 0, starting from the root Node and calling the function (new definition) to get data from the Node
(3) Node class needs to get the data of each node and fill it in the array. If it is judged that there is still data in the next node, it is necessary to continue recursion
6. Add a method to query data
equals method support required for (1)
Append a method in (2) Node to find the specified element, and it must start from the root node and go back
Add a method in (3) Link to judge the search content that must be entered and the link list is not empty. If it is normal, call the method in Node, starting from root
    
7. Get data according to index
(1) add an index search method in the Node class, and search according to the cursor
(2) add an index search method in the Link class to ensure that there is data in the linked list, and initialize the cursor to search from the root node later

8. Modify the data of the specified index
(1) first define a method in the Link class, pass in 2 parameters, the first is the index value, and the second is the target object value to be modified
If the index exceeds the length of the linked list, it will not be modified and the call will be terminated
Otherwise, set the cursor first, and then call the function in the Node that actually modifies the data from the root Node
For the methods defined in node class, first determine whether the current cursor is the specified cursor, and if so, modify the data
If not, judge whether the current node is the last one. If the node is not empty, continue to find the node later and call recursively

9. Delete data
(1) all the premises are that the data exists. All the data are first searched by the search methods defined above
If you delete the root node, you only need to complete the operation of replacing the root in the Link class
If not, the next Node of the root Node should be handed over to the deletion method in the Node class
In the node class, judge whether the data of the current object is the data to be deleted. If so, point the previous next of this object to the next

Continue recursive deletion if not

 

Update the search method. There is something wrong with the original course

//Get data by index
    public Object getNode(int searchIndex) {
      if (Link.this.index++ == searchIndex) {
        return this.data;
      } else {
        return this.next.getNode(searchIndex);
      }
    }
class Link {
    private Node root; //Root node, add data function add
    private int count; //Number of statistical elements
    private Object[] retData; //Returns an array of objects
    private int index = 0; //Operation cursor
    // Define the internal class of Node, which means that Node only serves the Link class
    private class Node { //Responsible for data saving and node relationship configuration
        private Object data;
        private Node next;
        public Node(Object data) {
            this.data = data;
        }
        //Add data
        public void addNode(Node newNode) {
        if (this.next == null) {
            this.next = newNode;
        } else {
            this.next.addNode(newNode);
        }
        }
        //Convert to object array
        public void toArrayNode() {
            Link.this.retData[Link.this.index ++] = this.data;//First, take out the data of the root node, and then add a cursor
            if (this.next != null){ //If the next node still has data, recursively get
                this.next.toArrayNode();
            }
        }
        //Find data
        public boolean containsNode(Object search) {
            if (search.equals(this.data)) {
                return true; //Find data
            } else {
                if (this.next != null) { //And subsequent nodes
                    return this.next.containsNode(search);//recursive lookup
                } else {
                    return false;
                }
            }
        }
        //Get data by index
        public Object getNode(int searchIndex) {
            if (Link.this.index ++ == searchIndex) {
                return this.data;
            } else {
                this.next.getNode(searchIndex);
            }
            return null;
        }
        //Modify data for the specified index
        public void setNode(int searchIndex, Object newData) {
            if (Link.this.index ++ == searchIndex) {
                this.data = newData;
            } else {
                if (this.next != null) {
                    this.next.setNode(searchIndex,newData);
                }
            }
        }
        //Delete elements
        public void removeDataNode(Node previous, Object data) {
            if (this.data.equals(data)) {
                previous.next = this.next; //This is in the middle. If this data is the data to be deleted, point a node before this to a node after this
            } else {
                this.next.removeDataNode(this, data);
            }
        }
    }
    // ---------Here is the Link class definition-----------
    //Add elements
    public void add(Object data) {
        if ( data == null ) {//Null data is not allowed
            return;
        }
        Node newNode = new Node(data); //Create a new node
        if (this.root == null) {
            this.root = newNode;
        } else {
            this.root.addNode(newNode);
        }
        this.count ++;
    }
    //Get linked list size
    public int size() {
        return this.count;
    }
    //Judge whether the list is empty
    public boolean isEmpty() {
        if (this.root == null && this.count == 0 ) {
            return false;
        } else {
            return true;
        }
    }
    //Convert linked list to object array
    public Object[] toArray() {
        if (this.count == 0) { //If the linked list has no data, null is returned
            return null;
        }
        this.retData = new Object[this.count];//If count is not zero, an array of objects with specified space will be opened
        this.index = 0;//Cursor initialized to 0
        this.root.toArrayNode();//Give the Node class to retrieve the data
        return this.retData;//Returns an array of objects
    }
    //Find data
    public boolean contains(Object search) {
        if (search == null || this.root == null) {
            return false;
        }
        return this.root.containsNode(search);
    }
    //Get data by index
    public Object get(int searchIndex) {
        if (searchIndex >= this.count) {
            return null;
        }
        this.index = 0;
        return this.root.getNode(searchIndex);
    }
    //Modify data for the specified index
    public void setData(int searchIndex, Object newData) {
        if (searchIndex >= this.count) {
            return ;
        } else {
            this.index = 0;
            this.root.setNode(searchIndex, newData);
        }
    }
    //Delete data
    public void removeData(Object data) {
        if (this.contains(data)) {
            if (this.root.data.equals(data)) {
                this.root = this.root.next;
            } else {
                this.root.next.removeDataNode(this.root, data);
            }
            this.count --;
        }
    }
            
}
 
class Factory {
    public static Link getInstance() {
        return new Link();
    }
}
 
public class TestLinkDemo {
    public static void main(String[] args) {
        Link all = Factory.getInstance();
        //
        all.add("AAA");
        all.add("BBB");
        all.add("CCC");
        //
        System.out.println("The chain table size is: " + all.size());
        //
        Object[] result = all.toArray();
        System.out.println("The linked list is converted to an object array and output: ");
        for ( Object x : result ) {
            System.out.println(x);
        }
        //Query data method
        System.out.println("Query data method: ");
        System.out.println(all.contains("AAA"));
        System.out.println(all.contains("D"));
        //Get index data
        System.out.println("Find data with index 0: ");
        System.out.println(all.get(0));
        System.out.println("Find data with index 3: ");
        System.out.println(all.get(3));
        //Modify index data
        System.out.println("Modify index data: ");
        all.setData(0,"DDD");
        Object[] result1 = all.toArray();
        System.out.println("Modify index data and output: ");
        for ( Object x : result1 ) {
            System.out.println(x);
        }
        //Delete data
        System.out.println("Delete data: ");
        all.removeData("BBB");
        Object[] result2 = all.toArray();
        System.out.println("Delete data and output: ");
        for ( Object x : result2 ) {
            System.out.println(x);
        }
    }
}

   


Test results:


 

Tags: Programming Attribute

Posted on Wed, 06 Nov 2019 01:50:27 -0800 by klycette