This article mainly introduces the relevant information on the detailed explanation of the implementation of the doubly linked list in java. Friends who need it can refer to
The detailed explanation of the implementation of the doubly linked list in java
Two-way Linked list is a basic data structure. LinkedList has already implemented this structure in Java, but as a developer, you must also have the ability to display this structure yourself. Without further ado, here’s the code:
First is the node class of the linked list:
/** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainNode<T> nextChainNode; public ChainNode<T> preChainNode; public ChainNode(T data, ChainNode<T> nextChainNode, ChainNode<T> preChainNode) { this.data = data; this.nextChainNode = nextChainNode; this.preChainNode = preChainNode; } public ChainNode(T data) { this.data = data; } public int getDataNo() { return dataNo; } public void setDataNo(int dataNo) { this.dataNo = dataNo; } public void setData(T data) { this.data = data; } public T getData() { return data; } }
Then is the linked list:
<pre name="code" class="java">/** * 链表实现类 * @author Administrator * * @param <T> */ public class Chain<T> { //头节点 private ChainNode<T> headNode; //末尾节点指针 private ChainNode<T> lastNode; private int size; //创建链表就创建头节点 public Chain() { this.headNode = new ChainNode<T>(null); this.lastNode = headNode; } //增加一个节点 public void addNode(T data) { ChainNode<T> node = new ChainNode<T>(data); if(lastNode != null){ lastNode.nextChainNode = node; node.preChainNode = node; node.setDataNo(size); lastNode = node; size++; } } //删除指定索引的节点 public void deleteNode(int dataNo) throws Exception { if(getSize() == 0){ throw new Exception("chain is empty"); } for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) { if(node.getDataNo() == dataNo){ node.preChainNode.nextChainNode = node.nextChainNode; if(node.nextChainNode != null){ node.nextChainNode.preChainNode = node.preChainNode; } node.nextChainNode = null; node.preChainNode = null; size--; //重新设置节点的编号 for (ChainNode<T> chainNode = node.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) { chainNode.setDataNo(chainNode.getDataNo()-1); } return; } } throw new Exception("the corresponding data that can not be found"); } //获取指定索引的节点 public T get(int dataNo) throws Exception { if(getSize() == 0){ throw new Exception("chain is empty"); } for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) { if(node.getDataNo() == dataNo){ return node.getData(); } } throw new Exception("the corresponding data that can not be found"); } //修改对应索引的节点 public void set(int dataNo,T data) throws Exception { if(getSize() == 0){ throw new Exception("chain is empty"); } for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) { if(node.getDataNo() == dataNo){ node.setData(data); return; } } throw new Exception("the data that is to be modified can not be found"); } //是否包含对应数据的节点 public boolean isContains(T data) throws Exception { if(getSize() == 0){ throw new Exception("chain is empty"); } for (ChainNode<T> chainNode = headNode.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) { if(chainNode.getData() == data){ return true; } } return false; } //获取节点数量(不含头节点) public int getSize() { return size; } }
Test it:
public class ChainTest { public static void main(String[] args) throws Exception{ String oneString = "one"; String twoString = "two"; String threeString = "three"; String fourString = "four"; Chain<String> chain = new Chain<String>(); chain.addNode(oneString); chain.addNode(twoString); chain.addNode(threeString); chain.addNode(fourString); for (int i = 0; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } try { String string = chain.get(2); System.out.println("the data of the second node is"+string); System.out.println(chain.isContains(fourString)); chain.set(1, "haha"); System.out.println("modify chain"); for (int i = 0; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } chain.deleteNode(3); System.out.println("delete one node"); for (int i = 0; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } }
Result:
one two three four the data of the second node isthree true modify chain one haha three four delete one node one haha three
The above is the detailed content of Sample code sharing for java doubly linked list implementation. For more information, please follow other related articles on the PHP Chinese website!