How to Alphabetically Sort a Linked List in JavaScript-CodePudding

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

CodePudding user response：

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

CodePudding user response：

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 i = this.size >> 1; i > 1; i--) {
        node = node.next;
    }
    // Split list into two halves
    let that = new Books();
    that.head = node.next;
    that.size = this.size - (this.size >> 1);
    node.next = null;
    this.size >>= 1;
    // 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;
    }
    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());