在 JavaScript 中的链表中实现排序（冒泡排序或其他）

Question

我正在尝试在 JavaScript 中为链表实现冒泡排序。我一直在寻找类似的问题，但只找到了 C++ 或 Java 中的实现。我将不胜感激你的帮助。做 BubbleSort 会很棒，但如果有其他排序选项，我也会很高兴看到它们的实现。我尝试了不同的选项来实现链表中的排序，但它们没有用。现在我只有在列表的开头或结尾添加元素的方法。下面是列表的实现。

链表节点

export class LinkedListNode {
  public value;
  public prev;
  public next;

  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

链表

import { LinkedListNode } from './LinkedListNode';

export class LinkedList {
  private head;
  private tail;

  addHeadNode = (value) => {
    const newLinkendListNode = new LinkedListNode(value);

    if (!this.head) {
      this.head = newLinkendListNode;
      this.tail = newLinkendListNode;
    } else {
      this.head.prev = newLinkendListNode;
      newLinkendListNode.next = this.head;
      this.head = newLinkendListNode;
    }
  };

  addTailNode = (value) => {
    const newLinkendListNode = new LinkedListNode(value);

    if (!this.tail) {
      this.head = newLinkendListNode;
      this.tail = newLinkendListNode;
    } else {
      this.tail.next = newLinkendListNode;
      newLinkendListNode.prev = this.tail;
      this.tail = newLinkendListNode;
    }
  };

  getByIndex = index => {
    let currentNode = this.head;
    let count = 0;

    while (currentNode) {
      if (count === index) {
        console.log(currentNode);
        return currentNode;
      }
      count++;
      currentNode = currentNode.next;
    }
    return -1;
  };
}

Answer 1

冒泡排序可以通过添加这个方法来实现：

    bubbleSort() {
        let last = this.tail;
        while (last) {
            let node = this.head;
            while (node != last) {
                let next = node.next
                if (node.value > next.value) { // swap
                    [node.value, next.value] = [next.value, node.value];
                }
                node = next;
            }
            last = last.prev; // shorten the range that must be bubbled through
        }
    }

在这里它与您的代码结合（但使用普通 JavaScript，并允许构造函数采用参数）：

class LinkedListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class LinkedList {
    constructor(iterable) { // Allow to initialise from an iterable
        this.head = null;
        this.tail = null;
        if (iterable) {
            for (let value of iterable) this.addTailNode(value);
        }
    }

    addHeadNode(value) {
        const newLinkendListNode = new LinkedListNode(value);

        if (!this.head) {
            this.head = newLinkendListNode;
            this.tail = newLinkendListNode;
        } else {
            this.head.prev = newLinkendListNode;
            newLinkendListNode.next = this.head;
            this.head = newLinkendListNode;
        }
    }

    addTailNode(value) {
        const newLinkendListNode = new LinkedListNode(value);

        if (!this.tail) {
            this.head = newLinkendListNode;
            this.tail = newLinkendListNode;
        } else {
            this.tail.next = newLinkendListNode;
            newLinkendListNode.prev = this.tail;
            this.tail = newLinkendListNode;
        }
    }

    getByIndex(index) {
        let currentNode = this.head;

        while (currentNode) {
            if (!index--) return currentNode;
            currentNode = currentNode.next;
        }
        return null;
    }
    
    bubbleSort() {
        let last = this.tail;
        while (last) {
            let node = this.head;
            while (node != last) {
                let next = node.next
                if (node.value > next.value) { // swap
                    [node.value, next.value] = [next.value, node.value];
                }
                node = next;
            }
            last = last.prev; // shorten the range that must be bubbled through
        }
    }
    
    * [Symbol.iterator]() {
        let node = this.head;
        while (node) {
            yield node.value;
            node = node.next;
        }
    }
    
    toString() {
        return Array.from(this).join(",");
    }
}

// Demo
let list = new LinkedList([1, 10, 5, 7, 3, 2, 9, 8, 4, 6]);
console.log("before:", String(list));
list.bubbleSort();
console.log("after: ", String(list));

请注意，它通过交换值而不是节点来执行交换。这是一个更便宜的操作。

Answer 2

如果我必须对 LinkedList 进行冒泡排序，我会从我所知道的或我能找到的开始。

假设您知道如何对数字进行冒泡排序，并且您决定使用 TypeScript，因为它更容易在以后重构为 LinkedList。

然后我会像这样完成一个基于 class 的实现：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    
  }
}

