1. 前言
前文我们分别实现了不带哨兵的单链表，带哨兵节点的双向链表，接着我们实现带哨兵节点的双向循环链表.双向循环链表只需一个哨兵节点，该节点的prev指针和next指针都指向了自身哨兵节点.
2. 实现双向循环链表的代码
例 :
//模拟双向循环链表 public class CircleLinkedList implements Iterable<Integer>{ private static class Node{ Node prev; int value; Node next; public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; } } private static Node head = new Node(null, 10086, null); //只有一个哨兵节点, 并且哨兵节点的两个指针域都指向本身 public CircleLinkedList() { head.prev = head; head.next = head; } //头插法 public void addHead(int value) { Node p = head.next; Node q = new Node(head, value, p); head.next = q; p.prev = q; } //从头开始遍历 public void Traverse1Head() { Node p = head.next; while (p != head) { System.out.println("该处节点的数据域的值是" + p.value); p = p.next; } } //从尾开始遍历 public void Traverse1Tail() { Node p; for (p = head.prev; p != head; p = p.prev) { System.out.println("该处节点的数据域的值是" + p.value); } } //获取指定位置的值 public static int get(int index) { Node p = findIndex(index); //此时该方法返回的是哨兵节点 if (p == head) { throw new RuntimeException("哨兵节点不可获取值"); } return p.value; } //从哨兵节点开始找指定索引的节点的值 private static Node findIndex(int index) { //我们假设哨兵节点的索引为-1 int count = -1; Node p = head; if (index < -1) { throw new RuntimeException("index输入不合法"); } while (count < index) { p = p.next; //当p == head, 说明遍历一圈都没找到, 即index过大 if (p == head) { throw new RuntimeException("输入无效的index"); } count++; } return p; } //尾插法 public void addTail(int value) { Node p = head.prev; Node q = new Node(p, value, head); p.next = q; head.prev = q; } //向指定索引的位置添加节点 public void Insert(int index, int value) { //找到要插入节点的前一个节点 Node p = findIndex(index - 1); Node q = new Node(p, value, p.next); p.next.prev = q; p.next = q; } //对指定索引的节点进行删除操作 public void remove(int index) { //找到要插入节点的前一个节点 //当index==0时, p指向哨兵节点 Node p = findIndex(index - 1); p.next.next.prev = p; p.next = p.next.next; } //实现了Iterable接口, 可foreach循环 @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { Node p = head.next; @Override public boolean hasNext() { return p != head; } @Override public Integer next() { int value = p.value; p = p.next; return value; } }; } }
3. 单元测试
@Test public void test1() { CircleLinkedList c = new CircleLinkedList(); c.addHead(12); c.addHead(23); c.addHead(34); c.addHead(45); c.addHead(56); c.addHead(67); c.addHead(78); c.Traverse1Head(); // c.Traverse1Tail(); // System.out.println(c.get(6)); } @Test public void test2() { CircleLinkedList c = new CircleLinkedList(); c.addTail(12); c.addTail(23); c.addTail(34); c.addTail(45); c.addTail(56); c.addTail(67); c.addTail(78); c.Insert(7, 100); c.remove(7); c.remove(0); // c.Traverse1Head(); c.Traverse1Head(); } @Test public void test3() { CircleLinkedList c = new CircleLinkedList(); c.addTail(12); c.addTail(23); c.addTail(34); c.addTail(45); c.addTail(56); c.addTail(67); c.addTail(78); for (int element : c) { System.out.println("该节点的数据域是" + element); } }
