Data Structure Questions: Delete Duplicate Nodes in Singly-Linked List (Javascript)

educative.io

Before diving into this question... What is a Linked List?

A linked list is a data structure made up of a chain of nodes, where each node contains a value and a pointer to another node in the chain.

The head refers to the first node, and the last element (the tail) in the list points to null.

Quick Note: Nodes are essentially objects that point to one another. The value/data in a node can be anything (String, Integer, etc…)

The Problem/Prompt:

Deleting duplicate nodes to produce a linked list with unique nodes is a classic data structure problem. A typical prompt to this question might look like the following:

Prompt:

Write a function which takes in a list and deletes any duplicate nodes from the list. The list is not sorted. The given head pointer may be null indicating that the list is empty.

For example:

input:
1 → 5 → 5 → 6 → 5 → 7 →

output:
1 → 5 → 6 → 7 →

Below is a provided ListNode class.

Basic Node Class implementation. (Javascript)

Tackling the Problem:

When approaching these technical problems I like to think about what are the bare bone necessities in accomplishing this problem?

1.) We need to some how go through the whole list.

This implies some kind of iteration through each node in the list. To do this we can use a while loop.

2.) As we iterate through this list, we need to somehow keep track of what values we have seen already.

A great data structure for this could be Sets. As we iterate through the list, if the node value at an iteration is not within our Set, add the new key.

3.) Return the updated LinkedList, which will be a head node.

Quick note: remember a node points to other nodes, so we are actually returning the whole list when returning the head node.

Implementing the 3 observations I said above

Current implementation, but we still got work to do.

Let’s summarize what the code is doing above:

We have a function that takes in a head node, and before we iterate through the list, we initialized a Set data structure called ‘set’ (line 25) and added the head node’s value to it as a key.

The while loop will continuously execute while the variable, current_node is a ‘truthy’ value.

Throughout this iteration it will add unique node values until we reach the end of the list.

At the end we return head
…
…
wait a minute we haven’t even done anything with head yet, we’re just returning our input.

Updating Node Pointers:

We are almost done, we just need to somehow return an updated head node which will consist of a unique list.

This can be done by creating an additional variable that will initially refer to the head node, continuously update its pointer to the next node, update itself to be current_node ONLY when the current node is a unique value.

what it looks like:

Full implementation

Let’s walk through this code with our input:

(I would recommend writing this down with paper and pencil, because reading and imagining this in your head could be quite intensive)

Given our input 1 → 5 → 5 → 6 → 5 → 7 → null

1. At the first iteration/Beginning of while loop:
   Set = { ‘1’ }
   unique_node = 1 ( node 1 )
   current_node = 5 ( node 2 )
   
   Our Set DOES NOT have ‘5’ as a key so we add it to our set and change unique_node to equal current_node.
   
   Quick Note: Our head node and what it pointed to did not need to change at this iteration because the next node is a unique node.
2. At the Second iteration
   Set = { ‘1’ , ‘5’ }
   unique_node = 5 ( node 2 )
   current_node = 5 ( node 3 )
   
   Our set DOES have ‘5’ as a key so we update unique_node’s pointer to be current_node’s next pointer.
3. At the Third Iteration
   Set = { ‘1’ , ‘5’ }
   unique_node = 5 ( node 2 )
   current_node = 6 ( node 4 )
   
   Our Set DOES NOT have ‘6’ as a key so we add it to our set and change unique_node to equal current_node.
4. At the Fourth Iteration
   Set = { ‘1’ , ‘5’ , ‘6’ }
   unique_node = 6 ( node 4 )
   current_node = 5 ( node 5 )
   
   Our Set DOES have ‘5’ as a key so we so we update unique_node’s pointer to be current_node’s next pointer. (which is node 6, which has value 7)
5. At the Fifth Iteration
   Set = { ‘1’ , ‘5’ , ‘6’ }
   unique_node = 6 ( node 4 )
   current_node = 7 ( node 6)
   
   Our Set DOES NOT have ‘7’ as a key so we add it to our set and change unique_node to equal current_node.
6. At the Sixth and Final Iteration
   Set = { ‘1’ , ‘5’ , ‘6’ , ‘7’ }
   unique_node = 7( node 6)
   current_node = null ( node 7)
   
   current_node is not a “truthy” value, we exit the while loop here and return head, which now points to nodes with new pointers.

Well done we have created a function that returns a linked list that contains unique values!

Here is a main function that you can play around with that can console.log your list.

As I continue to study more data structure problems, I will also continue to share my insights and my thought process of solving them.

Til then,
Banks Out.