Remove Duplicates from Linked List Python
Your logic for removing the duplicated items you find is not right. It causes you to cut out all the items between the first occurrence of a value and a point past its last occurrence. For your example list, that results in a single item, 14
being printed after the deduplication runs (it cuts from just after the first value to the end, though it makes some smaller cuts along the way too).
Here's a fixed version of your removeDups
method.
def removeDups(self):
current = second = self.head
while current is not None:
while second.next is not None: # check second.next here rather than second
if second.next.data == current.data: # check second.next.data, not second.data
second.next = second.next.next # cut second.next out of the list
else:
second = second.next # put this line in an else, to avoid skipping items
current = second = current.next
The main change is that second
points to the node before the second node we're actually interested in checking. We do all our work on second.next
. We need to keep the reference to second
so we can easily cut second.next
out of the list. Doing it this way requires that we don't advance second
if we've cut out a node, so the second = second.next
line needs to be in an else
clause.
Since current
and second
always start with the same value after each update to current
, I changed the logic to assign both of them in a single statement. It would work fine the original way, I just think this way looks nicer.
I think it is confusing to use the "second" variable.
def removeDups(self):
current = self.head
while current: #First loop
while current.next and current.data == current.next.data: #Second loop
current.next = current.next.next #Deletion
current = current.next
You start at the head of the list and for each node in your list until you hit the None at the end (while current) you enter another loop. That loops checks to make sure there is a next node (while current.next) and if that next node has the same data as the current node (current.data == current.next.data). Each time this second loop is true, it means we have a duplicate. The next line (current.next = current.next.next) is what does the actual deletion. It also conveniently updates current.next to the next node in the list that we want to compare so that the second loop can immediately check again to see if we have another duplicate. Once that second loop has found and deleted all the duplicates for that particular node, we will drop down to the next line (current = current.next), update our current node to the next one and start checking that node for duplicates.
We can use a list or dictionary to check whether the item inserted is already there or not
class Node:
def __init__(self,data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def append(self,data):
new_Node=Node(data)
if self.head is None:
self.head=new_Node
return
last_node=self.head
while last_node.next:
last_node=last_node.next
last_node.next=new_Node
def printing(self):
current_node=self.head
while current_node:
print(current_node.data)
current_node=current_node.next
def remove_dup(self):
curr=self.head
glist=[] #list to store the values
while curr:
if curr.data in glist: #checking the value already exists in list
prev.next=curr.next
else:
glist.append(curr.data)
prev=curr
curr=curr.next
llist=LinkedList()
llist.append(1)
llist.append(6)
llist.append(1)
llist.append(4)
llist.append(2)
llist.append(2)
llist.append(4)
llist.remove_dup()
llist.printing()