The program is written here to delete the duplicate elements from the sorted list. List is represented here by singly linked list. The singly linked list can be represented in memory as a user-defined data type i.e. by using ‘structure’ or ‘class’.
Each node of the linked list contain two parts-
The structure of the node:
Let the sorted list of duplicate elements be:
Here in this list, the duplicate elements are ‘1’ and ‘3’.
Two pointers will be needed here to delete the duplicate elements from the list. At the beginning, a pointer ‘ptr’ will be pointing to the first node i.e. head.
Here the data of ‘ptr’ is equal to the next node of ‘ptr’, therefore, the element is a duplicate element. So, this element should be removed. For this, a pointer will be pointing to the next node of ‘ptr’.
Now, the address of the node ‘ptr’ will be replaced with the address of the node pointed by the pointer ‘nxt’. The link of the supplicate element will be de-touched.
After removing the duplicate node, the list will be:
Now, the data of ‘ptr’ (here, 1) will be compared with the data of the next node of ‘ptr’ (here, 2). As the data are not same the pointer ‘ptr’ will be moved to the next node.
Now, again the same process will be followed. There is another duplicate data ‘3’ which will be deleted using the same process as explained previously. After, deleting the duplicate elements from the list, the new list will be:
INPUT: The number of elements to create the list and the elements which are to be inserted.
OUTPUT: a) The list after creating it.
b) The list after deleting the duplicate elements from it.
PROCESS:
Step 1: Define a structure named ‘node’ which has two parts−
• The data part of integer type.
• The ‘next’ (points to it’s next node i.e. the address of the next node) part which is a structure(node) type pointer.
Step 2: Create a function “void createlist()”
Step 2.1: Take the number of elements from user in an ‘integer’ type variable ‘n’
Step 2.2: For i=0 to (n-1) repeat Step 2.3 to Step 2.7.
Step 2.3: Take the element which is to be inserted in an integer type variable ‘x’.
Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.
Set data[p] <- x
Set next[p] <- Null
Step 2.5: If (head1 = Null) then
Set head1 <- p
[End of ‘If’ ]
Step 2.6: Else
Set next[ptr] <- p
[End of ‘Else’]
Step 2.7: Set ptr <-p
[End of Step 2.2 ‘For’ loop]
[End of the function “void createlist( )”]
Step 3: Create a function “void displaylist()”
Step 3.1: Set p <-head1
Step 3.2: While(p≠Null) then repeat Step 3.3 and Step 3.4
Step 3.3: Print data[p]
Step 3.4: Set p<-next[p]
[End of Step 3.2 ‘While’ loop]
[End of the function “void displaylist( )”]
Step 4: Create a function “void remove()”
Step 4.1: Set ptr<-head1
Step 4.2: if ptr= NULL then
Return
[End of step 4.2 ‘if’]
Step 4.3: while next[ptr]≠ NULL repeat Step 4.4
Step 4.4: if data[ptr] = data[next[ptr]] then
Set nxt <- next[next[ptr]]
Set next[ptr]<- nxt
else
Set ptr <- next[ptr]
[End of Step 4.4 ‘if’]
[End of Step 4.3 ‘while’ loop]
[End of function ‘remove()’]
Step 5: [Function ‘main()’]
Call the function ‘createlist()’
Call the function ‘displaylist()’
Call the function ‘remove()’
Step 6: Stop.
ADVANTAGES:
1. The main advantage of using a linked list is the dynamic allocation of memory. No wastage of memory is taken place as the memory is allocated for each element at the runtime.
DISADVANTAGES:
1. The extra memory space is required to store the address of the next node.
TIME COMPLEXITY
The time complexity to delete the duplicate elements from the sorted list is O(n) where n is the number of nodes of the list.
SPACE COMPLEXITY
The space complexity of removing the duplicate elements from the sorted list is O(n) where n is the number of nodes of the list.
Related
Contributed by