链表 - 双向链表 - 《数据结构与算法》

双向链表的遍历操作
双向链表的插入操作
双向链表的删除操作

相对于单向链表，双向链表的有点是：对于给定的节点，可以从两个方向进行操作，而单向链表只能向后继方向操作，除非持有了该节点的前驱节点。因为双向链表中的节点需要持有其前驱节点以及后驱节点，因此操作上相对于单向链表略微复杂，在存储上也需要更多的存储空间。

下面是一个双向链表的简单示意图。

针对其节点的代码描述为

  @Data
  static class DLLNode<T> {
    // 节点数据
    private T data;
    // 节点的前驱节点，如果该节点为头节点，previous则为NULL
    private Node<T> previous;
    // 节点的后驱节点，如果该节点为尾结点，next则为NULL
    private Node<T> next;
  }

双向链表的遍历操作

双向链表的遍历和单向链表类似，从前向后遍历是相同的代码逻辑，双向链表比单向链表多了一个从后向前的遍历方式，和从前向后遍历大同小异。

public <T> void foreachDLLNode(Node<T> node) {
  // 从前向后遍历
  while (node != null) {
    System.out.println(node.data);
    node = node.next;
  }
  // 从后向前遍历
  while (node != null) {
    System.out.println(node.data);
    node = node.previous;
  }
}

双向链表的插入操作

同单向链表类似，双向链表的插入也分为从链表的头部插入，中间插入以及从尾部插入，下面笔者从这三种方式讲解。

从链表头部插入数据

从链表的头部插入数据分为几部，其示意图如下

将新的节点 A0 的next 指向原表头
将原表头的 previous 指向新节点A0

其代码逻辑如下所示

public static <T> Node<T> insertNode(Node<T> newNode, Node<T> source) {
  newNode.next = source;
  source.previous = newNode;
  return newNode;
}

从链表中间插入数据

从双向链表中间插入数据分为4步，其示意图如下所示

将新节点的 previsou 执行插入点节点 source
将插入点的 source 的next指向新节点
向新节点的next指向 source 的next节点
source的next节点的 previous 指向新节点

public static <T> void insertNode(Node<T> newNode, Node<T> source) {
  // 获取插入节点的后驱节点
  Node<T> next = source.next;
  // 将新节点的前驱设置正确
  newNode.previous = source;
  source.next = newNode;
  // 将新节点的next节点设置正确
  newNode.next = next;
  next.previous = newNode;
}

从链表尾部插入数据

从链表尾部插入数据和从头部插入数据类似，其步骤分为2 步

将尾结点的next执行新节点
向新节点的previous执行尾结点

public static <T> void insertNode(Node<T> newNode, Node<T> end) {
  end.next = newNode;
  newNode.previous = end;
  // 如有必要
  newNode.next = null;
}

双向链表的删除操作

同插入数据一样，删除操作也分为从表头删除，中间删除以及尾部删除

从链表头部删除

其示意图如下

找到新的头部节点，将新的头部节点与原节点断开
将原节点的next断开

返回新的节点

public static <T> Node<T> removeNodeFromHead(Node<T> target) {
// 新的头部节点
Node<T> newHeadNode = target.next;
// 断开与原头节点的关联
target.next = null;
newHeadNode.previous = null;
// help GC
target = null;
return newHeadNode;
}

从链表中间删除

其示意图如下

断开被删除节点D的前驱引用以及后驱引用
将前驱节点C的next指向 E
将后驱节点E的previous 指向 C

public static <T> void removeNode(Node<T> target) {
  // 新的头部节点
  Node<T> next = target.next;
  Node<T> previous = target.previous;
  previous.next = null;
  target.next = null;
  next.previous = null;
  target.previous = null;
  // help GC
  target = null;
  previous.next = next;
  next.previous = previous;
}

从链表尾部删除

从链表尾部删除，和从链表头部删除类似

删除尾部节点E的previous 引用
删除尾部节点E的前驱节点D的next引用

public static <T> void removeNode(Node<T> end) {
  Node<T> previous = end.previous;
  end.previous = null;
  previous.next = null;
  // help GC
  end = null;
}