So I´m doing some algorithms exercises and I found this problem:

Write code to remove duplicates from an unsorted linked list

I said, ok that´s easy:

def removeDuplicates(A):
    new = []
    for i in A:
        if i not in new:
            new.append(i)
    return new

Which works fine. However, this is what I found on geeksforgeeks.

class Node():
     
    def __init__(self, data):
         
        self.data = data
        self.next = None
 
class LinkedList():
     
    def __init__(self):
         
        # Head of list
        self.head = None
 
    def remove_duplicates(self):
         
        ptr1 = None
        ptr2 = None
        dup = None
        ptr1 = self.head
 
        # Pick elements one by one
        while (ptr1 != None and ptr1.next != None):
             
            ptr2 = ptr1
 
            # Compare the picked element with rest
            # of the elements
            while (ptr2.next != None):
                 
                # If duplicate then delete it
                if (ptr1.data == ptr2.next.data):
                     
                    # Sequence of steps is important here
                    dup = ptr2.next
                    ptr2.next = ptr2.next.next
                else:
                    ptr2 = ptr2.next
                     
            ptr1 = ptr1.next
             
    # Function to print nodes in a
    # given linked list
    def printList(self):
        temp = self.head
         
        while(temp != None):
            print(temp.data, end = " ")
            temp = temp.next
             
        print()
         
# Driver code
list = LinkedList()
list.head = Node(10)
list.head.next = Node(12)
list.head.next.next = Node(11)
list.head.next.next.next = Node(11)
list.head.next.next.next.next = Node(12)
list.head.next.next.next.next.next = Node(11)
list.head.next.next.next.next.next.next = Node(10)
 
print("Linked List before removing duplicates :")
list.printList()
list.remove_duplicates()
print()
print("Linked List after removing duplicates :")
list.printList()

So far I´ve been using python for statistical analysis with given modules and built in functions and I´m quite new with this type of exercises/algorithms.

Why is this a good choice? Has it something to do with the speed of processing?

CodePudding user response：

You can just use the "set" object from python

def removeDuplicates(A):
    return set(A)

CodePudding user response：

There are a few fundamental differences between your solution and the one you copied from Geeks for Geeks.

1. Your code acts on python lists which are python's implementation of dynamic arrays. This is very different from linked lists.
2. Despite using additional space in the form of a new list, your solution is of quadratic time complexity. Reason is that searching in python's list data structure is a linear operation. if i not in new looks short and neat but each time you hit this line, python will search the whole new list to make sure i is not in there.
3. What you can instead do is using a hashing data structure like a set which gives you constant time complexity for lookup and insertion. You can then modify the input array to move the unique elements to the front and at the end remove the extra tail. This would make your algorithm linear.
4. Geek for Geeks code acts on real linked lists. It runs in quadratic time but doesn't use any additional space.

In short, your solution and Geeks for Geeks are apples and oranges. They can't be compared.

Keep in mind that python's list data structure is only in its name like a linked list.