Implement Sorting In Linked List In JavaScript (bubble Sort Or Another)
Solution 1:
If I had to do a bubble sort for a LinkedList, I would start with what I do know or what I could find.
Let's assume you knew how to do a bubble sort for numbers and that you decided to go with TypeScript because it was easier to refactor later on into a LinkedList.
I would then have done a class-based implementation like so:
class Sorter {
constructor(public collection: number[]) {}
sort(): void {
}
}
So I defined and initialized a collection of an array of numbers inside a class of Sorter with a method of sort() that will do the actual sorting like so:
class Sorter {
constructor(public collection: number[]) {}
sort(): void {
const { length } = this.collection;
}
}
I destructured out the length from the collection, which is an array of numbers. Then, one thing that is good to remember, a bubble sort requires one for loop nested inside another like so:
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++) {
}
}
}
}
So remembering the nested double for loop is the easy part, now inside we have to remember that in bubble sort we are comparing two elements, let's say the the number 10 and number 3 and we are asking, is 10 > than 3? If so, swap them, but we are just wanting to write the comparison logic for now and it's done like so:
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]) {
}
}
}
}
}
So if the left hand element is greater then swap them and we designate that like so:
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];
}
}
}
}
}
So I assigned the leftHand side, then I took the right hand side and threw it over to the left with this line: this.collection[j] = this.collection[j + 1];
Then I need to take the left hand side and throw it over to the right like so:
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];
}
}
}
}
}
Okay, so this is pretty good. So now on to how to do a LinkedList version of this.
I said to do this in TypeScript because now I can avail myself of something called an interface.
I cannot sing the praises of interfaces enough. Interfaces are excellent not because we can describe a type, but because we can set up a contract between one class and another class and say if you do xyz, imagine all the functionality I am going to give you.
That's why we care about interfaces in TypeScript.
So how can an interface help me with a Linked List implementation?
Well, we can break down what a bubble sort is doing, the previous answer already mentioned something about swapping, so that's one. We can create a method for that:
interface Sortable {
swap(leftIndex: number, rightIndex: number): void;
}
So above I am saying the interface now has a method of swap() with arguments of leftIndex and rightIndex, both are numbers and they return nothing.
What else do we do in bubble sort?, before we swap we compare, we ask is the element on the left greater than the element on the right? By doing that comparison we also check for the length of each element. So we check for length and we compare, so we can add those to the interface like so:
interface Sortable {
length: number;
compare(leftIndex: number, rightIndex: number): boolean;
swap(leftIndex: number, rightIndex: number): void;
}
Now inside of that Sorter class we can replace the public collection from having to be a number of arrays to being the interface of 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];
}
}
}
}
}
So what we are well on our way of doing here is taking this basic bubble sorting algorithm that we know works with an array of numbers and applying an interface so it can then work with other data structures as well, including LinkedLists.
We separated out swapping and comparing. So now rather than working with this.collection as if it were a plain array, I delegated this out to the interface and now I can say this.collection.compare() and pass in the two indices I want to compare which is going to be j and j + 1` and I can do the same thing for the swapping method like so:
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);
}
}
}
}
}
So in a Linked List data structure we have a series of different nodes, every node contains one value. A value can be of any arbitrary type, but let us build our LinkedList to store numbers.
A node is going to have a single number, it's also going to have a reference to the next node inside of a chain. When we get all the way down to the last node right here, the last one is going to reference a value of null and that means we have hit the end of our chain.
So I am going to have two classes in total, a Node class that represents each individual node and a LinkedList class, the LinkedList class will have a reference to the head Node and it's also going to have a bunch of methods associated with it to manipulate the overall list.
So the LinkedList class will have a method called length to return the total number of nodes. It will have an add method to add in a new node, an at method to return the element at a very specific index in the chain, compare, swap and a print method to iterate through the whole list and print out every value inside of it.
The goal of the print() method is to verify that I have corrected sorted the list at some point in time.
Inside of here I will first put together my implementation of a Node.
So at the top I added a new class called Node like so:
class Node {
next: Node | null = null;
constructor(public data: number) {}
}
A node has two properties, a value that’s a number, the actual number I am trying to store in a Node and then next which is going to be a reference to the next node in the chain or it might possibly be null and if it is, that means I have hit the end of the chain.
So my node will have two properties and you see I defined the constructor and used the shortened syntax of public data and that’s the number I am trying to track here. A node has a next property with a stand-alone notation because I don’t want to define the next node in the chain when I create a node, instead I want to be able to create a node first and then associate it with some other node in the chain later on, that’s why I am not sticking next inside the constructor.
Next is going to be of type node to say I am referencing another node or it will be of type null.
By default when I first create this thing it’s going to be null. When I create a node by itself it's not going to be attached or referencing any other node, so by default, next will be node.
That's the total implementation of a node.
Now I can start to put together the linked list.
Inside of the linked list I will have a reference to the head node, so head is going to be either a reference to a node or it might be null when I first create the linked list. If it's null that means the linked list is totally empty like so:
export class LinkedList {
head: Node | null = null;
So I said this thing has a head property that references a node so it's of type node or is null and I defaulted it to null, so the LinkedList starts out as totally empty.
That is the only property that a LinkedList is going to have.
From here on, it's just about adding all the methods. The first method will be the add method that takes in a number, it creates a node out of it and add that node at the end of the chain. So if I call add with a value or number of 2 I will essentially find the last node and stick on to the end a new node with a value of 2 and that new node would reference null.
So my add method will take in some number that I will refer to as data, I don’t expect for it to return anything so I annotated it with a return type of void.
add(data: number): void {
}
So right away I create a new Node() and pass in that number data like so:
add(data: number): void {
const node = new Node(data);
}
So then inside of here I need to consider two different cases, I need to ensure I actually have a head, if I don’t have a head yet and my list is entirely empty then I can take the new node created and assign it to the head property by saying if there is not a head then this.head will be the new Node() just created and return immediately like so:
add(data: number): void {
const node = new Node(data);
if (!this.head) {
this.head = node;
return;
}
Notice how I have a return type of void? But I put in a return statement anyway. When I have a return type of void, I can still have return statements, void just means I am not going to specifically return any useful values.
So I can still return early if I want to, I just can’t return an actual thing.
After that, I will be in the case where I already have a head in the node and I need to find the last node in the chain and add the newly created node to that.
To do so, I have to write out a while loop here that I will be using several times in this class to iterate through my chain like so:
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;
}
So I am saying while tail.next, so while the head node has a next property, then advance that tail variable with tail is tail.next.
This statement is challenging to get your head around the first time.
So I am going to create a variable called tail and by default tail is going to reflect or point at the head node. I am then going to say, look at tail, if tail has a defined next property, so in other words if next is referring to an actual node then update my tail reference and say that tail is now referring to the next node. I will then look at the next node and as long as it has the defined next property, then update the tail reference again and go to the next one, I will repeat that process until I hit the very last node in the chain.
When I get there I say if tail.next refers to something, in that case it refers to null so that when I exit the while loop.
So when hitting the very last node, it will be captured here, while tail has a defined next property, when tail is eventually the very last node, next will be undefined and so the while loop will not continue after that.
Once I find that very last node, I am going to take node I just created and add it as the next property to the tail like so:
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;
}
So once I get to this last node, take the node that was just created and have the next property of the last node refer to the node I just created.
So that is the first method of add().
Next one is length. The length list has to have a length property, if it's going to satisfy the interface like so:
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;
}
So that length returns a number and the length as you can see has a lot going on.
Inside of there I checked to see if there is not a head, if I don’t have a head at all, then I return zero because the list is empty, if I then get past that, I set up a while loop and iterate through the list. I created a counting variable called length and initialized it as one.
I got a reference to the first node in the change with let node = this.head;
So once again I am iterating through the entire chain and once I get to the very last node, next will be undefined and so the while loop will break out, at that point, length will reflect the total number of nodes that I crawled through.
And after the while loop I return length.
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");
}
So once again, a quick check, if I don’t have a head property, if my LinkedList is empty and I am trying to get some element inside of it, I will throw an error of index out of bounds.
I also set up a while loop that says let counter at zero for that first node, I then create a node variable to refer to this.head. So while I have a node, if counter equals index, if I have counted all the way up to the appropriate index that means I found the node I am looking for, so in that case return the node, otherwise, then I need to continue iterating.
Counter plus plus to move on to the next node and I will update the node reference to the next node on the chain.
So if I get out of this while loop eventually without ever hitting the return statement I throw an error again.
Essentially, I went through the entire list of nodes that were found and I never found an index equal to the one I was looking for, which means someone was probably asking for an index that is just too great or larger than the actual Linked List.
Notice I added on a manual type annotation where I said node can either be Node or null:
let node: Node | null = this.head;
That was exhausting.
So now compare and swap from the interface.
compare(leftIndex: number, rightIndex: number): boolean {
if (!this.head) {
throw new Error("List is empty");
}
return this.at(leftIndex).data > this.at(rightIndex).data;
}
So this is going to take leftIndex and rightIndex that’s a number and return a boolean, this is where I immediately use the at method I put together.
If I don’t have anything in the list calling compare does not make any sense, so I will just throw a new error that says list is empty.
The errors are just for covering corner cases that we might run into if we try to test out weird inputs to the code.
Then I can return this.at(leftIndex) that will give me the node at leftIndex, I want to reference its data property to find the number in the actual node and then compare it to see if it's greater than the node value at the right index.
So now swap and print.
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;
}
Swapping two elements inside a LinkedList can be extremely complicated, so I am going to cheat here and not swap the nodes, because if I swap the nodes I have to repair all the different references that might be broken.
Rather than swapping the nodes, I am going to swap the values, which is easier.
So I got a reference to the node on the left with leftNode is this.at(leftIndex) and then just as before write out some basic swapping logic.
Now print():
print(): void {
if (!this.head) {
return;
}
let node: Node | null = this.head;
while (node) {
console.log(node.data);
node = node.next;
}
}
So if we don’t have a head and this thing is empty, return right away, otherwise I iterate through the list with a while loop, while I have a node, do a console log of node.data and update the node variable to the next node on the chain and once again node.next could either be a Node or null.
Solution 2:
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.
Post a Comment for "Implement Sorting In Linked List In JavaScript (bubble Sort Or Another)"