所以我使用 sort() 的方法在 Sorter 的 class 中定义并初始化了一个数字数组的集合，它将像这样进行实际排序：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    const { length } = this.collection;

  }
}

我解构了集合中的长度，它是一个数字数组。然后，记住一件好事，冒泡排序需要一个 for 循环嵌套在另一个循环中，如下所示：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    const { length } = this.collection;
    
    for (let i =0; i < length; i++) {
      for (let j = 0; j < length - i - 1; j++) {

      }
    }
  }
}

所以记住嵌套的双 for 循环是比较容易的部分，现在我们必须记住在冒泡排序中我们比较两个元素，假设数字 10 和数字 3 而我们要问的是 10 >比 3?如果是这样，交换它们，但我们现在只想编写比较逻辑，它是这样完成的：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    const { length } = this.collection;
    
    for (let i =0; i < length; i++) {
      for (let j = 0; j < length - i - 1; j++) {
        if (this.collection[i] > this.collection[i + 1]) {

        }
      }
    }
  }
}

因此，如果左侧元素更大，则交换它们，我们这样指定：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    const { length } = this.collection;
    
    for (let i =0; i < length; i++) {
      for (let j = 0; j < length - i - 1; j++) {
        if (this.collection[i] > this.collection[i + 1]) {
          const leftHand = this.collection[i];
          this.collection[j] = this.collection[j + 1];
        }
      }
    }
  }
}

所以我分配了 leftHand 边，然后我把右手边扔到左边，用这条线：this.collection[j] = this.collection[j + 1];

然后我需要把左手边扔到右边，像这样：

class Sorter {
  constructor(public collection: number[]) {}

  sort(): void {
    const { length } = this.collection;
    
    for (let i =0; i < length; i++) {
      for (let j = 0; j < length - i - 1; j++) {
        if (this.collection[i] > this.collection[i + 1]) {
          const leftHand = this.collection[i];
          this.collection[j] = this.collection[j + 1];
        }
      }
    }
  }
}

好的，这已经很不错了。那么现在来介绍如何做一个 LinkedList 版本。

我说要在 TypeScript 中执行此操作，因为现在我可以利用一种叫做 interface.

的东西

我怎么赞美接口都不够。接口之所以优秀，不是因为我们可以描述一种类型，而是因为我们可以在一个 class 和另一个 class 之间建立契约，然后说如果你做 xyz，想象一下我要给你的所有功能.

这就是我们关心 TypeScript 接口的原因。

那么接口如何帮助我实现链表？

好吧，我们可以分解一下冒泡排序是做什么的，之前的回答已经提到了一些关于交换的东西，那就是一个。我们可以为此创建一个方法：

interface Sortable {
  swap(leftIndex: number, rightIndex: number): void;
}

所以上面我说 interface 现在有一个 swap() 的方法，参数为 leftIndex 和 rightIndex，两者都是数字，它们 return 没什么。

我们在冒泡排序中还做了什么？在交换之前我们比较，我们问左边的元素是否大于右边的元素？通过进行比较，我们还检查了每个元素的长度。所以我们检查长度并进行比较，所以我们可以像这样将它们添加到接口中：

interface Sortable {
  length: number;
  compare(leftIndex: number, rightIndex: number): boolean;
  swap(leftIndex: number, rightIndex: number): void;
}

现在在 Sorter class 里面，我们可以将 public collection 从必须是多个数组替换为 Sortable 的接口：

class Sorter {
  constructor(public collection: Sortable) {}

sort(): void {
  const { length } = this.collection;

for (let i =0; i < length; i++) {
  for (let j = 0; j < length - i - 1; j++) {
    if (this.collection[i] > this.collection[i + 1]) {
      const leftHand = this.collection[i];
      this.collection[j] = this.collection[j + 1];
    }
   }
  }
 }
}

所以我们在这里所做的很好的事情是采用我们知道适用于数字数组的基本冒泡排序算法并应用接口，以便它也可以适用于其他数据结构，包括 LinkedLists .

