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() { // I adapted this to use the (modified) iterator
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
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.
Using a more efficient sorting algorithm
Instead of the O(n²) bubble sort, you could go for a O(nlogn) merge sort.
I have here added a mergeSort method, and a helper method to make a partition: splice. It extracts a section out of the linked list (removing it) and returns it as a new instance. For this splicing to work well, it uses the same list like a shared memory pool, but with its own head and tail. This means that the length of the list is no longer an indication of the size of the linked list, and so some code that referenced length had to change, like the outer loop in the bubble sort routine:
class LinkedList {
constructor(sortingFunction) {
this.head = null; // Initialise with null explicitly
this.tail = null;
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.head == null) { // Avoid using list.length
this.head = this.list.length; // While here it is appropriate to use list.length!
this.tail = this.list.length;
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;
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() {
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
sort(sortingFunction) {
if (!sortingFunction) return false;
let dirty = true;
while (dirty) { // Removed dependency on length
dirty = false;
let prevNode = null;
// Iterate in the current order, so by following the links:
for (const 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;
dirty = true;
} else {
prevNode = currNode;
}
}
}
}
// Added this method which can also be of use for algorithms that use partitioning
splice(head, tail) {
// Remove this slice from the current linked list
if (tail != this.tail) this.list[this.list[tail].next].previous = this.list[head].previous;
else this.tail = this.list[head].previous;
if (head != this.head) this.list[this.list[head].previous].next = this.list[tail].next;
else this.head = this.list[tail].next;
this.list[tail].next = null;
this.list[head].previous = null;
// Wrap the removed slice into a new linked list instance, but one that shares the memory list
let slice = new LinkedList(this.sortingFunction);
slice.list = this.list;
slice.head = head;
slice.tail = tail;
return slice;
}
mergeSort(sortingFunction) {
if (!sortingFunction || this.head == null || this.head == this.tail) return; // base case
// Find last node of first half
let fastIter = this.iterator();
fastIter.next();
let half;
for (half of this.iterator()) {
if (fastIter.next().done || fastIter.next().done) break;
}
// Split list into two halves
let right = this.splice(half.next, this.tail);
let left = this; // ...what remains after the splice.
// Recursively sort the two shorter lists
left.mergeSort(sortingFunction);
right.mergeSort(sortingFunction);
// Make sure the "left" sublist is the one with a head value that comes before the other head value
if (sortingFunction(this.list[right.head].value, this.list[left.head].value)) [left, right] = [right, left];
// Merge the two sorted lists
let tailIndex = left.head;
let otherIndex = right.head;
for (let currIndex = this.list[tailIndex].next; currIndex != null || otherIndex != null; currIndex = this.list[tailIndex].next) {
if (currIndex == null || otherIndex != null && sortingFunction(this.list[otherIndex].value, this.list[currIndex].value)) {
this.list[tailIndex].next = otherIndex;
this.list[otherIndex].previous = tailIndex;
tailIndex = otherIndex;
otherIndex = currIndex;
} else {
tailIndex = currIndex;
}
}
this.head = left.head;
this.tail = tailIndex;
}
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 linked = new LinkedList();
linked.insert(100);
linked.insert(30);
linked.insert(50);
linked.insert(400);
linked.insert(10);
linked.insert(200);
linked.insert(-90);
console.log("When each node is sorted when it is inserted:")
linked.print();
linked.mergeSort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
linked.print();