The program is written here to delete the duplicate elements from the unsorted list. The list is represented here by a 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 unsorted list of duplicate elements be:
The two pointers are taken here to delete the duplicate elements from the list. First, one of the pointers will point to the first node of the list. For each node pointed by ‘ptr’, another pointer will be used which will point the node ‘ptr’ and will traverse the rest of the list for finding the duplicate elements.
Now the data of pointer ‘ptr’ will be compared with the data of ‘next[ptr1]’. As they are not the same, ptr1 will be moved to the next node.
Now, the same process will be repeated i.e. the data of ‘ptr’ will be compared with the data of ‘next[ptr1]’. Now, both the data are the same. So, the address of the node pointed by the pointer ‘ptr1’ will be replaced by the address ‘next[next[ptr1]]’.
After deleting the ‘node’ with duplicate data we will get:
Now, the pointer ‘ptr’ will be moved to the next node and the same process will be continued till all the duplicate data of the list are not get deleted.
After deleting all the duplicate elements from the list we will get:
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
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 ptr1 <- head1
Step 4.2: while ptr1 ≠ NULL and next[ptr1]≠NULL repeat from step 4.3 to 4.6
Step 4.3: Set ptr2 <- ptr1
Step 4.4: while next[ptr2]≠ NULL repeat step 4.5
Step 4.5: if data[ptr1] = data[next[ptr2]] then
Set ptr <- next[ptr2]
Set next[ptr2] = next[next[ptr2]]
Free ptr
else
Set ptr2 <- next[ptr2]
[End of step 4.5 ‘if’]
[End of step 4.4 ‘while’ loop]
Step 4.6: Set ptr1 <- next[ptr1]
[End of step 4.2 ‘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
SPACE COMPLEXITY
Related
Contributed by