How to Alphabetically Sort a Linked List in JavaScript

Question

I have a few classes to make a linked list of books. I am having a hard time alphabetically sorting each book and returning them all. I haven't found anything on SO related to sorting linked lists alphabetically in JavaScript specifically so hopefully this post example will be useful for others too. The sortList() function should sort the books alphabetically by their name and return them all so they can be console.log'd.

class Book {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Books {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(element) { //adds a book
    var node = new Book(element);
    var current;
    if (this.head == null) this.head = node;
    else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  insertAt(element, index) { //adds a book at the specified index
    if (index < 0 || index > this.size)
      return console.log("Please enter a valid index.");
    else {
      var node = new Book(element);
      var curr, prev;

      curr = this.head;

      if (index == 0) {
        node.next = this.head;
        this.head = node;
      } else {
        curr = this.head;
        var it = 0;

        while (it < index) {
          it++;
          prev = curr;
          curr = curr.next;
        }

        node.next = curr;
        prev.next = node;
      }
      this.size++;
    }
  }

  sortList() { //sorts the head alphabetically
    var sortedList = new Books();
    let current = this.head;
    var array = new Set();

    while (current != null) {
      array.add(current);
      current = current.link;
    }
    array.sort();

    for (let i = array.length - 1; i >= 0; i--) {
      sortedList.insertAt(new Book(array[i]), 0);
    }

    return sortedList;
  }
}

var bookList = new Books();

bookList.add("abook1");
bookList.add("bbook2");
bookList.add("cbook3");
bookList.add("dbook4");
bookList.add("ebook5");
bookList.add("fbook6");
bookList.add("gbook7");
bookList.add("hbook8");

console.log(bookList.sortList()); //prints out the sorted bookList

trincot · Accepted Answer · 2021-10-21 03:09:09Z

As an alternative solution, here is a merge sort algorithm, which has a time complexity of O(nlogn):

class Book {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Books {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(element) { //adds a book
    var node = new Book(element);
    var current;
    if (this.head == null) this.head = node;
    else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  *values() { // Utility function to facilitate printing
    let current = this.head;
    while (current) {
      yield current.element;
      current = current.next;
    }    
  }

  sortList() { // Sorts the list alphabetically, using merge sort
    if (!this.head || !this.head.next) return; // Nothing to sort
    // Find last node of first half
    let node = this.head;
    for (let fast = node.next; fast?.next; fast = fast.next.next) {
        node = node.next;
    }
    // Split list into two halves
    let that = new Books();
    that.head = node.next;
    node.next = null;
    // Recursively sort the two shorter lists
    this.sortList();
    that.sortList();
    // Merge the two sorted lists
    if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
    let prev = this.head;
    let thatNode = that.head;
    while (prev.next && thatNode) {
      if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
      prev = prev.next;
    }
    if (thatNode) prev.next = thatNode;
    // The sort happened in-place, so we don't return the list
  }
}

let bookList = new Books();
for (let ch of "himvlxpbcyndwjkefuzgqorsat") {
  bookList.add(ch);
}
console.log("input:");
console.log(...bookList.values());
bookList.sortList();
console.log("sorted:");
console.log(...bookList.values());

Comparison of running times.

Here is a comparison between algorithms, using a list of 500 elements, sorted initially in reversed order: "499", "498", "497", ..., "001", "000".

const
    compareString = (a, b) => a.localeCompare(b);

class Book {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Books {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(element) { //adds a book
    var node = new Book(element);
    var current;
    if (this.head == null) this.head = node;
    else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  sortList_NinaScholz() { // Version of 20.10.2021
    let current = this.head;
    while (current.next) {
      if (compareString(current.element, current.next.element) > 0) { // swap
        [current.element, current.next.element] = [current.next.element, current.element];
        current = this.head;
        continue;
      }
      current = current.next;
    }
    return this;
  }
  
  sortList_trincot() {
    if (!this.head?.next) return; // Nothing to sort
    // Find last node of first half
    let node = this.head;
    for (let fast = node.next; fast?.next; fast = fast.next.next) {
        node = node.next;
    }
    // Split list into two halves
    let that = new Books();
    that.head = node.next;
    node.next = null;
    // Recursively sort the two shorter lists
    this.sortList_trincot();
    that.sortList_trincot();
    // Merge the two sorted lists
    if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
    let prev = this.head;
    let thatNode = that.head;
    while (prev.next && thatNode) {
      if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
      prev = prev.next;
    }
    if (thatNode) prev.next = thatNode;
    // The sort happened in-place, so we don't return the list
  }  
}

console.log("running sort...");
setTimeout(function () {
    for (let method of ["trincot", "NinaScholz"]) {
        let bookList = new Books();
        for (let v of [...Array(500).keys()].reverse()) 
            bookList.add(v.toString().padStart(3, "0"));
        let start = performance.now();
        bookList["sortList_" + method]();
        console.log(method, performance.now() - start, "milliseconds");
        // verify that list is really sorted
        for (let book = bookList.head, i=0; book; book = book.next, i++) {
            if (+book.element != i) throw "not well sorted";
        }
    }
}, 100);

Nina Scholz · Accepted Answer · 2021-10-20 17:11:58Z

0

You could change the values from the liked list by checking node and the next node. If necessary swap the values and start the comparing again from head.

This approach takes a comparing function which uses a three-way comparison with a return value of smaller than zero, zero or greater than zero, depending on the order.

const
    compareString = (a, b) => a.localeCompare(b);

class Book {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Books {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(element) { //adds a book
    var node = new Book(element);
    var current;
    if (this.head == null) this.head = node;
    else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  sortList() {
    let current = this.head;
    while (current.next) {
      if (compareString(current.element, current.next.element) > 0) { // swap
        [current.element, current.next.element] = [current.next.element, current.element];
        current = this.head;
        continue;
      }
      current = current.next;
    }
    return this;
  }
}

var bookList = new Books();

bookList.add("ac");
bookList.add("ab");
bookList.add("cc");
bookList.add("bb");
bookList.add("aa");
bookList.add("dd");
bookList.add("ba");
bookList.add("bc");

console.log(bookList.sortList()); //prints out the sorted bookList

edited Oct 20, 2021 at 17:11

answered Oct 20, 2021 at 17:06

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

3 Comments

Nina Scholz Over a year ago

@trincot, yes, nearly.

kindall Over a year ago

It's worse than a bubble sort because it makes only one swap per pass. If you swapped multiple items per pass, that would improve its performance significantly.

trincot Over a year ago

It has O(n³) time complexity. Browser times out for sorting a random list with 2000 short strings.

Collectives™ on Stack Overflow

How to Alphabetically Sort a Linked List in JavaScript

2 Answers 2

Comparison of running times.

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comparison of running times.

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related