双向链表

引子查询修改MyList测试 删除FirstToLast修改MyList测试 LastToFirst 修改修改MyList测试 源码

引子

承接我的上一篇博客传送门 如果还不会单向链表的话，我的另一篇博客传送门

查询

同样的，虽然不擅长查询以及修改操作，但是只是练习而已，就简单的实现一下

修改MyList

public Node searchNodeByValue(int value) { //如果没有节点，直接返回 if(this.size == 0) return null; Node currNode = this.firstNode; while(currNode.getValue() != value) { if(currNode.getNextNode() != null) { currNode = currNode.getNextNode(); } //如果已经遍历完毕，直接返回 else return null; } return currNode; }

测试

测试1：没有节点

@Test void testSearchNode() { MyList myList = new MyList(); System.out.println(myList.searchNodeByValue(1)); }

结果 测试2：有一个节点，没有其值对应的节点

@Test void testSearchNode2() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.setFirstNode(node1); System.out.println(myList.searchNodeByValue(2)); }

结果 测试3：有一个节点，有其值对应的节点

@Test void testSearchNode3() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.setFirstNode(node1); System.out.println(myList.searchNodeByValue(1)); }

结果 测试4：有两个节点，没有其值对应的节点

@Test void testSearchNode4() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println(myList.searchNodeByValue(3)); }

结果 测试5：有两个节点，有其值对应的节点

@Test void testSearchNode5() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println(myList.searchNodeByValue(1)); System.out.println(myList.searchNodeByValue(1).getNextNode()); }

结果

删除

为了跟单向链表区分，设置为从前往后查询到第一个节点删除，以及从后往前

FirstToLast

修改MyList

public String deleteFirstToLast(int value) { if(this.size == 0) return "当前链表中没有节点"; Node currNode = this.searchNodeByValue(value); if(currNode == null) return "当前链表中没有该节点"; if(this.size == 1) { //如果只有一个节点，直接清空 this.firstNode = null; this.lastNode = null; } else { Node preNode = currNode.getPreNode(); Node nextNode = currNode.getNextNode(); if(currNode == this.firstNode) { //如果删除的是第一个节点，则更换指向 this.firstNode = nextNode; } if(currNode == this.lastNode) { //如果删除的是第最后个节点，更换指向 this.lastNode = preNode; } if(preNode != null) preNode.setNextNode(nextNode); if(nextNode != null) nextNode.setPreNode(preNode); } this.size--; return "删除成功"; }

测试

测试1：没有节点

@Test void testDeleteFirstToLast1() { MyList myList = new MyList(); System.out.println(myList.deleteFirstToLast(0)); }

结果 测试2：有一个节点，没有对应元素

@Test void testDeleteFirstToLast2() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.setFirstNode(node1); System.out.println(myList.deleteFirstToLast(0)); }

结果 测试3：有一个节点，有对应元素

@Test void testDeleteFirstToLast3() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.setFirstNode(node1); System.out.println("删除前"+myList); System.out.println(myList.deleteFirstToLast(1)); System.out.println("删除后"+myList); }

结果 测试4：有两个节点，没有对应元素

@Test void testDeleteFirstToLast4() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println("删除前"+myList); System.out.println(myList.queryAll()); System.out.println(myList.deleteFirstToLast(3)); System.out.println("删除后"+myList); System.out.println(myList.queryAll()); }

结果 测试5：有两个节点，有对应元素，且为第一个元素

@Test void testDeleteFirstToLast5() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println("删除前"+myList); System.out.println(myList.queryAll()); System.out.println(myList.deleteFirstToLast(1)); System.out.println("删除后"+myList); System.out.println(myList.queryAll()); }

结果 测试6：有两个节点，有对应元素，且为最后个元素

@Test void testDeleteFirstToLast6() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println("删除前"+myList); System.out.println(myList.queryAll()); System.out.println(myList.deleteFirstToLast(2)); System.out.println("删除后"+myList); System.out.println(myList.queryAll()); }

结果

LastToFirst

其实要实现这个，只需要重新写一个找寻节点的方法即可

public Node searchNodeByValue1(int value) { //从后往前查询即可 if(this.size == 0) return null; Node currNode = this.lastNode; while(currNode.getValue() != value) { if(currNode.getPreNode() != null) { currNode = currNode.getPreNode(); } else return null; } return currNode; } public String deleteLastToFirst(int value) { if(this.size == 0) return "当前链表中没有节点"; Node currNode = this.searchNodeByValue1(value); if(currNode == null) return "当前链表中没有该节点"; if(this.size == 1) { this.firstNode = null; this.lastNode = null; } else { Node preNode = currNode.getPreNode(); Node nextNode = currNode.getNextNode(); if(currNode == this.firstNode) { this.firstNode = nextNode; } if(currNode == this.lastNode) { this.lastNode = preNode; } if(preNode != null) preNode.setNextNode(nextNode); if(nextNode != null) nextNode.setPreNode(preNode); } this.size--; return "删除成功"; }

修改

修改MyList

public String updateNode(int origin, int target) { if(this.size == 0) return "当前链表中没有节点"; Node currNode = this.searchNodeByValue(origin); if(currNode == null) return "当前链表中没有该节点"; else currNode.setValue(target); return "修改成功"; }

测试

测试1：没有节点

@Test void update() { MyList myList = new MyList(); System.out.println(myList.updateNode(1, 2)); }

结果 测试2：没有对应节点

@Test void update1() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println(myList.updateNode(3, 2)); }

结果 测试3：修改成功

@Test void update2() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); myList.addNode(node2); System.out.println("====修改前===="); System.out.println(myList); System.out.println(myList.queryAll()); System.out.println("====修改后===="); System.out.println(myList.updateNode(1, 2)); System.out.println(myList); System.out.println(myList.queryAll()); }

结果

源码

传送门