Skip to content

双向链表

· 10 min

双向链表：Doubly Linked List

包含两个方向：

image-20250227140504893

双向链表特点：

  1. 每个节点包含 3 个部分

    • value：或者叫做 data，具体的数据
    • next：下一个节点的指针
    • pre：上一个节点的指针

  2. 可以双向遍历

  3. 插入和删除操作更加的灵活

    • 获取前一个节点的时候，不需要像单向链表一样不断的缓存前一个节点

    • 直接通过 pre 属性就可以拿到上一个节点。

    • 举例：假设要移除 current 这个节点

      current.prev.next = current.next
      current.next.prev = current.prev

  4. 相比单向链表，需要更多的内存空间。因为每个节点多了一个 pre 的指针引用。

  5. 书写双链表的方法的时候，需要小心谨慎，因为需要同时维护两个指针。

代码实现#

DoublyLinkedList.js
class Node {
  // 节点当前的数据
  constructor(data) {
    // 每个节点就是三个属性
    this.data = data // 当前节点存储的数据
    this.next = null // 下一个节点的指针
    this.prev = null // 上一个节点的指针
  }
}


class DoublyLinkedList {
  constructor() {
    this.head = null // 双向链表的头节点
    this.tail = null // 双向链表的尾节点
    this.size = 0 // 链表的长度
  }


  // 打印链表
  print() {
    let current = this.head // current --> 头节点
    let result = [] // 存储节点内容
    while (current) {
      result.push(current.data)
      current = current.next // 更新节点
    }
    // 退出上面的while，说明节点已经遍历完毕
    console.log(result.join(' <-> '))
  }
}
module.exports = {
  Node,
  DoublyLinkedList,
}
// 测试文件
const { DoublyLinkedList, Node } = require('./DoublyLinkedList')


// 先创建3个节点
const node1 = new Node(1)
const node2 = new Node(2)
const node3 = new Node(3)


// 接下来，将这3个节点串联成一个双向链表
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2


// 创建一个 DoublyLinkedList 并将 node1 作为头节点
const dl = new DoublyLinkedList()
dl.head = node1
dl.tail = node3
dl.size = 3


// 打印双向链表
dl.print()

双向链表新增节点

  1. 在链表尾部新增一个节点
// 接收一个参数
// 该参数为新的节点的数据
add(item){
  // 生成新的节点
  const newNode = new Node(item);


  if(!this.head){
    // 进入此分支，说明 this.head 为 null
    // this.head 为 null 说明是一个空链表
    // 当前就一个节点，头部也是它，尾部也是它
    this.head = newNode;
    this.tail = newNode;
  } else {
    // 说明当前的双向链表是有节点
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }


  // 无论上面进入哪个分支，都是添加
  // 长度会增长
  this.size++;
}
  1. 在链表指定位置添加节点
// 接收两个参数
// 1. 要插入的下标
// 2. 新节点的数据
addAt(index, item){
  if(index < 0 || index > this.size){
    throw new Error("索引值无效");
  }


  // 创建新的节点
  const newNode = new Node(item);


  // 没有进入上面的if，说明索引没有问题，接下来开始根据索引进行插入操作
  if(index === 0){
    // 进入此分支，说明是要插入到头部
    newNode.next = this.head;
    if(this.head){
      // 因为头节点可能是null，例如空链表的情况
      this.head.prev = newNode;
    }
    this.head = newNode; // 更新头节点
    if(!this.tail){
      // 没有尾节点的时候，会进入此分支
      this.tail = newNode;
    }
  } else if(index === this.size){
    // 进入此分支，说明是要插入到尾部
    this.add(item);
  } else {
    // 插入到中间
    // 这里会涉及到需要找到具体的位置
    let current = this.head;
    let counter = 0; // 计数器，用于标注节点的个数，起到一个类似于数组下标的作用
    while(current){
      if(counter === index){
        // 更新各个节点的指向
        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;
        break;
      }
      // 不停的更新节点
      current = current.next;
      counter++;
    }
  }
  this.size++;
}

删除节点

  1. 删除指定数据节点
