数据结构-链表（二）双向链表（带哨兵）

代码实现：

• 构造

  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 27 28

  package LinkedLists; import java.util.NoSuchElementException; public class DoublyLinkedListSentinel { private final Node_ head; private final Node_ tail; // 构造函数 public DoublyLinkedListSentinel() { //头哨兵 head = new Node_(null, 114514, null); //尾哨兵 tail = new Node_(null, 1919810, null); head.next = tail; tail.prev = head; } 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

  private void insert(int index, int value) { Node_ prev = findByIndex(index - 1); if (prev != null) { prev.next = new Node_(prev, value, prev.next); } throw new IndexOutOfBoundsException("非法指针index[" + index + "]"); } private void addLast(int value) { tail.prev.next = new Node_(tail.prev, value, tail); tail.prev = tail.prev.next; }

• 删除

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

  private void remove(int index) { Node_ prev = findByIndex(index - 1); if (prev != null && prev.next != tail) { prev.next.next.prev = prev.next; prev.next = prev.next.next; } throw new IndexOutOfBoundsException("非法指针index[" + index + "]"); } private void removeLast() { if (tail.prev == head) { throw new NoSuchElementException("链表为空，无法删除最后一个元素"); } tail.prev.prev.next = tail; tail.prev = tail.prev.prev; }