## Delete dups unsorted linked list ### O(n) time with Buffer If we can have a data structure that keeps track of the recently visited elements we can run through the array and at each point check in O(1) times in our e.g Hashmap if the element exi

unsortedLinkedListDeleteDups.java

public class removeDupsUnsorted {
	
	public static void main(String[] args){
		//Create unsorted linked list
		List<Integer> list = new LinkedList<Integer>();
		list.add(4);
		list.add(3);
		list.add(1);
		list.add(3);
		list.add(6);
		list.add(6);
		list.add(7);
		list.add(1);
		//4 4 1 3 6 6 7 1
		System.out.println("List before deleting dups naively: "+list.toString());
		removeDupsNaive(list);//O(N) time complexity
		System.out.println("List after deleting dups naively: "+list.toString());
	}
	
	//O(N) time complexity
	public static void removeDupsNaive(List<Integer> list){
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i = 0; i < list.size(); i++){
			int elem = list.get(i);
			if(!map.containsKey(elem)){
				map.put(elem, 1);
			}else{
				list.remove(i);
				i--;
			}
		}
	}
}