三、单向链表（带哨兵）
观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head 这样的代码，能不能简化呢？
用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表
public class SinglyLinkedListSentinel { // ... private Node head = new Node(Integer.MIN_VALUE, null); }
具体存什么值无所谓，因为不会用到它的值
加入哨兵节点后，代码会变得比较简单，先看几个工具方法
public class SinglyLinkedListSentinel { // ... // 根据索引获取节点 private Node findNode(int index) { int i = -1; for (Node curr = this.head; curr != null; curr = curr.next, i++) { if (i == index) { return curr; } } return null; } // 获取最后一个节点 private Node findLast() { Node curr; for (curr = this.head; curr.next != null; ) { curr = curr.next; } return curr; } }
findNode 与之前类似，只是 i 初始值设置为 -1 对应哨兵，实际传入的 index 也是 [ − 1 , ∞ ) [-1, \infty)[−1,∞)
findLast 绝不会返回 null 了，就算没有其它节点，也会返回哨兵作为最后一个节点
这样，代码简化为
public class SinglyLinkedListSentinel { // ... public void addLast(int value) { Node last = findLast(); /* 改动前 if (last == null) { this.head = new Node(value, null); return; } */ last.next = new Node(value, null); } public void insert(int index, int value) { /* 改动前 if (index == 0) { this.head = new Node(value, this.head); return; } */ // index 传入 0 时，返回的是哨兵 Node prev = findNode(index - 1); if (prev != null) { prev.next = new Node(value, prev.next); } else { throw illegalIndex(index); } } public void remove(int index) { /* 改动前 if (index == 0) { if (this.head != null) { this.head = this.head.next; return; } else { throw illegalIndex(index); } } */ // index 传入 0 时，返回的是哨兵 Node prev = findNode(index - 1); Node curr; if (prev != null && (curr = prev.next) != null) { prev.next = curr.next; } else { throw illegalIndex(index); } } public void addFirst(int value) { /* 改动前 this.head = new Node(value, this.head); */ this.head.next = new Node(value, this.head.next); // 也可以视为 insert 的特例, 即 insert(0, value); } }
对于删除，前面说了【最后一个 if 块对应着至少得两个节点的情况】，现在有了哨兵，就凑足了两个节点
四、双向链表（带哨兵）
public class DoublyLinkedListSentinel implements Iterable<Integer> { private final Node head; private final Node tail; public DoublyLinkedListSentinel() { head = new Node(null, 666, null); tail = new Node(null, 888, null); head.next = tail; tail.prev = head; } private Node findNode(int index) { int i = -1; for (Node p = head; p != tail; p = p.next, i++) { if (i == index) { return p; } } return null; } public void addFirst(int value) { insert(0, value); } public void removeFirst() { remove(0); } public void addLast(int value) { Node prev = tail.prev; Node added = new Node(prev, value, tail); prev.next = added; tail.prev = added; } public void removeLast() { Node removed = tail.prev; if (removed == head) { throw illegalIndex(0); } Node prev = removed.prev; prev.next = tail; tail.prev = prev; } public void insert(int index, int value) { Node prev = findNode(index - 1); if (prev == null) { throw illegalIndex(index); } Node next = prev.next; Node inserted = new Node(prev, value, next); prev.next = inserted; next.prev = inserted; } public void remove(int index) { Node prev = findNode(index - 1); if (prev == null) { throw illegalIndex(index); } Node removed = prev.next; if (removed == tail) { throw illegalIndex(index); } Node next = removed.next; prev.next = next; next.prev = prev; } private IllegalArgumentException illegalIndex(int index) { return new IllegalArgumentException( String.format("index [%d] 不合法%n", index)); } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { Node p = head.next; @Override public boolean hasNext() { return p != tail; } @Override public Integer next() { int value = p.value; p = p.next; return value; } }; } 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; } } }
五、环形链表（带哨兵）
双向环形链表带哨兵，这时哨兵既作为头，也作为尾
参考实现
public class DoublyLinkedListSentinel implements Iterable<Integer> { @Override public Iterator<Integer> iterator() { return new Iterator<>() { Node p = sentinel.next; @Override public boolean hasNext() { return p != sentinel; } @Override public Integer next() { int value = p.value; p = p.next; return value; } }; } 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 final Node sentinel = new Node(null, -1, null); // 哨兵 public DoublyLinkedListSentinel() { sentinel.next = sentinel; sentinel.prev = sentinel; } /** * 添加到第一个 * @param value 待添加值 */ public void addFirst(int value) { Node next = sentinel.next; Node prev = sentinel; Node added = new Node(prev, value, next); prev.next = added; next.prev = added; } /** * 添加到最后一个 * @param value 待添加值 */ public void addLast(int value) { Node prev = sentinel.prev; Node next = sentinel; Node added = new Node(prev, value, next); prev.next = added; next.prev = added; } /** * 删除第一个 */ public void removeFirst() { Node removed = sentinel.next; if (removed == sentinel) { throw new IllegalArgumentException("非法"); } Node a = sentinel; Node b = removed.next; a.next = b; b.prev = a; } /** * 删除最后一个 */ public void removeLast() { Node removed = sentinel.prev; if (removed == sentinel) { throw new IllegalArgumentException("非法"); } Node a = removed.prev; Node b = sentinel; a.next = b; b.prev = a; } /** * 根据值删除节点 * <p>假定 value 在链表中作为 key, 有唯一性</p> * @param value 待删除值 */ public void removeByValue(int value) { Node removed = findNodeByValue(value); if (removed != null) { Node prev = removed.prev; Node next = removed.next; prev.next = next; next.prev = prev; } } private Node findNodeByValue(int value) { Node p = sentinel.next; while (p != sentinel) { if (p.value == value) { return p; } p = p.next; } return null; } }
