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();CodePudding user response：
Here's a quick and dirty solution leveraging 
this.headandthis.tailare set tonullbut never set to their appropriate values again.
Your code has a nice iterator() method, which I would like to reuse in your bubble sort, but to avoid that it will use next references that have been altered by a recent swap, I would suggest a tiny change in that generator so it will be immune to that:
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node; // ...so the consumer can safely alter node.next
}
}
And now your sort method can become:
sort(sortingFunction) {
if (!sortingFunction) return;
for (let i = 0; i < this.list.length; i ) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
Here is the whole script where I couldn't resist to use your generator function also in forEachInOrder and some:
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) { // I adapted this to use the iterator
for (const node of this.iterator()) {
if (func(node)) {
return node.previous == null ? this.head : this.list[node.previous].next;
}
}
return -1;
}
forEachInOrder(func) { // I adapted this to use the iterator
for (const node of this.iterator()) func(node);
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node;
}
}
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;}
for (let i = 0; i < this.list.length; i ) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
print() { // I adapted this a bit to get more condense output and add a call to printInOrder
console.log(JSON.stringify(this.list));
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
this.printInOrder();
}
printInOrder() { // I adapted this to use your nice iterator()
console.log(...Array.from(this.iterator(), node => node.value));
}
}
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();Just one more note: your sortingFunction returns a boolean (indicating whether the two given arguments are in their correct order), which is unlike the comparator function that can be passed to the native Array#sort method: there it is expected to return a number, which allows to indicate whether the arguments are in their correct order by returning a negative value, equality with 0 and inversion with a positive value. You might want to follow the same "contract" in your implementation.