Preface
A linked list is a common basic data structure. It is a linear table, but it is not stored sequentially in memory. It is stored in a chain form. Each node stores the "pointer" of the next node. Data in Java is divided into reference data types and basic data types. There is no concept of pointers in Java, but for linked lists, pointers refer to the address of reference data types.
Linked lists and arrays are both linear data structures, and their length is fixed for arrays. Since they are continuous in memory, they are more suitable for search and traversal. Linked lists are not stored sequentially in memory, but because they are composed of "pointers", it is more convenient to compare arrays when inserting and deleting.
The following code implements a simple data structure of a linked list described in Java language through internal classes and recursive methods. Let's take a look at the detailed introduction.
Definition of linked list data structure
First, let’s take a look at the definition of the linked list data structure, the code is as follows:
class NodeManager { private Node root; // root node private int currentIndex = 0; // node serial number, each operation starts from 0 public void add(int data) {} public void delNode(int data) {} public void print() {} public boolean findNode(int data) {} public boolean updateNode(int oldData, int newData) {} // Insert public void insert(int index, int data) {} // Who owns the data and provides the method class Node { private int data; private Node next; // Take the current type as a property public Node(int data) { this.data = data; } public void setData(int data) { this.data = data; } public int getData() { return data; } // Add node public void addNode(int data) {} // Delete node public void delNode(int data) {} // Output all nodes public void printNode() {} // Find whether the node exists public boolean findNode(int data) {} // Modify node public boolean updateNode(int oldData, int newData) {} // Insert node public void insertNode(int index, int data) {} }}For the definition of linked lists, the NodeManager class is used to manage linked list operations, while the member internal class Node is used to provide linked list data and chain structure. For the class users, data is not directly accessed, so the NodeManager class operates, and the internal class Node provides real data management. Therefore, the Node class needs to provide real data operation methods, and the NodeManager class also needs to provide a set of methods to operate linked lists by externally. Therefore, both the NodeManager class and the Node class provide seemingly the same methods, but the actual meaning is not the same.
Let’s check the add() method in the NodeManager class and the Node class. The code is as follows:
public void add(int data) { if ( root == null ) { root = new Node(data); } else { root.addNode(data); }}// Add node public void addNode(int data) { if ( this.next == null ) { this.next = new Node(data); } else { this.next.addNode(data); }}The above method in the code is the method in the NodeManager class, while the following method is the method in the Node class.
A root member variable is provided in the Manager class, which is used to manage the head node of the linked list. Therefore, when adding a node, it will first determine whether the root is empty. If it is empty, the node will be saved directly by the root. If the root is not empty, it will be added through the addNode() method in the Node class. The idea of adding to the point is to find the last node of the current linked list and assign the new addition to the next member variable that the node is assigned to the last node.
Add, delete, modify and check the linked list
The same idea is also given to other operations on linked lists. The complete code for adding, deleting, retrieval and output of linked lists is as follows:
class NodeManager { private Node root; // root node private int currentIndex = 0; // node serial number, each operation starts from 0 public void add(int data) { if ( root == null ) { root = new Node(data); } else { root.addNode(data); } } public void delNode(int data) { if ( root == null ) return ; if ( root.getData() == data ) { Node tmp = root; root = root.next; tmp = null; } else { root.delNode(data); } } public void print() { if ( root != null ) { System.out.print(root.getData() + " "); root.printNode(); System.out.println(); } } public boolean findNode(int data) { if ( root == null ) return false; if ( root.getData() == data ) { return true; } else { return root.findNode(data); } } public boolean updateNode(int oldData, int newData) { if ( root == null ) return false; if ( root.getData() == oldData ) { root.setData(newData); return true; } else { return root.updateNode(oldData, newData); } } // Insert public void insert(int index, int data) { if ( index < 0 ) return ; currentIndex = 0; if ( index == currentIndex ) { Node newNode = new Node(data); newNode.next = root; root = newNode; } else { root.insertNode(index, data); } } // Whoever owns the data, who provides the method class Node { private int data; private Node next; // Take the current type as a property public Node(int data) { this.data = data; } public void setData(int data) { this.data = data; } public int getData() { return data; } // Add node public void addNode(int data) { if ( this.next == null ) { this.next = new Node(data); } else { this.next.addNode(data); } } // Delete the node public void delNode(int data) { if ( this.next != null ) { if ( this.next.getData() == data ) { Node tmp = this.next; this.next = this.next.next; tmp = null; } else { this.next.delNode(data); } } } // Output all nodes public void printNode() { if ( this.next != null ) { System.out.print(this.next.getData() + " "); this.next.printNode(); } } // Find whether the node exists public boolean findNode(int data) { if ( this.next != null ) { if ( this.next.getData() == data ) { return true; } else { return this.next.findNode(data); } } return false; } // Modify the node public boolean updateNode(int oldData, int newData) { if ( this.next != null ) { if ( this.next.getData() == oldData ) { this.next.setData(newData); return true; } else { return this.next.updateNode(oldData, newData); } } return false; } // Insert node public void insertNode(int index, int data) { currentIndex ++; if ( index == currentIndex ) { Node newNode = new Node(data); newNode.next = this.next; this.next = newNode; } else { this.next.insertNode(index, data); } } } }}The above is the complete code for the basic operation of the linked list. The following is a call code for testing, the code is as follows:
public class LinkList { public static void main(String[] args) { NodeManager nm = new NodeManager(); System.out.println("Address of linked list (add 5, 4, 3, 2, 1)"); nm.add(5); nm.add(4); nm.add(3); nm.add(2); nm.add(1); nm.print(); System.out.println("Delete of linked list (delete 3)"); nm.delNode(3); nm.print(); System.out.println("Looking of linked list (finding 1)"); System.out.println(nm.findNode(1)); System.out.println("Linking list (find 10)"); System.out.println(nm.findNode(10)); System.out.println("Update list (update 1 to 10)"); nm.updateNode(1, 10); nm.print(); System.out.println("Insert list (insert 20 at the first position)"); nm.insert(1, 20); nm.print(); System.out.println("Insert list (insert 30 at the first position)"); nm.insert(1, 20); nm.print(); System.out.println("Insert list (insert 30 at the zero position)"); nm.insert(0, 30); nm.print(); }}Compile and run the code, the result is as follows:
I have used a lot of knowledge about data structures in the collection class in Java. When I am in good condition, I will learn the source code of the Java collection class. I will work hard to be a junior programmer!
Summarize
The above is the entire content of this article. I hope that the content of this article has certain reference value for everyone's study or work. If you have any questions, you can leave a message to communicate. Thank you for your support to Wulin.com.