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

Question

I am trying to implement Bubble sort for a linked list in JavaScript. I was looking for similar questions but only found implementation in C ++ or Java. I would be grateful for your help. It would be great to do BubbleSort but if there are other sorting options, I will also be happy to see their implementation. I tried different options to implement sorting in the linked list but they didn't work. Now I just have methods that add elements in begin or end of the list. Below is the implementation of the list.

LinkedListNode

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

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

LinkedList

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

Bubble sort can be implemented by adding this method:

    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
        }
    }

Here it is combined with your code (but using plain JavaScript, and allowing the constructor to take an argument):

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));

Note that it performs the swap by swapping the values, not the nodes. This is a cheaper operation.