基于数组存储的LinkedList仅调整next/prev指针实现重排序的问题

背景 #

我实现了一个LinkedList类，插入节点时会自动按规则排序。该链表采用特殊存储结构：用存储所有节点/元素的数组模拟RAM，head、tail以及节点的next、prev指针代表RAM地址，在本示例中实际对应存储节点的数组下标。

示例如下：

myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0

此时调用printInOrder方法会依次输出1、2后结束。

注意：插入新节点时，节点始终被追加到数组末尾，仅调整相邻节点的next和prev指针，保证从head到tail的遍历路径符合指定排序规则（默认升序），节点在数组中的下标不会发生变化，仅通过指针标识其逻辑位置。

遇到的问题 #

假设我创建了一个默认升序的链表，插入2、1、3三个值后遍历会得到1、2、3的顺序。现在我需要对链表重新排序，要求所有节点在数组中的下标保持不变，仅调整节点的next、prev指针以及全局的head、tail值来实现排序。我尝试用冒泡排序实现对应的sort方法，但节点指针调整不符合预期，无法完成排序，找不到问题原因。

相关代码 #

目前实现的有问题的冒泡排序sort方法代码如下：

class LinkedList {
  constructor(sortingFunction) {
    this.head;
    this.tail;
    this.list = [];
    this.sortingFunction = sortingFunction ?? ((a, b) => {
      return a < b
    });
  }
  sort(sortingFunction) {
    if (!sortingFunction) {
      return false;
    }
    this.head = null;
    this.tail = null;
    const arr = this.list.map(x => x);
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length; j++) {
        if (!arr[j + 1]?.value) {
          console.log("no");
          continue;
        }
        if (sortingFunction(arr[j].value, arr[j + 1].value)) {
          let tmp_next = arr[j].next;
          let tmp_prev = arr[j].previous;
          arr[j].next = arr[j + 1].next;
          arr[j].previous = arr[j + 1].previous;
          arr[j + 1].next = tmp_next;
          arr[j + 1].previous = tmp_prev;
        }
      }
    }
    this.list = arr;
  }
}

完整的LinkedList类代码如下，可直接复现问题：

class LinkedList {
   constructor(sortingFunction) {
      this.head;
      this.tail;
      this.list = [];
      this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
   }

   some(func) {
      let currentNode = this.list[this.head];
      let index = this.head;
      while(!func(currentNode)) {
         index = currentNode.next;
         currentNode = this.list[index];
         if(index == undefined || index == null) { return -1; }
      }
      return index;
   }
   forEachInOrder(func) {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         func(node);
         current = node.next;
      }
   }
   * iterator() {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         yield node;
         current = node.next;
      }
   }
   
   insert(value) {
      if(!this.list.length) {
         this.head = 0;
         this.tail = 0;
         this.list.push({value, next:null,previous:null});
         return 0;
      }
      let nodeToInsert = {value, next:null,previous:null};
      let indexToInsert = this.head;
      let nthnode = this.list[this.head];
      while(nthnode && this.sortingFunction(nthnode.value, value)) {
         indexToInsert = nthnode.next;
         nthnode = this.list[indexToInsert];
      }
      if(indexToInsert === null) {
         // new tail (biggest)
         nodeToInsert.previous = this.tail;
         this.list[this.tail].next = this.list.length;
         this.tail = this.list.length;
      } else if(indexToInsert === this.head) {
         // new head (smallest)
         nodeToInsert.next = this.head;
         this.list[this.head].previous = this.list.length;
         this.head = this.list.length;
      } else {
         nodeToInsert.next = indexToInsert;
         if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
            this.list[this.list[indexToInsert].previous].next = this.list.length;
         }
         nodeToInsert.previous = this.list[indexToInsert].previous;
         this.list[indexToInsert].previous = this.list.length;
      }
      this.list.push(nodeToInsert);
      return 1;
   }

   reverse() {
      let _temp;
      for(let i = 0; i < this.list.length; i++) {
         _temp = this.list[i].next;
         this.list[i].next = this.list[i].previous;
         this.list[i].previous = _temp;
      }
      _temp = this.head;
      this.head = this.tail;
      this.tail = _temp;
   }
   sort(sortingFunction) {
      if(!sortingFunction) {return false;}
      this.head = null;
      this.tail = null;
      const arr = this.list.map(x=>x);
      for (let i = 0; i < arr.length; i++) {
         for (let j = 0; j < arr.length; j++) {
            if(!arr[j+1]?.value) {continue;}
            if (sortingFunction(arr[j].value, arr[j+1].value)) {
               let tmp_next = arr[j].next;
               let tmp_prev = arr[j].previous;
               arr[j].next = arr[j+1].next;
               arr[j].previous = arr[j+1].previous;
               arr[j+1].next = tmp_next;
               arr[j+1].previous = tmp_prev;
            }
         }
      }
      this.list = arr;
   }

   print() {
      console.log(this.list);
      console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
   }
   printInOrder() {
      let current = this.list[this.head];
      while(current) {
         console.log(current.value);
         current = this.list[current.next];
      }
   }
}


