I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Remove Duplicates From a Linked List

10.17.2013
| 13326 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Remove Duplicates from a Linked List

Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list. 


Catch up on all our previous puzzlers here

Comments

Ondřej Smola replied on Thu, 2013/10/17 - 5:53am

Scala solution using bitset

  def removeDuplicates(list : List[Int],bits : BitSet):List[Int]={
  	list match {
  		case Nil => Nil
  		case head :: tail if bits(head) => removeDuplicates(tail, bits)
  		case head :: tail => head ::  removeDuplicates(list, bits + head)
  	}
  }



Frank Dietrich replied on Thu, 2013/10/17 - 6:45am

 Java


import static java.lang.System.out;
import java.util.LinkedList;

class DupesInLinkedList {

	public static void main(String[] args) throws Exception {

		LinkedList<String> list = new LinkedList();
		list.add("2");
		list.add("0");
		list.add("1");
		list.add("3");
		list.add("1");
		list.add("0");
		list.add("1");
		list.add("7");

		int index = 0;
		while (index < list.size()) {
			String element = list.get(index);
			while(list.indexOf(element) != list.lastIndexOf(element)) {
				out.println("remove: " + element);
				list.remove(list.lastIndexOf(element));
			}
			index++;
		}

		for (String element : list) {
			out.println(element);
		}
	}
}

Márcio Ferreira replied on Thu, 2013/10/17 - 7:53am in response to: Ondřej Smola

could be this ? (Groovy)

view sourceprint?1.[1,5,3,2,6,9,1,0,2].unique()​


Mihai Dinca - P... replied on Thu, 2013/10/17 - 7:41am

The shortest way of eliminating duplicates in any list in Java:

List nonDuplicatesList = new ArrayList(new LinkedHashSet(listToProcess));

Maor Leger replied on Thu, 2013/10/17 - 10:10am

In Python (of course it's cheating, since we are not actually traversing the list and changing pointers around):

def removeDupes(l):
	if len(l) == 0:
		return l
	else:
		return [l[0]] + removeDupes(filter(lambda a: a != l[0], l[1:]))

Ramesh Babu Yagnam replied on Thu, 2013/10/17 - 10:20am

ArrayList<Integer> l = new ArrayList<Integer>();l.add(0);l.add(0);l.add(1);l.add(2);l.add(1);l.add(1);l.add(10);l.add(0);l.add(5);l.add(1);for(int i=0;i<l.size();i++){int temp = l.get(i);for(int j=0;j<l.size();j++){if(temp==l.get(j) && i!=j){l.remove(j);}}}System.out.println(l);

Mike P(Okidoky) replied on Thu, 2013/10/17 - 11:12am in response to: Ondřej Smola

Ondřej, I've been coding since the Vic-20 days. I've seen assembler, written assemblers, I've done the Amiga era, wrote compilers, did gaming on early PC DOS, did C++, Windows, DCOM ATL, Linux + Java since the 90s. I've written a ton of code and invented solutions all over the place. I've worked with various development teams, and also independently. 


Yet when I look at a bit of Scala code like this, I can't make any heads or tails from it. I can stare at it and try to comprehend it, but it's pretty darn confusing. Of course, I'm not familiar with the Scale language. But I can just imagine that if one had a larger project that's full of highly compressed dense code like this, that one couldn't just hire people do add to the workforce and expect them to be effective. I think Java is a great language, because I can quickly put Co-Ops to work and sometimes they even contribute something. In a former job, I've seen people lose their jobs because they kept making a mess in C++. Templates not being used properly, destructors not being used properly, memory leaks, writing to freed memory, buffer overruns, etc etc, C++ is full of traps. Java solves much of that. But with Scala I see another trap: not being able to comprehend it. I wonder what it would look like if the code was commented. Then what would a Java equivalent look like and when also commented, how do the two then compare, and is there then still any value from using Scala as opposed to Java?


Joe Gerew replied on Thu, 2013/10/17 - 12:41pm

public class Puzzler {
    public void deDupeList(LinkedList<String> list){
        for (int i = 0; i < list.size(); i++){
            String currentItem = list.get(i);
            while (list.lastIndexOf(currentItem) != i){
                list.removeLastOccurrence(currentItem);
            }
        }
    }
   
    public static void main (String[] args){
        LinkedList<String> list = new LinkedList<String>(); list.add("one"); list.add("two"); list.add("three"); list.add("one"); list.add("two"); list.add("three"); new Puzzler().deDupeList(list);
    }
}

Tero Tukiainen replied on Thu, 2013/10/17 - 1:54pm

In Clojure:

(into '() (into #{} '(:A :B :A :A :D :D :C)))