// 接收一个参数
// 要删除的数据节点对应的数据
remove(item){
  let current = this.head; // 一开始指向头节点
  while(current){
    // 这里面就需要去寻找对应数据的那个节点
    if(current.data === item){
      // 进入此分支，说明找到了要删除的节点
      if(current === this.head && current === this.tail){
        // 进入此分支，说明整个双向链表只有一个节点
        // 将头尾节点都置为空
        this.head = null;
        this.tail = null;
      } else if(current === this.head){
        // 说明当前要删除的节点是头节点
        this.head = this.head.next;
        this.head.prev = null;
      } else if(current === this.tail){
        // 说明要删除的节点为尾节点
        this.tail = this.tail.prev
        this.tail.next = null;
      } else {
        // 说明就是中间节点
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
      // 无论上面进入哪一个分支，都会删除一个节点
      this.size--;
      return true;
    }
    current = current.next;
  }
  return false;
}
  1. 删除指定索引节点
// 接收一个参数
// 要删除的节点所对应的索引值
removeAt(index){
  if(index < 0 || index >= this.size){
    throw new Error("索引值有误");
  }


  let current = this.head; // 先记录头节点
  let counter = 0; // 计数器，对下标进行计数
  if(index === 0){
    // 进入此分支，说明删除的是头节点
    if(this.head === this.tail){
      // 说明当前的双链表只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
  } else {
    // 说明删除的是后面的节点
    while(current){
      if(counter === index){
        // 找到要删除的节点的时候，会进入该分支
        if(current === this.tail){
          // 说明要删除的节点是尾节点
          this.tail = current.prev; // 更新尾节点
          this.tail.next = null;
        } else {
          // 说明就是中间的节点
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
        break;
      }
      // 不断的更新节点
      current = current.next;
      counter++;
    }
  }
  this.size--;
}

其他方法

  1. 反转链表
reverse(){
  if(!this.head) return; // 如果是空链表，直接返回


  let current = this.head; // 缓存头节点
  let prev = null; // 用于缓存上一个节点
  let next = null; // 用于缓存下一个节点


  while(current){
    next = current.next;
    current.next = prev;
    current.prev = next;
    prev = current;
    current = next;
  }


  // 更新头节点和尾节点
  this.tail = this.head; // 原来的头变成了尾巴
  this.head = prev; // 然后更新头节点
}
  1. 置换链表

接收两个下标值，将对应下标值的节点的内容进行交换

// 接收2个参数
// 是两个下标值
swap(index1, index2){
  if(index1 === index2) return false; // 如果索引相等，不需要交换
  if(index1 < 0 || index1 >= this.size || index2 < 0 || index2 >= this.size){
    throw new Error("索引值有错误");
  }


  let current = this.head; // 记录头节点
  let counter = 0; //计数器，用于记录索引的，类似于数组的下标
  let node1 = null;
  let node2 = null;


  while(current){
    if(counter === index1) node1 = current;
    if(counter === index2) node2 = current;
    if(node1 && node2) break; // 两个节点都找到了，跳出循环
    current = current.next;
    counter++;
  }


  // 找到了两个节点，接下来进行交换操作
  if(node1 && node2){
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }


  return false;
}
  1. 查看长度与是否为空
length(){
  return this.size;
}
isEmpty(){
  return this.size === 0;
}
  1. 遍历链表

允许用户传递一个回调函数，然后对该双向链表所有的节点都应用该回调函数。

类似于数组的 foreach 方法：

const arr = [1, 2, 3]
arr.forEach((item, index) => {
  console.log(item, index)
})
// 接收一个参数
// 该参数是一个回调函数
forEach(fn){
  // 遍历整个链表，将所有的节点扔给这个回调函数
  let current = this.head;
  while(current){
    fn(current);
    current = current.next;
  }
}
  1. 查看节点索引
1000 --> 0
100 --> 7
// 接收一个参数
// 要查找的节点的数据是什么
find(item){
  let current = this.head;
  let counter = 0;
  while(current){
    if(current.data === item){
      // 说明找到了
      return counter;
    }
    current = current.next;
    counter++;
  }
  // 代码走到这儿，说明没有进入过 while 里面的 if
  // 说明没有找到
  return -1;
}

-EOF-