我们把交换和比较分开了。所以现在我不再像使用普通数组那样使用 this.collection，而是将其委托给接口，现在我可以说 this.collection.compare() 并传入我要比较的两个索引是 j and j + 1`，我可以像这样对交换方法做同样的事情：

class Sorter {
  constructor(public collection: Sortable) {}

sort(): void {
  const { length } = this.collection;

for (let i =0; i < length; i++) {
  for (let j = 0; j < length - i - 1; j++) {
    if (this.collection.compare(, j + 1)) {
      this.collection.swap(j, j + 1);
    }
   }
  }
 }
}

所以在链表数据结构中我们有一系列不同的节点，每个节点包含一个值。值可以是任意类型，但让我们构建我们的 LinkedList 来存储数字。

一个节点将有一个单一的数字，它也将有一个链中下一个节点的引用。当我们一直走到这里的最后一个节点时，最后一个节点将引用 null 值，这意味着我们已经到达链的末端。

所以我将总共有两个 class，一个节点 class 代表每个单独的节点和一个 LinkedList class，LinkedList class 将有一个对头节点的引用，它还将有一堆与之关联的方法来操作整个列表。

所以LinkedListclass会有一个方法叫length到return总节点数。它将有一个 add 方法来添加一个新节点，一个 at 方法来 return 链中非常特定索引处的元素，比较，交换和一个 print 方法来遍历整个列表并打印出每个它里面的值。

print() 方法的目标是验证我是否已在某个时间点更正排序列表。

在这里，我将首先整理我的 Node 实现。

所以在顶部我添加了一个新的 class 像这样调用节点：

class Node {
  next: Node | null = null;

  constructor(public data: number) {}
}

一个节点有两个属性，一个是数字的值，一个是我试图存储在节点中的实际数字，然后是下一个将是对链中下一个节点的引用，或者它可能是null，如果是，那意味着我已经到达链的末端。

所以我的节点将有两个属性，你看我定义了构造函数并使用了 public 数据的缩短语法，这就是我要在这里跟踪的数字。一个节点有一个带有独立符号的 next 属性因为我不想在创建节点时定义链中的下一个节点，而是我希望能够先创建一个节点然后关联它稍后与链中的其他节点一起使用，这就是为什么我不在构造函数中坚持 next 的原因。

接下来是节点类型，表示我正在引用另一个节点，否则它将是 null 类型。

默认情况下，当我第一次创建这个东西时，它将为空。当我自己创建一个节点时，它不会被附加或引用任何其他节点，所以默认情况下，下一个将是节点。

这是一个节点的全部实现。

现在可以开始拼链表了

在链表内部，我将引用头节点，因此头要么是对节点的引用，要么在我第一次创建链表时它可能为空。如果它为空，则表示链表完全为空，如下所示：

export class LinkedList {
  head: Node | null = null;

所以我说这个东西有一个头属性引用一个节点所以它是节点类型或者是 null 我将它默认为 null，所以 LinkedList 开始时完全是空的。

这是唯一的属性 LinkedList。

从这里开始，就是添加所有的方法。第一个方法是 add 方法，它接受一个数字，它从中创建一个节点并将该节点添加到链的末尾。因此，如果我使用值为 2 的值或数字调用 add，我基本上会找到最后一个节点并坚持到最后一个值为 2 的新节点，并且该新节点将引用 null。

所以我的 add 方法将接收一些我将称为数据的数字，我不期望它 return 任何东西所以我用 return 类型的 void 注释它.

add(data: number): void {
    
}

所以我马上创建一个新的 Node() 并像这样传入该数字数据：

add(data: number): void {
    const node = new Node(data);
}

那么在这里我需要考虑两种不同的情况，我需要确保我确实有一个头，如果我还没有头并且我的列表完全是空的那么我可以采用新节点创建并将其分配给头部属性通过说如果没有头部则 this.head 将是刚刚创建的新 Node() 并且 return 立即像这样：

 add(data: number): void {
   const node = new Node(data);

   if (!this.head) {
     this.head = node;
     return;
 }

注意到我有一个 return 类型的 void 吗？但是我还是输入了 return 语句。当我有一个 return 类型的 void 时，我仍然可以有 return 语句，void 只是意味着我不会专门 return 任何有用的值。

所以我仍然可以 return 如果我愿意，我只是不能 return 一个实际的东西。

在那之后，我将在节点中已经有一个头的情况下，我需要找到链中的最后一个节点并将新创建的节点添加到该节点中。

为此，我必须在这里编写一个 while 循环，我将在此 class 中多次使用它来遍历我的链，如下所示：

export class LinkedList {
  head: Node | null = null;

  add(data: number): void {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
      return;
    }

    let tail = this.head;
    while (tail.next) {
      tail = tail.next;
    }

所以我说的是while tail.next，所以while head node有下一个属性，然后advance那个tail variable with tail是tail.next.

这句话很难让你第一次理解。

所以我要创建一个名为 tail 的变量，默认情况下 tail 将反映或指向头节点。然后我要说，看看 tail，如果 tail 有一个定义的 next 属性，那么换句话说，如果 next 指的是一个实际的节点，那么更新我的 tail 引用并说 tail 现在指的是 next节点。然后我将查看下一个节点，只要它具有定义的下一个属性，然后再次更新尾部引用并转到下一个，我将重复该过程，直到我到达中的最后一个节点链.

当我到达那里时，我说如果 tail.next 指的是某物，在这种情况下它指的是 null，这样当我退出 while 循环时。

所以当命中最后一个节点时，它会在这里被捕获，而 tail 有一个定义的 next 属性，当 tail 最终是最后一个节点时，next 将是未定义的，所以 while 循环将之后不再继续。

一旦找到最后一个节点，我将采用我刚刚创建的节点并将其作为下一个属性添加到尾部，如下所示：

export class LinkedList {
  head: Node | null = null;

  add(data: number): void {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
      return;
    }

    let tail = this.head;
    while (tail.next) {
      tail = tail.next;
    }

    tail.next = node;
  }

因此，一旦我到达最后一个节点，就获取刚刚创建的节点，并让最后一个节点的下一个属性引用我刚刚创建的节点。

那就是add()的第一个方法。

下一个是长度。长度列表必须有一个长度属性，如果它要像这样满足接口：

export class LinkedList {
  head: Node | null = null;

  add(data: number): void {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
      return;
    }

    let tail = this.head;
    while (tail.next) {
      tail = tail.next;
    }

    tail.next = node;
    }

  get length(): number {
    if (!this.head) {
      return 0;
    }

    let length = 1;
    let node = this.head;
    while (node.next) {
      length++;
      node = node.next;
    }

    return length;
  }

因此长度 return 是一个数字，如您所见，长度有很多变化。

在那里我检查了看是否没有头，如果我根本没有头，那么我 return 零，因为列表是空的，如果我通过那个，我设置了一个 while 循环并遍历列表。我创建了一个名为 length 的计数变量并将其初始化为一个。

我使用 let node = this.head;

获得了对更改中第一个节点的引用

所以我再次遍历整个链，一旦我到达最后一个节点，next 将是未定义的，因此 while 循环将中断，此时，长度将反映节点总数我爬过的。

在 while 循环之后我 return 长度。

export class LinkedList {
  head: Node | null = null;

  add(data: number): void {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
      return;
    }

    let tail = this.head;
    while (tail.next) {
      tail = tail.next;
    }

    tail.next = node;
  }

  get length(): number {
    if (!this.head) {
      return 0;
    }

    let length = 1;
    let node = this.head;
    while (node.next) {
      length++;
      node = node.next;
    }

    return length;
  }

  at(index: number): Node {
    if (!this.head) {
      throw new Error("Index out of bounds");
    }
    let counter = 0;
    let node: Node | null = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }
      counter++;
      node = node.next;
    }
    throw new Error("Index out of bounds");
  }

所以再一次快速检查，如果我没有头属性，如果我的 LinkedList 是空的并且我试图在其中获取一些元素，我将抛出一个错误索引越界。

我还设置了一个 while 循环，让第一个节点的计数器为零，然后我创建了一个节点变量来引用 this.head。所以当我有一个节点时，如果计数器等于索引，如果我一直计算到适当的索引，这意味着我找到了我正在寻找的节点，那么在这种情况下 return 节点，否则，然后我需要继续迭代。

计数器加加移动到下一个节点，我将更新节点引用到链上的下一个节点。

因此，如果我最终退出此 while 循环而没有遇到 return 语句，我将再次抛出错误。

基本上，我遍历了找到的整个节点列表，但从未找到与我要查找的节点相同的索引，这意味着有人可能要求的索引太大或大于实际的链表。

注意我添加了一个手动类型注释，其中我说节点可以是 Node 或 null:

let node: Node | null = this.head;

太累了。

所以现在从界面比较交换。

  compare(leftIndex: number, rightIndex: number): boolean {
    if (!this.head) {
      throw new Error("List is empty");
    }
    return this.at(leftIndex).data > this.at(rightIndex).data;
  }

所以这将采用 leftIndex 和 rightIndex，这是一个数字和 return 一个布尔值，这是我立即使用我放在一起的 at 方法的地方。

如果我在列表中没有任何东西，调用比较没有任何意义，所以我会抛出一个新的错误，说列表是空的。

这些错误只是为了涵盖我们可能运行在我们尝试测试代码的奇怪输入时可能遇到的极端情况。

然后我可以 return this.at(leftIndex) 会给我 leftIndex 的节点，我想参考它的数据属性找到实际节点中的数字然后比较它查看它是否大于右侧索引处的节点值。

所以现在交换并打印。

  swap(leftIndex: number, rightIndex: number): void {
    const leftNode = this.at(leftIndex);
    const rightNode = this.at(rightIndex);

    const leftHand = leftNode.data;
    leftNode.data = rightNode.data;
    rightNode.data = leftHand;
  }

在 LinkedList 中交换两个元素可能非常复杂，所以我在这里作弊而不是交换节点，因为如果我交换节点我必须修复所有可能被破坏的不同引用。

我不交换节点，而是交换值，这样更容易。

所以我得到了对左边节点的引用，leftNode is this.at(leftIndex) 然后像以前一样写出一些基本的交换逻辑。

现在打印():

print(): void {
    if (!this.head) {
      return;
    }
    let node: Node | null = this.head;
    while (node) {
      console.log(node.data);
      node = node.next;
    }
  }

所以如果我们没有头并且这个东西是空的，return 马上，否则我用 while 循环遍历列表，当我有一个节点时，做一个控制台日志node.data 并将节点变量更新为链上的下一个节点，再次 node.next 可以是节点或空值。

Answer 3

class Node {
  next: Node | null = null; //setting default value as null
  constructor(public data: number) {}
}

export class LinkedList {
  head: Node | null = null;
  //   even though I say void but we are still use "return". void means we are not returning any specific value.
  add(data: number): void {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
      return;
    }
    let tail = this.head;
    // initially "tail=head" but if tail or head has "next" property, then this next is the tail
    while (tail.next) {
      tail = tail.next;
    }
    // By default node.next=null
    tail.next = node;
  }
  // length is optional. it might be helpful in some cases
  get length(): number {
    if (!this.head) {
      return 0;
    }
    let length = 1;
    let node = this.head;
    while (node.next) {
      length++;
      node = node.next;
    }
    return length;
  }

  // we use this when swapping
  at(index: number): Node {
    if (!this.head) {
      throw new Error("index out of bounds");
    }
    let counter = 0;
    let node: Node | null = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }
      counter++;
      node = node.next;
    }
    // if we hit out of while loop, we throw error. Otherwise ts would give warning because we should be returning "Node"
    throw new Error("INdex out of bounds");
  }

  compare(leftIndex: number, rightIndex: number): boolean {
    if (!this.head) {
      throw new Error("List is empty");
    }
    return this.at(leftIndex).data > this.at(rightIndex).data;
  }
  swap(leftIndex: number, rightIndex: number): void {
    //rather than just swapping nodes, we find the previous ones and change the next values
    const leftNode = this.at(leftIndex);
    const rightNode = this.at(rightIndex);
    const leftHand = leftNode.data;
    leftNode.data = rightNode.data;
    rightNode.data = leftHand;
  }
  print(): void {
    if (!this.head) {
      return;
    }
    let node: Node | null = this.head;
    while (node) {
      console.log(node.data);
      //  this return error because "let node = this.head" ts infers that type of node will be Node but since "node=node.next" and node.next can be null, it shows error
      node = node.next;
    }
  }
}

在 JavaScript 中的链表中实现排序（冒泡排序或其他）

Implement sorting in linked list in JavaScript (bubble sort or another)

javascript

sorting

bubble-sort

doubly-linked-list