Linked List - Keeping track of each node-CodePudding

I found an algorithm to loop through a sorted linked list and remove the duplicate. I wrote it, it works.

Still, I don't understand how can this work. In the end of the loop, to move forward into the while loop, we do this :

currentNode = nextNode

How can this not erase the current node ? Why does the linked list is still here ? It feels every node is erased each time by the next, isn't it ?

class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeDuplicatesFromLinkedList(linkedList) {
    let currentNode = linkedList;

while(currentNode !== null){
    let nextNode = currentNode.next;
    
    while(nextNode !== null && nextNode.value === currentNode.value){
        nextNode = nextNode.next;
    }
    
    currentNode.next = nextNode
    currentNode= nextNode
    
}
currentNode = linkedList;

return linkedList;

}

exports.LinkedList = LinkedList;
exports.removeDuplicatesFromLinkedList = removeDuplicatesFromLinkedList;

CodePudding user response：

In fact, linkedList is never overwritten, so the initial list isn't damaged (because when removing duplicates, the first one is kept, only the following are removed).

Then, currNode is just the current pointer, to the current node. Assign a new value to it don't delete the previous node, since it's still referenced through the list head linkedList.

What is really missing is the free instruction on deleted node - this algo rely on a garbage collector to work without a memory leak.

CodePudding user response：

Let's do this by an example:

2 -> 3 -> 3 -> 4

Initially currentNode == 2. In the first iteration of the loop nextNode == 3, which is the next node to current node. The inner while loop doesn't run since currentNode.value isn't equal to nextNode.value. So we hit:

    currentNode.next = nextNode
    currentNode= nextNode

This sets the next node of currentNode to NextNode. So, nothing changes. Then we move current node one forward: currentNode = nextNode

In the next iteration though, nextNode == 3, while currentNode == 3 too. Now the inner while loop runs one iteration and moves nextNode to 4 and breaks since they aren't equal anymore. Then, currentNode.next is set to nextNode, which was 4, and after nextNode is assigned to currentNode.

Since these are all pointers to nodes, nothing is being erased. Just the duplicate values are removed from the chain of linked nodes.