#
Delete Duplicates

/*************************************************************************** * Author: Isai Damier * Title: Singly Linked List * Project: geekviewpoint * Package: datastructure * * Description: A LinkedList is a data structure that allows access * to a collection of data using pointers/references. While an * array can also be defined as above, LinkedLists and arrays differ * in how they are stored in memory and in the operations they * allow. Unlike an array that must be stored in a block of memory, * the nodes of a LinkedList can be stored anywhere because each * node has a reference to the node that succeeds it. Because the * nodes are stored so loosely, inserting nodes into a LinkedList * is easy; whereas in an array, all the succeeding elements must * be shifted. Of course, insertion also means changing the size of * the array, which means creating the entire array anew. * * Perhaps the greatest beauty of LinkedList is that it allows * accessing an entire sequence of nodes using only one variable: * a reference to the first node in the sequence. * * Countless operations can be performed on LinkedLists. Following * are a few, ranging from the common to the very interesting. **************************************************************************/ public class SinglyLinkedList { Node head = null; Node tail = null; /***************************************************************** * Time Complexity of Solution: * O(n). * * Description: Delete all duplicates from this list, such that * iabcdeafgdc becomes iabcdefg * * Technical Details: The easiest way to remove duplicates from * a collection tends to be with a hashmap. Here is a process: * 0] traverse the list, sending data to a linked hashmap, which * discards duplicates. (Do deleteFromHead if acceptable) * 1] empty the linked hashmap into a new linked list. * Time Complexity is O(n); Space Complexity is O(n) *****************************************************************/ public void deleteDuplicates() {//min, max, avg, sum, size Map<Integer, Integer> noDups = new LinkedHashMap<Integer, Integer>(); Node t = null; while (null != (t = this.deleteFromHead())) //if(!noDups.containsKey(t.data)): not necessary { noDups.put(t.data, 1); } //reconstruct linkedlist for (int k : noDups.keySet()) { addToTail(k); } } }

public class SinglyLinkedListTest { /** * Test of deleteDuplicates method, of class SinglyLinkedList. */ @Test public void testDeleteDuplicates() { System.out.println("deleteDuplicates"); int[] input = {2, 19, 11, 5, 17, 11, 1, 17, 2, 11}; SinglyLinkedList linkedList = new SinglyLinkedList(); for (int i = 0; i < input.length; i++) { linkedList.addToTail(input[i]); } int[] exp = {2, 19, 11, 5, 17, 1}; linkedList.deleteDuplicates(); assertTrue(Arrays.equals(exp, linkedList.toArray())); } }