Press "Enter" to skip to content

Remove duplicates from a LinkedList in PHP

Ajk 0

The question we are going to take a look at today is how to remove duplicates from a LinkedList. We’re going to be using PHP for the coding part, just because it’s the language I use more these days. Remember, languages don’t matter as much in this basic interview questions.

So first of all, since we’re doing this in PHP, let’s try to define a simple LinkedList API.

How To Remove Duplicates From a LinkedList in PHP – LinkedList API

This is a very basic implementation to help us answer our question on how to remove duplicates from a LinkedList in PHP.

So let’s jump into thinking about our problem. As always the first thing we should do is ask for clarification on the requirements. When we try to remove duplicates from a LinkedList:

  • Does removing duplicates means manipulating the current list?
  • Should we remove duplicates so elements still stay, or should we remove all elements that are non unique?
  • Are we concerned about any time / space bottlenecks?
  • What’s the size of the list?

So let’s make some assumptions that we got answers for these three questions. We do need to manipulate the current list. We are only removing the dupes (i.e. 5->2->2->3 will result in 5->2->3 not 5->3) and we know the list is not going to be too big so are concerned with time.

Well if we were concerned with space we could have tried to come up with some in-place sorting algorithm that would save auxiliary space, but in this case, our algorithm to remove duplicates from a LinkedList should be as follows:

  1. Loop the LinkedList.
  2. Check elements against a temp hashtable. If element found, then it’s a dupe, if not found, insert it.

Sounds like a simple O(N) algorithm :). Let’s put our words into code!

How To Remove Duplicates From a LinkedList in PHP – Solution

That was about it! Wasn’t too hard! Well next time you get asked how to remove duplicates in a linkedlist in an interview I am sure you will ace it.
Hope you guys enjoyed it… and I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