Remove Duplicates from Linked List Python

Question

I am running below code to remove duplicates from Linked List. But my code only prints linked List before removing duplicates. Once removeDup method is called, it does not print anything. Below is my code. Please tell me what am I missing.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        node = Node(data)
        node.next=self.head
        self.head = node
    
    def printl(self):
        current  = self.head
        while current:
            print current.data
            current= current.next

    def removeDups(self):
        current = self.head
        while current.next is not None:
            if second.data == current.data:
                current.next = current.next.next
            else:
                current=current.next


l= LinkedList()
l.insert(15)
l.insert(14)
l.insert(16)
l.insert(15)
l.insert(15)
l.insert(14)
l.insert(18)
l.insert(159)
l.insert(12)
l.insert(10)
l.insert(15)
l.insert(14)

l.printl()
print "==============="

l.removeDups()
l.printl()

Answer 1

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.

Answer 2

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.

Answer 3

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()