JavaScript 双向链表插入排序实现详解

为什么选择双向链表排序

在基于数组的插入排序中，为了在指定位置插入新元素，需要将该位置之后的所有元素向后移动一位，这在最坏情况下（如逆序数组）会导致大量的数据搬移操作，时间复杂度虽为 O(n²)，但常数因子较大。

换成链表结构后，逻辑发生了本质变化。链表节点在内存中无需连续存储，我们只需要修改节点的 prev（前驱）和 next（后继）指针即可改变连接关系。因此，在进行插入排序时：

1. 根据每个节点的前驱指针，向前扫描找到合适的插入点。
2. 将目标节点从原链表位置“摘下”（断开与前驱、后继的连接）。
3. 将链表在插入点处视为断开，把目标节点重新“接”入正确的位置。

这种基于指针调整的操作避免了大规模的数据复制，是链表排序的优势所在。

核心实现步骤

第1步：构建双向链表基础结构

首先需要定义节点类和链表类。为了方便处理边界情况，通常设置一个不存储实际数据的头节点作为哨兵位，有效数据从头节点后的第一个节点开始。

• 节点类 (Node)：包含 data（数据）、next（后继指针）和 prev（前驱指针）。
• 链表类 (DbLinkList)：包含 head（头节点）以及插入、删除、打印等方法。

第2步：实现插入排序算法 (insertSort)

插入排序的核心逻辑是从左向右遍历链表中的每一个待排序节点 p，将其插入到左侧已经有序的子链表中。具体操作如下：

1. 初始化：若链表为空或只有一个元素，直接返回；否则令指针 p 指向第一个实际元素。
2. 寻找插入点：对于当前节点 p，使用指针 t 从 p.prev 开始向前遍历。当 t.data > p.data 时继续向前，直到 t.prev == null 或 t.data <= p.data。此时 t 即为 p 应插入的位置的后继节点的前驱。
3. 判断是否需调整：如果 t.next == p，说明 p 已经在正确位置，无需任何操作，直接进入下一轮循环。
4. 断开连接（摘除）： - 保存 p.next 到变量 x，以便下一轮循环时知道从哪个节点继续。 - 更新 p 原有前驱的 next 指针，跳过 p。 - 更新 p 原有后继（如有）的 prev 指针，指回 p 的前驱。
5. 重新连接（插入）： - 将 p 的 next 指向 t.next。 - 将 p 的 prev 指向 t。 - 将 t 的 next 指向 p。 - 如果 t.next（即原 p.next）存在，将其 prev 指向 p。
6. 迭代：将 p 更新为之前保存的 x，继续处理下一个节点。

<!doctype html>
<html>
<head>
  <title>双链表-插入排序</title>
  <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
  //节点类
  var Node = function (pData) {
    this.next = null; //后继“指针”
    this.prev = null; //前驱"指针"
    this.data = pData;
  }
  //单链表(约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始)
  var DbLinkList = function () {
    this.head = new Node(null); //头节点   
    //插入新元素
    this.insert = function (pNodeValue) {
      var newNode = new Node(pNodeValue);
      //如果只有头节点
      if (this.head.next == null) {
        this.head.next = newNode;
        newNode.prev = this.head;
        return;
      }
      //否则遍历找到尾节点
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = newNode;
      newNode.prev = p;
    }
    //获取第n个元素的数据值
    this.getData = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      while (p.next != null && i <= index) {
        p = p.next;
        i += 1;
      }
      return p.data;
    }
    //取尾节点
    this.getTail = function () {
      if (this.head.next == null) {
        return null;
      }
      var p = this.head.next;
      while (p.next != null) {
        p = p.next;
      }
      return p;
    }
    //删除指定位置的元素
    this.removeAt = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      //从头开始遍历，找到index位置的前一个元素
      while (p.next != null && i < index) {
        p = p.next;
        i += 1;
      }
      p.next = p.next.next; //修改index位置前一个元素的后继指针
      p.next.prev = p;
      return p.data; //返回删除元素的值    
    }
    //打印所有元素
    this.print = function () {
      document.write("<br/>");
      if (this.head.next == null) {
        return;
      }
      var p = this.head.next;
      while (p.next != null) {
        document.write(p.data + " ");
        p = p.next;
      }
      document.write(p.data + " "); //最后一个元素，需要单独打印
      document.write("<br/>");
    }
    //从后打印所有元素
    this.printFromBack = function () {
      document.write("该链表共有" + this.size + "个元素，从后向前分别为:<br/>");
      var tail = this.getTail();
      var p = tail;
      if (p == null) {
        return;
      }
      while (p.prev != null) {
        document.write(p.data + " ");
        p = p.prev;
      }
      document.write("<br/>");
    }
    //插入排序
    this.insertSort = function () {
      if (this.head.next == null || this.head.next.next == null) {
        return;
      }
      var p = this.head.next;
      while (true) {
        if (p == null) {
          return;
        }
        var t = p.prev;
        //向前查找p之前的插入点
        while (t.prev != null && t.data > p.data) {
          t = t.prev;
        }
        //如果插入点就是p的前驱节点，不用调整，
        //忽略，直接进入下一轮
        if (t.next == p) {
          p = p.next;
          continue;
        }
        //将p的后续节点先保护起来，以便下一轮循环时确定起始位置
        var x = p.next;
        //将p从链表上摘下
        if (p.next != null) {
          p.next.prev = p.prev;
        }
        p.prev.next = p.next;
        //p插入到t之后
        t.next.prev = p;
        p.next = t.next;
        t.next = p;
        p.prev = t;
        this.print(); //打印输出，调试用  
        //重新将p定位到下一轮循环的"正确"起始节点
        p = x;
      }
    }
  }
  var linkTest = new DbLinkList();
  linkTest.insert(10);
  linkTest.insert(9);
  linkTest.insert(8);
  linkTest.insert(7);
  linkTest.insert(6);
  linkTest.insert(5);
  linkTest.insert(4);
  linkTest.insert(3);
  linkTest.insert(2);
  linkTest.insert(1);
  document.write("--排序前---<br/>")
  linkTest.print();
  linkTest.insertSort();
  document.write("<br/>--排序后---<br/>")
  linkTest.print();
</script>
</html>

运行结果分析

执行上述代码，控制台将输出每一步排序的过程及最终结果。以下是典型的输出日志：

--排序前---
10 9 8 7 6 5 4 3 2 1 

9 10 8 7 6 5 4 3 2 1 
...
1 2 3 4 5 6 7 8 9 10 

--排序后---
1 2 3 4 5 6 7 8 9 10

可以看出，算法逐步将较小的元素向左移动，最终形成一个有序的升序链表。虽然时间复杂度仍为 O(n²)，但在链表场景下，其空间复杂度仅为 O(1)（不计输入存储空间），且没有数据拷贝开销。

总结

双向链表的插入排序关键在于准确处理 prev 和 next 指针的断连与重连。通过预存下一个待处理节点的方式，可以避免因当前节点被移出链表而导致的指针丢失。以上就是 JavaScript 双向链表插入排序实现的详细内容，更多关于 JavaScript 数据结构与算法的资料请关注本站其它相关文章！