数据结构-链表（三）双向哨兵循环链表

代码实现：

• 构造

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  package LinkedLists; import java.util.NoSuchElementException; import java.util.function.Consumer; public class DoublyLoopLinkedListSentinel { private final Node_ sentinel = new Node_(null, -1, null); public DoublyLoopLinkedListSentinel() { sentinel.prev = sentinel; sentinel.next = sentinel; } 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; } }

• 插入

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  public void addFirst(int value) { Node_ next = sentinel.next; Node_ newNode = new Node_(sentinel, value, sentinel.next = newNode; next.prev = newNode; } public void insert(int index, int value) { if (index == 0) { addFirst(value); return; } Node_ prev = findByIndex(index - 1); Node_ next = prev.next; prev.next = new Node_(prev, value, next); next.prev = prev.next; }

• 删除

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  private void removeFirst() { if (sentinel.next == sentinel) { throw new NoSuchElementException("索引为空"); } Node_ next = sentinel.next.next; sentinel.next = next; next.prev = sentinel; } private void removeLast() { if (sentinel.prev == sentinel) { throw new NoSuchElementException("索引为空"); } Node_ prev = sentinel.prev.prev; sentinel.prev = prev; prev.next = sentinel; } public void remove(int index) { if (index == 0) { removeFirst(); return; } Node_ prev = findByIndex(index - 1); Node_ next = prev.next.next; prev.next = next; next.prev = prev; }

• 索引查找

  1 2 3 4 5 6 7 8 9

  private Node_ findByIndex(int index) { int i = 0; for (Node_ cur = sentinel.next; cur != sentinel; cur = cur.next, i++) { if (i == index) { return cur; } } throw new IndexOutOfBoundsException("索引异常index[" + index + "]"); }