Ondřej Smola replied on Thu, 2013/10/17 - 2:50pm in response to: Mike P(Okidoky)

Hi Mike,

my professional career is much short than yours (i am working as a developer for 3 years now, last two years working as a developer / technical staff  at Technical  University of Liberec during my graduate studies) writing software mostly in Java EE, Groovy, Javascript and Python + some server administration. In my little spare time studying things around compilers and JVM. I agree that Scala is something that is very hard to understand and quickly grasp ... it is the only language i have ever programmed that when i see some parts of its documentation i just dont get it without example. Some functions documentation  look like from different character set encoding at best :). I am using Scala mainly for algorithmic stuff and some "utility" mini projects -> things i dont want to work with every day. But i have strong passion for Scala, in some sense it just THE perfect language i would like to write my backend Java software every day from now on. It will be for a long discussion so it is time for quick conclusion -> i love Java etc. for it simplicity, stability etc. but there is something in Scala that makes my  brain much more happy :).

Ondřej Smola replied on Thu, 2013/10/17 - 4:18pm in response to: Mike P(Okidoky)

Java solution ( it tries to be closest to my previous scala solution as possible)


public static LinkedList<Integer> removeDuplicates(
			LinkedList<Integer> inputList, BitSet bitSet) {
		Integer head = inputList.pollFirst(); // remove head of linked list (null if empty)
		if (head == null) {
			return new LinkedList<Integer>(); // reconstruct the list, starting with empty list 
		} else if (bitSet.get(head)) {
			return removeDuplicates(inputList, bitSet); //element is duplicate of previous one, skip it 
		} else {
			bitSet.set(head); // remember element already present
			LinkedList<Integer> result = removeDuplicates(inputList, bitSet); // solve all smaller subproblems
			result.push(head); // add actual element to solution
			return result;
		}
	}

Rony Cesana replied on Fri, 2013/10/18 - 11:29am in response to: Ondřej Smola

Doesn't using an auxiliary data structure like BitSet count a little like using a buffer?

This Scala solution uses less structures:

object Thursday {
	def removeDuplicates[T](list: List[T]): List[T] = {
		def purge(list: List[T], value: T): List[T] =
			list match {
				case Nil => Nil
				case head :: tail => 
					if (head == value) 
						purge(tail, value) 
					else  
						head :: purge(tail, value)
			}
		list match {
			case Nil => Nil
			case head :: tail => head :: removeDuplicates(purge(tail, head))
		}
	}
}

If you will, this has the same "feeling" in Java, though it's not using immutable data:

public class LinkedListPurge {
	public static <T> LinkedList<T> removeDuplicates(LinkedList<T> list) {
		if (list == null || list.size() <= 1)
			return list;
		
		T head = list.poll();
		
		return cons(head, removeDuplicates(purge(list, head)));
	}
	
	private static <T> LinkedList<T> cons(T head, LinkedList<T> list) {
		list.push(head);

		return list;
	}

	private static <T> LinkedList<T> purge(LinkedList<T> list, T value) {
		if (list.isEmpty()) {
			return list;
		}

		T head = list.poll();
		
		if (head.equals(value)) {
			return purge(list, value);
		} else {
			return cons(head, purge(list, value));
		}
	}
}


Camilo Rivera replied on Sun, 2013/10/20 - 8:56pm

