A linked list is a complex data structure. The relationship between the data makes a linked list divided into three types: single linked list, circular linked list, and bidirectional linked list . The following will be introduced one by one. Linked lists are the basic and important knowledge points in the data structure. Here we will talk about the implementation of linked lists in Java.
JAVA linked list operations: single-linked list and double-linked list
A few points mainly talk about:
1. Introduction to the linked list
2. Principles and necessities for implementation of linked lists
3. Single-stranded example
4. Double-linked example
1. Introduction to the linked list
Linked lists are a relatively common data structure. Although linked lists are more complicated to store, they are more convenient when querying. They are used in multiple computer languages accordingly. There are many categories of linked lists. Articles are analyzed for single-linked lists and double-linked lists. The data in the linked list is like being connected together by a chain, allowing easy access to data.
2. Principles and necessities for implementation of linked lists
Only single-linked lists and double-linked lists are analyzed here. The implementation process of linked lists is a bit complicated, but it will bring many benefits. For example, with the arrival of online shopping, merchants usually pack the goods in a box and write the address information on the box. The express company can find the buyer through the information on the box, and the goods arrive intact. Without the protection of the box, the product may be damaged along the way. The linked list is like the box with address information written, which not only protects product information, but also writes logistics information. There is a HEAD node in the linked list, similar to the "locomotive". As long as the corresponding HEAD node is found, you can operate on the linked list. In this analysis, the HEAD node only acts as a data header and does not save valid data.
The implementation principle of single linked list is shown in the figure:
Double-linked list implementation principle:
3. Single-stranded example
ICommOperate<T> interface operation class:
package LinkListTest;import java.util.Map;public interface ICommOperate<T> { public boolean insertNode(T node) ; public boolean insertPosNode(int pos, T node) ; public boolean deleteNode(int pos, Map<String, Object> map) ; public void printLink() ;}Single linked list node:
package LinkListTest;// Single-connected table node public class SNode { private String data; private SNode nextNode; public SNode() { } public SNode(String data) { this.data = data; this.nextNode = new SNode(); } public String getData() { return data; } public void setData(String data) { this.data = data; } public SNode getNextNode() { return nextNode; } public void setNextNode(SNode nextNode) { this.nextNode = nextNode; } @Override public String toString() { return "SNode [data=" + data + "]"; }}Single link operation class:
package LinkListTest;import java.util.HashMap;import java.util.Map;public class SingleLinkList implements ICommOperate<SNode>{ private SNode head = new SNode("HEAD"); // Public header pointer, unchanged after declaration private int size = 0 ; public int getSize() { return this.size; } /* * Insert the linked list, insert it to the end each time */ @Override public boolean insertNode(SNode node) { boolean flag = false ; SNode current = this.head ; if( this.size==0 ){ // empty linked list this.head.setNextNode(node) ; node.setNextNode(null) ; }else{ // node in the linked list while( current.getNextNode()!=null ){ current = current.getNextNode() ; } current.setNextNode(node) ; node.setNextNode(null) ; } this.size++ ; flag = true ; return flag; } /* * Insert the specified position of pos in the linked list, starting from 1, and pos is greater than size, then insert the end of the linked list * */ @Override public boolean insertPosNode(int pos, SNode node){ boolean flag = true; SNode current = this.head.getNextNode() ; if( this.size==0 ){ // The empty linked list this.head.setNextNode(node) ; node.setNextNode(null) ; this.size++ ; }else if( this.size<pos ){ // The pos position is greater than the length of the linked list, insertNode(node) ; }else if( pos>0 && pos<=this.size) { // Node in the linked list// 1. Find the node and the front node to be inserted int find = 0; SNode preNode = this.head; // Front node SNode currentNode = current; // Current node while( find<pos-1 && currentNode.getNextNode()!=null ){ preNode = current ; // Front node moves backward currentNode = currentNode.getNextNode() ; // Current node moves backward find++ ; }// System.out.println(preNode);// System.out.println(currentNode); // 2. Insert node preNode.setNextNode(node); node.setNextNode(currentNode); this.size++; System.out.println("Node has been inserted into the linked list"); }else{ System.out.println("Position information error"); flag = false ; } return flag; } /* * Specify the node pos of the linked list and delete the corresponding node. Method: Find the front and rear nodes to delete and delete. Starting from 1* */ @Override public boolean deleteNode(int pos) { boolean flag = false; SNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("Position information error or no information in the linked list"); }else{ // 1. Find the front and back nodes to delete int find = 0; SNode preNode = this.head; // Front node SNode nextNode = current.getNextNode(); // Back node while( find<pos-1 && nextNode.getNextNode()!=null ){ preNode = current ; // The front node is moved back nextNode = nextNode.getNextNode() ; // The back node is moved back find++ ; }// System.out.println(preNode);// System.out.println(nextNode); // 2. Delete the node preNode.setNextNode(nextNode); System.gc(); this.size-- ; flag = true ; } return flag; } /* * Specify the node pos of the linked list and modify the corresponding node. Starting from 1* */ @Override public boolean updateNode(int pos, Map<String, Object> map) { boolean flag = false ; SNode node = getNode(pos, map); // Get the node at the corresponding position if( node!=null ){ String data = (String) map.get("data") ; node.setData(data); flag = true ; } return flag; } /* * Find the node pos of the specified linked list, starting from 1* */ @Override public SNode getNode(int pos, Map<String, Object> map) { SNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("Position information is incorrect or the linked list does not exist"); return null; } int find = 0 ; while( find<pos-1 && current!=null ){ current = current.getNextNode() ; find++ ; } return current; } /* * Print linked list* */ @Override public void printLink() { int length = this.size ; if( length==0 ){ System.out.println("The linked list is empty!"); return ; } SNode current = this.head.getNextNode() ; int find = 0 ; System.out.println("Total number of nodes: " + length +" ones"); while( current!=null ){ System.out.println("Th" + (++find) + "nodes: " + current); current=current.getNextNode() ; } } public static void main(String[] args) { SingleLinkList sll = new SingleLinkList() ; SNode node1 = new SNode("Node1"); SNode node2 = new SNode("Node2"); SNode node3 = new SNode("Node3"); SNode node4 = new SNode("Node4"); SNode node5 = new SNode("Node5"); SNode node6 = new SNode("Insert specified position"); sll.insertPosNode(sll.getSize()+1, node1); sll.insertPosNode(sll.getSize()+1, node2); sll.insertPosNode(sll.getSize()+1, node3); sll.insertPosNode(sll.getSize()+1, node4); sll.insertPosNode(sll.getSize()+1, node5); // sll.insertNode(node1); // sll.insertNode(node2); // sll.insertNode(node3); // sll.insertNode(node4); // sll.insertNode(node5); System.out.println("******************************"); sll.printLink(); System.out.println("*********************************"); int pos = 2 ; System.out.println("Get the "+pos+" position data of the linked list: "+sll.getNode(pos, null)); System.out.println("****************************** Insert nodes to the specified position of the linked list**********************************"); int pos1 = 2 ; System.out.println("Insert data into "+pos1+" nodes: "); sll.insertPosNode(pos1, node6); sll.printLink(); System.out.println("************************************Delete the specified location node of the linked list*************************************"); int pos2 = 2; System.out.println("Delete"+pos2+" nodes: "); sll.deleteNode(pos2); sll.printLink(); System.out.println("***************************************Modify the specified location node of the linked list*************************************"); int pos3 = 2 ; System.out.println("Modify the "+pos3+" nodes: "); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; sll.updateNode(pos3, map) ; sll.printLink(); }}4. Double-linked example
ICommOperate<T> interface operation class:
package LinkListTest;import java.util.Map;public interface ICommOperate<T> { public boolean insertNode(T node) ; public boolean insertPosNode(int pos, T node) ; public boolean deleteNode(int pos, Map<String, Object> map) ; public void printLink() ;}Double-linked list node:
package LinkListTest;// Dual-contiguous table node public class DNode { private DNode priorNode; private String data; private DNode nextNode; public DNode(){ } public DNode(String data) { this.priorNode = new DNode() ; this.data = data ; this.nextNode = new DNode() ; } public DNode getPriorNode() { return priorNode; } public void setPriorNode(DNode priorNode) { this.priorNode = priorNode; } public String getData() { return data; } public void setData(String data) { this.data = data; } public DNode getNextNode() { return nextNode; } public void setNextNode(DNode nextNode) { this.nextNode = nextNode; } @Override public String toString() { return "DNode [data=" + data + "]"; } }Double-linked list implementation class:
package LinkListTest;import java.util.HashMap;import java.util.Map;public class DoubleLinkList implements ICommOperate<DNode>{ private DNode head = new DNode("HEAD"); private int size = 0 ; public int getSize() { return this.size; } /* * Insert the linked list, insert it to the end every time * */ @Override public boolean insertNode(DNode node) { boolean flag = false; DNode current = this.head ; if( this.size==0 ){ // empty linked list this.head.setNextNode(node); node.setPriorNode(this.head); node.setNextNode(null); }else{ // node in the linked list while( current.getNextNode()!=null ){ current = current.getNextNode() ; } current.setNextNode(node); node.setNextNode(null); node.setPriorNode(current); } this.size++ ; flag = true ; return flag; } /* * Insert the specified position of pos in the linked list, starting from 1, and pos is greater than size, insert the end of the linked list * */ @Override public boolean insertPosNode(int pos, DNode node) { boolean flag = true; DNode current = this.head.getNextNode() ; if( this.size==0){ // The linked list is empty this.head.setNextNode(node); node.setNextNode(null) ; node.setPriorNode(this.head); this.size++ ; }else if( pos>this.size ){ // Pos position is greater than the length of the linked list, insert the end insertNode(node); }else if( pos>0 && pos<=this.size ){ // Node in the linked list// 1. Find the pos node to be inserted, insert the pos node current location int find = 0; while( find<pos-1 && current.getNextNode()!=null ){ current = current.getNextNode() ; find++ ; } // 2. Insert node if( current.getNextNode()==null ){ // tail node node.setPriorNode(current); node.setNextNode(null); current.setNextNode(node); } else if( current.getNextNode()!=null ) { //Intermediate node node.setPriorNode(current.getPriorNode()); node.setNextNode(current); current.getPriorNode().setNextNode(node); current.setPriorNode(node); } this.size++ ; }else{ System.out.println("Position information error"); flag = false ; } return flag; } /* * Specify the node pos of the linked list, delete the corresponding node, starting from 1* */ @Override public boolean deleteNode(int pos) { boolean flag = false; DNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("Position information is incorrect or the linked list does not exist"); }else{ // 1. Find the location to be deleted pos node int find = 0; while( find<pos-1 && current.getNextNode()!=null ){ current = current.getNextNode() ; find++ ; } // 2. Delete node if( current.getNextNode()==null ){ // The tail node current.getPriorNode().setNextNode(null) ; } else if( current.getNextNode()!=null ) { // The intermediate node current.getPriorNode().setNextNode(current.getNextNode()) ; current.getNextNode().setPriorNode(current.getPriorNode()) ; } System.gc(); this.size-- ; flag = true ; } return flag; } /* * Specify the node pos of the linked list and modify the corresponding node. Start at 1* */ @Override public boolean updateNode(int pos, Map<String, Object> map) { boolean flag = false ; DNode node = getNode(pos, map); if( node!=null ){ String data = (String) map.get("data") ; node.setData(data); flag = true ; } return flag; } /* * Find the node pos of the specified linked list, start at 1* */ @Override public DNode getNode(int pos, Map<String, Object> map) { DNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("Position information is incorrect or the linked list does not exist"); return null; } int find = 0 ; while( find<pos-1 && current!=null ){ current = current.getNextNode() ; find++ ; } return current; } /* * Print linked list* */ @Override public void printLink() { int length = this.size ; if( length==0 ){ System.out.println("The linked list is empty!"); return ; } DNode current = this.head.getNextNode() ; int find = 0 ; System.out.println("Total number of nodes: " + length +" ones"); while( current!=null ){ System.out.println("Th" + (++find) + "nodes: " + current); current=current.getNextNode() ; } } public static void main(String[] args) { DoubleLinkList dll = new DoubleLinkList() ; DNode node1 = new DNode("Node1"); DNode node2 = new DNode("Node2"); DNode node3 = new DNode("Node3"); DNode node4 = new DNode("Node4"); DNode node5 = new DNode("Node5"); DNode node6 = new DNode("Insert specified position"); dll.insertPosNode(10, node1); dll.insertPosNode(10, node2); dll.insertPosNode(10, node3); dll.insertPosNode(10, node4); dll.insertPosNode(10, node5);// dll.insertNode(node1);// dll.insertNode(node2);// dll.insertNode(node3);// dll.insertNode(node4);// dll.insertNode(node5); System.out.println("******************************"); dll.printLink(); System.out.println("************************************"); int pos = 2 ; System.out.println("Get the "+pos+" position data of the linked list: "+dll.getNode(pos, null)); System.out.println("****************************** Insert nodes to the specified position of the linked list**********************************"); int pos1 = 2 ; System.out.println("Insert data into the "+pos1+" nodes: "); dll.insertPosNode(pos1, node6); dll.printLink(); System.out.println("*********************************Delete the nodes specified in the linked list*************************************"); int pos2 = 7; System.out.println("Delete"+pos2+" nodes:"); dll.deleteNode(pos2); dll.printLink(); System.out.println("************************************Modify the nodes specified in the linked list*************************************"); int pos3 = 2; System.out.println("Modify the "+pos3+" nodes:"); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; dll.updateNode(pos3, map) ; dll.printLink(); } }Thank you for reading, I hope it can help you. Thank you for your support for this site!