Background:
I have a LinkedList class that organizes and inserts nodes automatically in the correct order. This linked list data structure represents RAM, with the array holding the nodes/elements and the pointers - head, tail, next, and prev representing addresses in RAM (although here they are indexes of the node array).
Example:
myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0
When I call my printInOrder function now, it will display 1, then 2, and stop.
Note: Upon inserting a new node, it is added to the end of the array, but the pointers of its neighboring nodes are adjusted (specifically next and prev) to maintain the desired order from head to tail. The position of the inserted node is indicated solely by its pointers.
The Issue at Hand:
My challenge lies within re-ordering the linked list without changing the index of each node; instead only altering their pointers (next and prev) along with the global head and tail variables. How can I utilize a sorting algorithm like merge or bubble sort to rearrange the nodes based on their values while preserving their original order?
My Code Attempt:
Below is my function for re-sorting the linked list using bubble sorting, which currently does not yield the expected results:
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction || ((a, b) => {
return a < b
});
}
sort(sortingFunction) {
if (!sortingFunction) {
return false;
}
this.head = null;
this.tail = null;
const arr = this.list.map(x => x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (!arr[j + 1]?.value) {
console.log("no");
continue;
}
if (sortingFunction(arr[j].value, arr[j + 1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j + 1].next;
arr[j].previous = arr[j + 1].previous;
arr[j + 1].next = tmp_next;
arr[j + 1].previous = tmp_prev;
}
}
}
this.list = arr;
}
}
Furthermore, below you will find the complete code snippet for my LinkedList class, providing a chance to replicate the issue - as the nodes fail to properly sort themselves despite adjustments made to their pointers. The reason behind this anomaly remains elusive to me.
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) {
let currentNode = this.list[this.head];
let index = this.head;
while(!func(currentNode)) {
index = currentNode.next;
currentNode = this.list[index];
if(index == undefined || index == null) { return -1; }
}
return index;
}
forEachInOrder(func) {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
func(node);
current = node.next;
}
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
yield node;
current = node.next;
}
}
insert(value) {
if(!this.list.length) {
this.head = 0;
this.tail = 0;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
this.list[this.list[indexToInsert].previous].next = this.list.length;
}
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() {
let _temp;
for(let i = 0; i < this.list.length; i++) {
_temp = this.list[i].next;
this.list[i].next = this.list[i].previous;
this.list[i].previous = _temp;
}
_temp = this.head;
this.head = this.tail;
this.tail = _temp;
}
sort(sortingFunction) {
if(!sortingFunction) {return false;}
this.head = null;
this.tail = null;
const arr = this.list.map(x=>x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if(!arr[j+1]?.value) {continue;}
if (sortingFunction(arr[j].value, arr[j+1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j+1].next;
arr[j].previous = arr[j+1].previous;
arr[j+1].next = tmp_next;
arr[j+1].previous = tmp_prev;
}
}
}
this.list = arr;
}
print() {
console.log(this.list);
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
}
printInOrder() {
let current = this.list[this.head];
while(current) {
console.log(current.value);
current = this.list[current.next];
}
}
}
const list = new LinkedList();
list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);
console.log("Nodes sorted upon insertion:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, post-reordering:");
list.print();