单链表缺点：
仅存在后继，没有前驱，故只能正向遍历;
节点无法完成自我删除；
而我们的双链表刚好能够弥补这些缺点，使用代码实现一下环形双链表：
package dataStructureAtShangGuiGu; public class DoubleLinkedListDemo { public static void main(String[] args) throws InterruptedException { Node1 node1 = new Node1(1,"节点1"); Node1 node2 = new Node1(2,"节点2"); Node1 node3 = new Node1(3,"节点3"); Node1 node4 = new Node1(4,"节点4"); sop("初始双向环形链表为："); DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.listForward(); /* doubleLinkedList.add(node1); doubleLinkedList.add(node2); doubleLinkedList.add(node3); doubleLinkedList.add(node4); */ doubleLinkedList.addByOrder(node4); doubleLinkedList.addByOrder(node1); doubleLinkedList.addByOrder(node3); doubleLinkedList.addByOrder(node2); sop("添加后链表情况："); doubleLinkedList.listForward(); //doubleLinkedList.listReverse(); //sop("删除元素后情况："); //doubleLinkedList.delete(3); //doubleLinkedList.listForward(); //doubleLinkedList.listReverse(); sop("修改后链表情况："); doubleLinkedList.update(new Node1(2,"被修改的节点编号2")); doubleLinkedList.listForward(); } private static void sop(Object obj) { System.out.println(obj); } } class DoubleLinkedList{ public Node1 head; public Node1 tail; public DoubleLinkedList(){ this.head = new Node1(-1,""); this.tail = this.head; } public void add(Node1 node) { Node1 cur = this.head; if(-1==this.head.no) { //第一次添加节点,即初始化链表 this.head = node; //替换头节点 cur = this.head; //将辅助指针指向头节点 cur.next = cur; //将头节点next指向头节点 cur.pre = cur; this.tail = cur; this.head.no = node.no; return; } Node1 tmp = null; while(true) { if(cur.next==this.head) break; cur = cur.next; } tmp = cur; //将当前指针位置存一起来以备接下来使用 cur.next = node; //将新节点连接到链表 cur = cur.next; //将指针指向新节点位置 cur.pre = tmp; //新节点pre指向链表连接前的最后一个节点 cur.next = this.head; //新节点next指向头节点 this.head.pre = cur; //头节点pre指向最后一个节点，到此环就建立起来了 this.tail = cur; } public void addByOrder(Node1 node) { Node1 cur = this.head; if(-1==this.head.no) { //第一次添加节点,即初始化链表 this.head = node; //替换头节点 cur = this.head; //将辅助指针指向头节点 cur.next = cur; //将头节点next指向头节点 cur.pre = cur; this.tail = cur; this.head.no = node.no; return; } boolean flag = false; while(true) { if(node.no==cur.next.no) { this.sop("已经存在该编号元素！无法插入"); return; } //已经存在该编号元素，直接返回 if(cur.next==this.head) { flag = true; break; }; //只有一个元素情况 if(node.no<=cur.next.no) break; //找到了插入的位置 cur = cur.next; } if(flag) { //添加初始的时候只有一个元素的情况 if(node.no<=cur.next.no) { this.head = node; this.head.next = cur; this.head.pre = cur; cur.next = this.head; cur.pre = this.head; } }else { Node1 curNext = cur.next; node.pre = cur; //插入的元素的pre指向插入左边元素位置 node.next = cur.next; //插入的元素的next指向插入元素右边元素位置 cur.next = node; //插入的元素的左边元素的next指向插入的元素 curNext.pre = node; } Node1 cur1 = this.head; while(cur1.next!=this.head) { cur1 = cur1.next; } this.tail = cur1; //获取链表最后位置 } public void delete(int no) { Node1 cur = this.head; if(-1==this.head.no) { //链表没有初始化的情况 sop("无法删除，链表是空的！"); return; } if(cur.next==this.head) { //元素只有一个情况 if(cur.no==no) { //只有一个元素且刚好匹配 this.head = new Node1(-1,""); this.head.pre = this.head; this.head.next = this.head; this.tail = this.head; return; } return; } while(true) { if(cur.no==no) { //找到情况 cur.pre.next = cur.next; cur.next.pre = cur.pre; return; } cur = cur.next; } } public void update(Node1 node) { if(-1==this.head.no) { //链表没有初始化的情况 sop("无法修改，链表是空的！"); return; } Node1 cur = this.head; while(true) { if(cur.no==node.no) { //找到编号的情况 cur.name = node.name; return; } cur = cur.next; if(cur.no==node.no) { //找到编号的情况 cur.name = node.name; return; } if(cur.next==this.head) { return; } } } public void listForward() { Node1 cur = this.head; while(true){ if(-1==this.head.no) { //链表没有初始化的情况 sop("[]"); return; } sop("正："+cur); if(cur.next==this.head) return; cur = cur.next; } } public void listReverse() { Node1 cur = this.tail; while(true){ if(-1==this.head.no) { //链表没有初始化的情况 sop("[]"); return; } this.sop(cur); if(cur.pre==this.tail) return; cur = cur.pre; } } public void listF() throws InterruptedException { Node1 cur = this.head; while(true){ sop("正: "+cur); cur = cur.next; Thread.sleep(500); } } public void listR() throws InterruptedException { Node1 cur = this.tail; while(true){ sop("反: "+cur); cur = cur.pre; Thread.sleep(500); } } private void sop(Object obj) { System.out.println(obj); } } class Node1{ public int no; public String name; public Node1 pre; public Node1 next; public Node1(int no,String name) { this.no = no; this.name = name; } public String toString() { return "[no="+this.no+",name="+this.name+"]"; } }