引子

写完单向链表以及双向链表以后，决定写写单向循环链表

回顾以及目的

回顾单向链表

单向链表需要一个指向第一个节点的成员变量，以及一个描述链表大小的成员变量，如下图所示

期望的单向循环链表

即原本第一个节点的上个节点更改为最后一个节点，最后一个节点的下一个节点更改为第一个节点，就好像形成了一个闭环一样

新建工程

大体结构如下

本次使用静态内部类，并且size大小设置为long类型

public class MyList {long size;Node firstNode;public long getSize() {return size;}public Node getFirstNode() {return firstNode;}public String toString() {return "MyList [size=" + size + ", firstNode=" + firstNode + "]";}public static class Node{private int value;private Node preNode;private Node nextNode;private Node(){}public int getValue() {return value;}private void setValue(int value) {this.value = 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;}public String toString() {return "Node [value=" + value + "]";}public Node(int value) {this.value = value;}}
}

增加结点

setFirstNode

修改MyList

public void setFirstNode(Node firstNode) {if(this.size == 0L){//本身没有节点this.firstNode = firstNode;this.firstNode.setPreNode(this.firstNode);this.firstNode.setNextNode(this.firstNode);this.size++;}else {if(this.size == 1L){this.firstNode = firstNode;this.firstNode.setPreNode(this.firstNode);this.firstNode.setNextNode(this.firstNode);}else {Node preNode = this.firstNode.getPreNode();Node nextNode = this.firstNode.getNextNode();this.firstNode = firstNode;this.firstNode.setNextNode(nextNode);this.firstNode.setPreNode(preNode);}}}

测试

测试1：没有节点，设置第一个节点

@Testvoid testSetFirstNode() {MyList myList = new MyList();Node node1 = new MyList.Node(1);myList.setFirstNode(node1);System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());}

结果

测试2：有节点，替换第一个节点

@Testvoid testSetFirstNode1() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);myList.setFirstNode(node1);System.out.println("----修改前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println("----修改后----");myList.setFirstNode(node2);System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());}

结果

addNode

修改MyList

public void addNode(Node node){if(this.size == 0L){this.firstNode = node;this.firstNode.setPreNode(this.firstNode);this.firstNode.setNextNode(this.firstNode);}else {//先找到最后一个节点Node currNode = this.firstNode;long flag = 0L;while(currNode.getNextNode() != null){//flag用来判断是否已经遍历过一次，防止死循环flag++;if(flag == this.size) break;currNode = currNode.getNextNode();}this.firstNode.setPreNode(node);currNode.setNextNode(node);node.setPreNode(currNode);node.setNextNode(this.firstNode);}this.size++;}

测试

测试1：本身没有节点，addNode加入第一个节点

@Testvoid testAddNode() {MyList myList = new MyList();Node node1 = new MyList.Node(1);myList.addNode(node1);System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());}

结果

遍历节点

为了更好地验证增加结点的结果，加入遍历链表的方法

修改MyList

public String queryAll() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append('{');Node currNode = this.firstNode;long flag = 0L;while(currNode != null){flag++;//防止死循环stringBuilder.append("->");stringBuilder.append(currNode.getValue());if(flag == this.size) break;currNode = currNode.getNextNode();}if(this.size != 0L){//只有有节点时候才删除，否则本来对于StringBulider就只有一个{//不能连续删除位置1上的字符stringBuilder.deleteCharAt(1);stringBuilder.deleteCharAt(1);}stringBuilder.append('}');return stringBuilder.toString();} 

测试2：本身有一个节点，addNode加入新的节点

@Testvoid testAddNode2() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);myList.setFirstNode(node1);myList.addNode(node2);System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());}

结果

测试3：本身用addNode加入新的节点，setFirstNode替换第一个节点

@Testvoid testAddNode3() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);myList.addNode(node1);System.out.println("----修改前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());myList.setFirstNode(node2);System.out.println("----修改后----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());}

