Java双向链表的操作

当我们需要对数据进行频繁的插入、删除等动态操作时，使用链表作为数据结构可以达到良好的效果。而双向链表相比单向链表，可以在 O(1) 的时间内实现任一结点的插入、删除或查找前驱、后继等操作。下面是 Java 双向链表的操作攻略。

定义结点类

class DListNode<T> {
  T val;
  DListNode<T> prev, next;
  public DListNode(T val) {
    this.val = val;
    prev = null;
    next = null;
  }
}

定义双向链表类

class DoubleLinkedList<T> {
  DListNode<T> head, tail;
  int size;
  public DoubleLinkedList() {
    head = null;
    tail = null;
    size = 0;
  }
}

其中 head 表示链表的头结点，tail 表示链表的尾节点，size 表示链表的长度。初始时链表为空，即 head 和 tail 都为 null。

插入结点

插入结点时，我们需要新建一个结点，并把该结点插入到链表中。假设我们需要在链表中插入一个值为 val 的结点，插入位置为 pos，则可以使用以下代码：

public void add(T val, int pos) {
  if (pos < 0 || pos > size) {
    // 判断 pos 的合法性
    throw new IndexOutOfBoundsException();
  }
  DListNode<T> node = new DListNode<>(val);
  if (size == 0) {
    // 链表为空时直接把新结点设为头结点和尾节点
    head = node;
    tail = node;
  } else if (pos == 0) {
    // 插入到头部，更新头结点
    node.next = head;
    head.prev = node;
    head = node;
  } else if (pos == size) {
    // 插入到尾部，更新尾节点
    tail.next = node;
    node.prev = tail;
    tail = node;
  } else {
    // 插入到中间位置，找到插入位置的前一个节点 prev，和后一个节点 next，
    // 将新结点的 prev 指向 prev，next 指向 next
    DListNode<T> prev = getNode(pos - 1);
    DListNode<T> next = prev.next;
    prev.next = node;
    node.prev = prev;
    node.next = next;
    next.prev = node;
  }
  size++;
}

// 获取第 pos 个结点
private DListNode<T> getNode(int pos) {
  DListNode<T> node = head;
  for (int i = 0; i < pos; i++) {
    node = node.next;
  }
  return node;
}

删除结点

删除结点时，我们先找到要删除的结点，然后将其断开与前一个节点和后一个节点的连接，最后释放该结点的内存。

public void remove(int pos) {
  if (pos < 0 || pos >= size) {
    // 判断 pos 的合法性
    throw new IndexOutOfBoundsException();
  }
  if (size == 1) {
    // 只有一个节点，删除后链表为空
    head = null;
    tail = null;
  } else if (pos == 0) {
    // 删除头结点
    head = head.next;
    head.prev = null;
  } else if (pos == size - 1) {
    // 删除尾节点
    tail = tail.prev;
    tail.next = null;
  } else {
    // 删除中间节点，找到要删除的节点 prev 和 next，
    // 将 prev 的 next 指向 next，next 的 prev 指向 prev，断开要删除的节点与链表的连接
    DListNode<T> node = getNode(pos);
    DListNode<T> prev = node.prev;
    DListNode<T> next = node.next;
    prev.next = next;
    next.prev = prev;
    node.prev = null;
    node.next = null;
  }
  size--;
}

示例

下面展示向双向链表中插入和删除节点的示例：

DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
// 向双向链表中插入节点：1, 2, 3
list.add(1, 0);
list.add(2, 1);
list.add(3, 2);
// 删除第二个节点
list.remove(1);

执行完上述代码后，链表中的结点为 1 和 3。

DoubleLinkedList<String> list = new DoubleLinkedList<>();
// 向双向链表中插入节点："a", "b", "c"
list.add("a", 0);
list.add("b", 1);
list.add("c", 2);
// 删除第一个节点
list.remove(0);

执行完上述代码后，链表中的结点为 "b" 和 "c"。

以上就是 Java 双向链表的操作攻略，希望能对你有所帮助。