1 Write a pseudo code for an algorithm that removes all dupl

1) Write a pseudo code for an algorithm that removes all duplicated numbers given a list of unsorted integers.

2) Analyze the worst-case time complexity of your algorithm in (1) using big-O notation.

Solution

Hi, Please find my two algorithm:

Method 1: two for loop

This is the simple way where two loops are used. Outer loop is used to pick the elements one by one and inner loop compares the picked element with rest of the elements.

void remove_duplicates() {
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;

/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;

/* Compare the picked element with rest of the elements */
while (ptr2.next != null) {

/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {

/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
System.gc();
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}

Time Complexity:
Outer for loop : runs n times
Inner for loop: inner loop run => n , n-1, n-2, n-3 ....., 1 times

so, T(n) = n + n-1 + n-2 + ..... + 1 = n(n+1)/2
Big-O: O(n^2)

Method 2 : Using Hasing
We traverse the link list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table.

Thanks to bearwang for suggesting this method.

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

PSUDO CODE

removeDuplicate(LinkedList head){
  
// creating a HashSet
HashSet set

// traversing through all nodes and if it is notin HashSet then adding both in HashSet and linked list

Node temp = head
set.add(temp)// adding first node in set
while(temp.next != null){

if(set.contains(temp.next))
temp.next = temp.next.next; // skipping this node because it has already seen in list earlier
else{
// adding in set
set.add(temp.next);
// forwarding temp to next node
temp = temp.next;

}
}
}