双向链表

基本思想大体结构增加修改MyList测试遍历修改MyList 删除修改MyList测试

基本思想

双向链表与单向链表大同小异，只不过双向链表还有个节点指向最后一个节点

大体结构

新建工程，结构如下

package list; public class MyList { long size; Node firstNode; Node lastNode; public long getSize() { return size; } public Node getFirstNode() { return firstNode; } public void setFirstNode(Node firstNode) { this.firstNode = firstNode; } public Node getLastNode() { return lastNode; } public void setLastNode(Node lastNode) { this.lastNode = lastNode; } @Override public String toString() { return "MyList [size=" + size + ", firstNode=" + firstNode + ", lastNode=" + lastNode + "]"; } public class Node{ private int value; private Node preNode; private Node nextNode; private Node() { } public Node(int value) { this.value = value; } private void setValue(int value) { this.value = value; } public int getValue() { return value; } public Node getPreNode() { return preNode; } private void setPreNode(Node preNode) { this.preNode = preNode; } public Node getNextNode() { return nextNode; } private void setNextNode(Node nextNode) { this.nextNode = nextNode; } @Override public String toString() { return "Node [value=" + value + "]"; } } }

增加

修改MyList

public void setFirstNode(Node firstNode) { if(this.size == 0) { //如果没有节点，添加进去一个节点，而且首尾全部指向这个节点 this.firstNode = firstNode; this.lastNode = firstNode; this.size++; } else { //如果有节点，替换掉原来的第一个节点 Node currNode = this.firstNode; if(this.size == 1) { //如果只有一个节点，最后一个节点应该也指向firstNode this.lastNode = firstNode; this.firstNode = firstNode; } else { this.firstNode = firstNode; this.firstNode.setPreNode(currNode.getPreNode()); this.firstNode.setNextNode(currNode.getNextNode()); } } } public void setLastNode(Node lastNode) { if(this.size == 0) { //如果没有节点，添加进去一个节点，而且首尾全部指向这个节点 this.firstNode = lastNode; this.lastNode = lastNode; this.size++; } else { //如果有节点，替换掉原来的第最后个节点 Node currNode = this.lastNode; if(this.size == 1) { //如果只有一个节点，第一个一个节点应该也指向firstNode this.firstNode = lastNode; this.lastNode = lastNode; } else { this.lastNode = lastNode; this.lastNode.setPreNode(currNode.getPreNode()); this.lastNode.setNextNode(currNode.getNextNode()); } } } public void addNode(Node node) { if(this.size == 0) { //如果没有节点，首尾全部指向这个节点 this.firstNode = node; this.lastNode = node; } else { //如果有节点，则最后一个节点应该指向新加入的节点 Node currNode = this.firstNode; while(currNode.getNextNode()!=null) { currNode = currNode.getNextNode(); } currNode.setNextNode(node); node.setPreNode(currNode); this.lastNode = node; } this.size++; }

测试

测试1：本身没有节点，使用setFirstNode

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

结果 测试1：本身没有节点，使用addNode

@Test void testAddNode1() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.addNode(node1); System.out.println(myList); }

结果

遍历

修改MyList

public String queryAll() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append('{'); Node currNode = this.firstNode; while(currNode != null) { stringBuilder.append("->"); stringBuilder.append(currNode.getValue()); currNode = currNode.getNextNode(); } stringBuilder.deleteCharAt(1); stringBuilder.deleteCharAt(1); stringBuilder.append('}'); return stringBuilder.toString(); }

测试3：使用addNode添加第一个节点，setFirstNode替换掉

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

结果 测试4：使用setFirstNode设置第一个节点，addNode添加节点

@Test void testSetFirstAndAdd() { 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()); }

结果 测试5 使用addNode添加第一个节点，setLastNode替换最后一个节点

@Test void testAddAndSetLast() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.addNode(node1); System.out.println("替换前"+myList); myList.setLastNode(node2); System.out.println("替换后"+myList); }

结果 测试6:使用setFirstNode添加第一个节点，setLastNode替换最后一个节点

@Test void testsetFirstAndSetLast() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); System.out.println("替换前"+myList); myList.setLastNode(node2); System.out.println("替换后"+myList); }

结果 测试7：有两个节点，setLastNode替换最后一个节点

@Test void testSetLast() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); Node node3 = new MyList().new Node(3); myList.setFirstNode(node1); myList.addNode(node2); System.out.println("替换前"+myList); myList.setLastNode(node3); System.out.println("替换后"+myList); }

结果

测试8:当前没有节点，使用setLastNode添加最后一个节点

@Test void testSetLasttNode1() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); myList.setLastNode(node1); System.out.println(myList); }

结果 测试9：当前有节点，使用setLastNode添加最后一个节点

@Test void testSetLasttNode2() { MyList myList = new MyList(); Node node1 = new MyList().new Node(1); Node node2 = new MyList().new Node(2); myList.setFirstNode(node1); System.out.println("替换前"+myList); myList.setLastNode(node2); System.out.println("替换后"+myList); }

结果

删除

同单向链表一致，不适合做修改以及查询操作，现在还是只删除第一个节点以及最后一个节点。

修改MyList

public void deleteFirstNode() { if(this.size == 0) return; else if(this.size == 1) { this.firstNode = null; this.lastNode = null; } else { Node currNode = this.firstNode.getNextNode(); this.firstNode = currNode; } this.size--; } public void deleteLastNode() { if(this.size == 0) return; else if(this.size == 1) { this.firstNode = null; this.lastNode = null; } else { Node currNode = this.lastNode.getPreNode(); this.lastNode = currNode; } this.size--; }

测试

测试1：没有节点使用deleteFirstNode

@Test void testdeleteFirstNode() { MyList myList = new MyList(); myList.deleteFirstNode(); }

测试2：没有节点使用deleteLastNode

@Test void testdeleteLastNode() { MyList myList = new MyList(); myList.deleteLastNode(); }

测试3：有一个节点使用deleteFirstNode

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

结果 测试4：有一个节点使用deleteLastNode

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

结果 测试5：有两个节点使用deleteFirstNode

@Test void testdeleteFirstNode3() { 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); myList.deleteFirstNode(); System.out.println("删除后"+myList); }

结果 测试6：有两个节点使用deleteLastNode

@Test void testdeleteLasttNode3() { 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); myList.deleteLastNode(); System.out.println("删除后"+myList); }

结果