What do you mean by "Temporary Buffer"? Is it that no other data structure can be used to track repeating elements? Is it that no other data structure can be used to return the result (meaning the input list must be used as output too?

Prashant Yadav replied on Tue, 2013/10/22 - 4:31am

 def purgeDuplicates[T](list: List[T]): List[T] = {

    list match {

      case Nil => List()

      case head :: Nil => List(head)

      case head :: tail => head :: {

        if (tail.contains(head)) purgeDuplicates(tail.filterNot(_ == head))

        else purgeDuplicates(tail)

      }

    }

  }                                               //> purgeDuplicates: [T](list: List[T])List[T]

assert(List(1, 3, 2, 4, 5) ==purgeDuplicates(List(1,3,2,1,4,5)))


Groovy:
def l = new LinkedList([1,2,3,4,2,3,1]) //l = [1,2,3,2,5,4]def unique1(LinkedList list){    new HashSet(list).toList()}assert(unique1(l)==[1, 2, 3, 4])

Arun Kumar replied on Mon, 2013/10/28 - 6:16am

import java.util.ArrayList;

import java.util.List;

import java.util.Set;

import java.util.TreeSet;

public class RemoveDuplication {

/***

@param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

List<String> list = new ArrayList<String>();

list.add("1");

list.add("2");

list.add("3");

list.add("2");

list.add("4");

list.add("5");

Set nonDupVal = removeDuplicate(list);

System.out.println(nonDupVal.toString());

}

// public static List removeDuplicate(List<String> list){

// List lt = new ArrayList();

// for(int i=0;i<list.size();i++){

// for(int j=i+1;j<list.size();j++){

// if(list.get(i)== list.get(j)){

// list.remove(list.get(j));

// }

// }

// }

// return list;

// }

public static Set removeDuplicate(List<String> list){

Set set = new TreeSet();

set.addAll(list);

return set;

}

}


Daniel Sobral replied on Wed, 2013/10/30 - 6:06am in response to: Ondřej Smola

A bitset looks like a temporary buffer to me...

Nikolay Ivanchev replied on Wed, 2013/10/30 - 6:37am

public void removeDupes(int currentPosition, LinkedList list) {
Integer val = list.get(currentPosition);
int index = list.lastIndexOf(val);
if (index > currentPosition) {
list.removeLastOccurrence(val);
removeDupes(currentPosition, list);
} else if (currentPosition < list.size()-1) {
removeDupes(currentPosition+1, list);
}
}

@Test
public void testRemoveDupes() {
LinkedList list= new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(2);
list.add(3);
removeDupes(0, list);
log.info(list);

}

Nikolay Ivanchev replied on Wed, 2013/10/30 - 6:45am

Or if you fancy an approach where it wont use lastIndexOf from Java's LinkedList as used in the previous approach, here is a sample implementation.


  private int lastIndexOf(Integer val, int startPos, LinkedList list) {
for (int i = list.size()-1; i > startPos; i--) {
if (list.get(i) == val) {
return i;
}
}
return startPos;
}


public void removeDupes2(int currentPosition, LinkedList list) {
Integer val = list.get(currentPosition);
int index = lastIndexOf(val, currentPosition, list);
if (index > currentPosition) {
list.remove(index);
removeDupes(currentPosition, list);
} else if (currentPosition < list.size()-1) {
removeDupes(currentPosition+1, list);
}
}

@Test
public void testRemoveDupes() {
LinkedList list= new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(2);
list.add(3);
removeDupes2(0, list);
log.info(list);

}

Sorry for the lack of indentation but a website such as dzone they should really have nice code pasting tool

Vinay Asopa replied on Wed, 2013/10/30 - 5:37pm

public static <T> List<T> removeDuplicates(List<T> inputList){
return new LinkedList<T>(new HashSet<T>(inputList));
}

Vinay Asopa replied on Wed, 2013/10/30 - 10:40pm in response to: Vinay Asopa

To better the solution from memory perspective:

public static <T> List<T> removeDuplicates(List<T> inputList){
Set<T> ouputSet = new HashSet<T>(inputList);
return (List<T>) java.util.Arrays.asList(ouputSet.toArray());
}

fritz schenk replied on Thu, 2013/10/31 - 1:50am in response to: Márcio Ferreira

 Great, I was thinking of converting the list to a Set through method asSet,

Cristian Martin replied on Thu, 2013/10/31 - 2:45am

In javascript:

var a = [2,0,1,3,1,0,1,7];
a.filter(function(el,i){
  for (var j = 0; j < i; j++){
    if (a[j] == el) return false;
  }
  return true;
});
// outputs: [2, 0, 1, 3, 7]

Kamala D'africa replied on Thu, 2013/10/31 - 6:27am

A java implementation

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class UniqueList {
	public static void main(String[] args) {
		final Integer[] elements = { 5, 5, 5, 3, 6, 3, 6, 7, 5, 2, 2, 3, 7, 0, 9, 3, 3, 1, 1, 1 };
		List<?> list = new LinkedList<Integer>(Arrays.asList(elements));

		uniqueList(list);

		System.out.println(list);

		// test
		assert new HashSet<Object>(Arrays.asList(elements)).equals(new HashSet<Object>(list));
	}

	public static void uniqueList(List<?> list) {
		ListIterator<?> iter = list.listIterator();
		while (iter.hasNext()) {
			Object item = iter.next();
			if (list.subList(iter.nextIndex(), list.size()).contains(item)) {
				iter.remove();
			}
		}
	}

}

output: [6, 5, 2, 7, 0, 9, 3, 1]


Yoonyoul Ryu replied on Fri, 2013/11/01 - 11:36am

A java implementation using indexOf and lastIndexOf methods of LinkedList

private static void removeDuplicate(LinkedList<String> linkedList){
		long startTime = System.nanoTime();
		
		ListIterator<String> it = linkedList.listIterator();
		while(it.hasNext()){
			int firstIndex = linkedList.indexOf(it.next());
			int lastIndex = linkedList.lastIndexOf(linkedList.get(firstIndex));
			if(firstIndex != lastIndex){
				it.remove();
			}
		}
		long endTime = System.nanoTime();
		System.out.println((endTime - startTime));
	}


I found the second answer improved performance. Idea of the answer is from LinkedList implements Queue interface.

private static void removeDuplicate2(LinkedList<String> linkedList){
		long startTime = System.nanoTime();
		int loopCnt = linkedList.size();
		for(int i=0;i<loopCnt;i++){
			String em = linkedList.pop();
			if(linkedList.contains(em)) continue;
			linkedList.addLast(em);
		}
		long endTime = System.nanoTime();
		System.out.println((endTime - startTime));
	}



Radosław Więckowski replied on Wed, 2013/11/06 - 2:06pm

Scala solution

  def deduplicate(xs: List[Any]): List[Any] = {
    def deduplicate(xs: List[Any], ys: List[Any]): List[Any] = xs match {
      case x :: rest if ys contains x => deduplicate(rest, ys)
      case x :: rest => deduplicate(rest, x :: ys)
      case Nil => ys
    }
    deduplicate(xs, Nil).reverse
  }

Claudiu Cosar replied on Sat, 2013/11/09 - 4:25pm

    public static <T extends Comparable<T>> List<T> removeDuplicates(Collection<T> duplicates) {
        ContractAssert.notNull(duplicates, "Duplicate Element Container cannot be null!");

        if (duplicates.isEmpty()) {
            return Collections.emptyList();
        }

        final List<T> uniqueElements = new ArrayList<>();
        for(T each: duplicates) {
            if(! uniqueElements.contains(each)) {
                uniqueElements.add(each);
            }
        }
        return uniqueElements;
    }

Paul Murray replied on Sat, 2013/11/23 - 3:17am


Set<Object> items = new HashSet<Object>();
for(Iterator<Object> i = theList.iterator(); i.hasNext();)
 {
  Object o = i.next();
  if(items.contains(o))
    i.delete();
  else
    items.add(o);
}

Neel Shah replied on Wed, 2014/07/02 - 12:55pm

Using additional buffer - We can use Hashtable to remove duplicates from a Linked List. Iterating through the list if the data at new node is found in the hashtable, remove that node.

For code with and without additional buffer http://www.algoqueue.com/algoqueue/default/view/7536640/remove-duplicates-in-an-unsorted-linked-list

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.