结果

测试4，使用addNode一次性添加多个节点

@Testvoid testAddNode4() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);Node node3 = new MyList.Node(3);myList.addNode(node1);		myList.addNode(node2);myList.addNode(node3);	System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());}

结果

删除节点

deleteFirstNode

修改MyList

public String deleteFirstNode(){if(this.size == 0L) return "当前链表为空";else if (this.size == 1L) {this.firstNode = null;}else {Node currNode = this.firstNode.getNextNode();currNode.setPreNode(this.firstNode.getPreNode());//如果只有两个节点，删除后后继节点以及前驱结点都应该为自身if(this.size ==2L) currNode.setNextNode(this.firstNode.getNextNode());this.firstNode = currNode;}this.size--;return "删除成功";}

测试

测试1，没有节点

@Testvoid testDeleteFirstNode() {MyList myList = new MyList();System.out.println(myList.deleteFirstNode());}

结果

测试2，有一个节点

@Testvoid testDeleteFirstNode1() {MyList myList = new MyList();Node node1 = new MyList.Node(1);myList.setFirstNode(node1);	System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteFirstNode());System.out.println("----删除后----");System.out.println("链表"+ myList);try {System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());			} catch (Exception e) {System.out.println(new RuntimeException("出错").getMessage());}System.out.println(myList.queryAll());}

结果

测试3，有两个节点

@Testvoid testDeleteFirstNode2() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);myList.setFirstNode(node1);	myList.addNode(node2);System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteFirstNode());System.out.println("----删除后----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());			System.out.println(myList.queryAll());}

结果

测试4，有多个节点

@Testvoid testDeleteFirstNode3() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);Node node3 = new MyList.Node(3);myList.setFirstNode(node1);	myList.addNode(node2);myList.addNode(node3);System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("第一个节点前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("第一个节点后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteFirstNode());System.out.println("----删除后----");System.out.println("链表"+ myList);System.out.println("第一个节点前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("第一个节点后继结点"+ myList.getFirstNode().getNextNode());			System.out.println(myList.queryAll());}

结果

deleteLastNode

修改MyList

public String deleteLastNode(){if(this.size == 0L) return "当前链表为空";else if (this.size == 1L) {this.firstNode = null;}else {Node lastNode = this.firstNode.getPreNode();Node currNode = lastNode.getPreNode();this.firstNode.setPreNode(currNode);currNode.setNextNode(this.firstNode);}this.size--;return "删除成功";}

测试

测试1，没有节点

@Testvoid testDeleteLastNode() {MyList myList = new MyList();System.out.println(myList.deleteLastNode());}

结果

测试2，有一个节点

@Testvoid testDeleteLastNode1() {MyList myList = new MyList();Node node1 = new MyList.Node(1);myList.setFirstNode(node1);	System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteLastNode());System.out.println("----删除后----");System.out.println("链表"+ myList);try {System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());			} catch (Exception e) {System.out.println(new RuntimeException("出错").getMessage());}System.out.println(myList.queryAll());}

结果

测试3，有两个节点

@Testvoid testDeleteLastNode2() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);myList.setFirstNode(node1);	myList.addNode(node2);System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteLastNode());System.out.println("----删除后----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());}

结果

测试4，有多个节点

@Testvoid testDeleteLastNode3() {MyList myList = new MyList();Node node1 = new MyList.Node(1);Node node2 = new MyList.Node(2);Node node3 = new MyList.Node(3);myList.setFirstNode(node1);	myList.addNode(node2);myList.addNode(node3);System.out.println("----删除前----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());System.out.println(myList.deleteLastNode());System.out.println("----删除后----");System.out.println("链表"+ myList);System.out.println("前驱结点"+ myList.getFirstNode().getPreNode());System.out.println("后继结点"+ myList.getFirstNode().getNextNode());System.out.println(myList.queryAll());}

结果