Context:
I have a LinkedList class which contains and automatically inserts nodes in the correct order. Note this is a linked list data structure (the array in which the nodes/elements are kept represents RAM, and the pointers - head, tail, as well as next and prev represent addresses in RAM (but in this example, they are indexes of the array in which the nodes are kept).
Eg
myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0
So now when I call my printInOrder function, it will output 1, then 2, then stop.
Note: When I insert a new node, it is pushed to the end of the array, but the pointers of what would be its adjacent nodes are changed (so next and prev) so that the train-like path from the head to the tail includes all nodes in a particular order (default is ascending). So the node which gets inserted always goes at the end, only its pointers signify its position.
My problem:
Here is my problem: (see the code at the end of the question)
Imagine I have created a linked list, which is sorted by default (ascending order), and I have the values 2, 1, and 3. So when I iterate through the list, I will receive 1,2,3. Now, I want to re-order the linked list. What that would mean is, that the index of each node does not change, but the pointers of the nodes do. After all, the pointers are what create the order. So how would I use, some sorting algorithm, say merge or bubble, to sort my nodes without actually changing their order, just their next and prev pointers (and the global head and tail).
My Code
Here is the code so far for the re-sort function, which currently uses bubble sorting but does not work:
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;
}
}
And here is the entire code of my LinkedList class, which will allow you to recreate my problem - which is that the nodes simply do not sort themselves. Their pointers change but not the way they should, and I cannot understand why.
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("When each node is sorted when it is inserted:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
list.print();