const list = new LinkedList();

list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);



console.log("When each node is sorted when it is inserted:")

list.print();

list.sort((a, b) => {
  return a > b;
});

console.log("Now, when re-sorted:");

list.print();

问题原因 #

你的sort方法存在几个核心错误：

1. 把链表排序当成了普通数组排序，直接交换两个节点的指针，但没有更新这两个节点相邻节点的指针指向，导致整个链表的链路断裂
2. 排序开始直接把head和tail设为null，排序结束后也没有重新赋值，排序完成后根本找不到链表的头尾
3. 用来遍历的arr是list的浅拷贝，修改里面的节点指针其实就是修改原list的节点，this.list = arr属于多余操作
4. 冒泡排序的边界逻辑错误，内层循环不需要每次都遍历整个数组，每轮冒泡后最后i个元素已经有序，不需要重复比较

修复后的代码 #

基础可用版本 #

sort(sortingFunction) {
  const sortFn = sortingFunction || this.sortingFunction;
  const len = this.list.length;
  if (len <= 1) return true;

  // 先按原逻辑顺序提取所有节点到临时数组
  let nodes = [];
  let current = this.head;
  while (current != null) {
    nodes.push(this.list[current]);
    current = this.list[current].next;
  }

  // 执行冒泡排序，仅交换临时数组里的节点顺序
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (sortFn(nodes[j+1].value, nodes[j].value)) {
        [nodes[j], nodes[j+1]] = [nodes[j+1], nodes[j]];
      }
    }
  }

  // 重建所有节点的next、prev指针，以及全局的head、tail
  this.head = this.list.indexOf(nodes[0]);
  this.tail = this.list.indexOf(nodes[len-1]);
  for (let i = 0; i < len; i++) {
    nodes[i].previous = i > 0 ? this.list.indexOf(nodes[i-1]) : null;
    nodes[i].next = i < len -1 ? this.list.indexOf(nodes[i+1]) : null;
  }
  return true;
}

优化版本（避免多次indexOf查询，性能更高） #

sort(sortingFunction) {
  const sortFn = sortingFunction || this.sortingFunction;
  const len = this.list.length;
  if (len <= 1) return true;

  // 提取节点时同时存储对应原数组下标，避免后续重复查询
  let nodes = [];
  let current = this.head;
  while (current != null) {
    nodes.push({
      node: this.list[current],
      idx: current
    });
    current = this.list[current].next;
  }

  // 冒泡排序
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (sortFn(nodes[j+1].node.value, nodes[j].node.value)) {
        [nodes[j], nodes[j+1]] = [nodes[j+1], nodes[j]];
      }
    }
  }

  // 重建指针
  this.head = nodes[0].idx;
  this.tail = nodes[len-1].idx;
  for (let i = 0; i < len; i++) {
    nodes[i].node.previous = i > 0 ? nodes[i-1].idx : null;
    nodes[i].node.next = i < len -1 ? nodes[i+1].idx : null;
  }
  return true;
}

以上实现全程不会修改节点在原数组的下标，仅调整指针和头尾值，完全符合你的要求。

内容的提问来源于stack exchange，提问作者Krokodil