Python Program to Remove Duplicates from a Linked List

This is a Python program to remove duplicates from a linked list.

Problem Description

The program creates a linked list and removes duplicates from it.

Problem Solution

1. Create a class Node with instance variables data and next.
2. Create a class LinkedList with instance variables head and last_node.
3. The variable head points to the first element in the linked list while last_node points to the last.
4. Define methods append, get_prev_node, remove and display.
5. The method append takes a data item as argument and appends a node with that data item to the list.
6. The method get_prev_node takes a reference node as argument and returns the previous node. It returns None when the reference node is the first node.
7. The method remove takes a node as argument and removes it from the list.
8. The method display traverses the list from the first node and prints the data of each node.
9. Define a function remove_duplicates which takes a linked list as argument and removes duplicates from it.
10. The function remove_duplicates uses two nested loops to remove duplicate nodes.
11. Create an instance of LinkedList, remove duplicate nodes and display the list.

Program/Source Code

Here is the source code of a Python program to remove duplicates from a linked list. The program output is shown below.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.last_node = None
 
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
 
    def get_prev_node(self, ref_node):
        current = self.head
        while (current and current.next != ref_node):
            current = current.next
        return current
 
    def remove(self, node):
        prev_node = self.get_prev_node(node)
        if prev_node is None:
            self.head = self.head.next
        else:
            prev_node.next = node.next
 
    def display(self):
        current = self.head
        while current:
            print(current.data, end = ' ')
            current = current.next
 
 
def remove_duplicates(llist):
    current1 = llist.head
    while current1:
        data = current1.data
        current2 = current1.next
        while current2:
            if current2.data == data:
                llist.remove(current2)
            current2 = current2.next
        current1 = current1.next
 
 
a_llist = LinkedList()
 
data_list = input('Please enter the elements in the linked list: ').split()
for data in data_list:
    a_llist.append(int(data))
 
remove_duplicates(a_llist)
 
print('The list with duplicates removed: ')
a_llist.display()
Program Explanation

1. An instance of LinkedList is created.
2. The user is prompted to enter the data items for the list.
3. The function remove_duplicates is called to remove duplicates from the list.
4. The linked list is displayed.

advertisement
advertisement
Runtime Test Cases
Case 1:
Please enter the elements in the linked list: 1 5 2 1 4 5 4 5
The list with duplicates removed: 
1 5 2 4 
 
Case 2:
Please enter the elements in the linked list: 3 4 1
The list with duplicates removed: 
3 4 1 
 
Case 3:
Please enter the elements in the linked list: 1 3 3 14 5 1 0
The list with duplicates removed: 
1 3 14 5 0

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.