How to remove duplicates from circular linked list

Question

My code is given below. It appends some numbers to the circular list. My program works fine. It gives an exact output of [5,3,3] or any numbers entered. But I want to make some changes in the output. without adding any new function what kind of changes to make in the def append(....) and def add_before(...) so it gives a unique number which means it gets rid of the duplicates. for example, will give [5,3]

class CirList:
    def __init__(self):
        head_node = NodeDLL(None)
        head_node.next = head_node
        head_node.prev = head_node
        self.__head = head_node

    def append(self, item):
        curr = self.__head
        new_node = NodeDLL(item, curr, curr.get_prev())
        curr.set_prev(new_node)
        new_node.get_prev().set_next(new_node)

    def add_before(self, item, old_item):
        curr = self.__head.next
        found = False
        while curr.get_data() != None and not found:
            if curr.get_data() == old_item:
                found = True  
            else:
                curr = curr.get_next()
        if found:
            new_node = NodeDLL(item, curr, curr.get_prev())
            curr.set_prev(new_node)
            new_node.get_prev().set_next(new_node)
        return found
    def remove(self, item):
        curr = self.__head.next
        found = False
        while curr.get_data() != None and not found:
            if curr.get_data() == item:
                found = True
            else:
                curr = curr.get_next()
        if found:       
            curr.get_prev().set_next(curr.get_next())
            curr.get_next().set_prev(curr.get_prev())
    def printall(self):
        curr = self.__head.next
        while curr.get_data() != None:
            print(curr.get_data(), end=" ")
            curr = curr.get_next()
        print()
    def __str__(self):
        result = "["
        curr = self.__head.next 
        while curr.get_data() != None:
            result += str(curr.get_data()) + " "
            curr = curr.get_next()
        result = result.rstrip(" ")
        result += "]"
        return result

Test

listA = CirList()
listA.append(5)
listA.append(3)
listA.append(3)
print(listA)

You'll need to search the list to see if it exists and only if it doesn't add it — Nick is tired, May 01 '18 at 09:01
@NickA True. But most of the time, our aim is not to "use a circular linked list" but to "store some items". (Maybe in a particular order, in which case [click here](https://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set).) — Thomas, May 01 '18 at 09:06
@Thomas, true, i cant think of any reasons to actually use a circularly linked list (over some other structure) — Nick is tired, May 01 '18 at 09:07

Patrick Artner · Accepted Answer · 2018-05-01T09:54:27.220

Two options (I can think of):

Don't add duplicates:

class CirList:
    def __init__(self):
        head_node = NodeDLL(None)
        head_node.next = head_node
        head_node.prev = head_node
        self.__head = head_node
        self._knownNumbers = set() # optimized lookup if number known

    def append(self, item):
        if item not in self._knownNumbers: # only add if not known
            self.__knownNumbers__.add(item)
            curr = self.__head
            new_node = NodeDLL(item, curr, curr.get_prev())
            curr.set_prev(new_node)
            new_node.get_prev().set_next(new_node)

    def add_before(self, item, old_item):
        if item not in self._knownNumbers: # only add if not known
            self.__knownNumbers__.add(item)
            curr = self.__head.next
            found = False
            while curr.get_data() != None and not found:
                if curr.get_data() == old_item:
                    found = True  
                else:
                    curr = curr.get_next()
            if found:
                new_node = NodeDLL(item, curr, curr.get_prev())
                curr.set_prev(new_node)
                new_node.get_prev().set_next(new_node)
            return found
    def remove(self, item):
        self._knownNumbers.remove(item) # forget this number again
        curr = self.__head.next
        found = False
        while curr.get_data() != None and not found:
            if curr.get_data() == item:
                found = True
            else:
                curr = curr.get_next()
        if found:       
            curr.get_prev().set_next(curr.get_next())
            curr.get_next().set_prev(curr.get_prev())

Or simply do not print duplicates:

def __str__(self):
    result = "["
    curr = self.__head.next
    known = set() # keep what we added already
    while curr.get_data() != None:
        if curr.get_data() not in known: # only add if not yet added
            result += str(curr.get_data()) + " "
            known.add(curr.get_data())   # remember this one
        curr = curr.get_next()
    result = result.rstrip(" ")
    result += "]"
    return result

You would have to modify your printall() accordingly if you want it to mimic this behaviour - you would still store all duplicates though so does not make much sense to me, unless you create a seperate def printNoDuplicates(self) specificly for this purpose.

Thank you. Would you able to explain me self.__knownNumbers__ = set() in the __init__ function.. is it a function ... — mini, May 01 '18 at 09:37
@mini, have a look at [Sets in Python](https://docs.python.org/3/tutorial/datastructures.html#sets). — Keyur Potdar, May 01 '18 at 09:38
It's a very bad use a `__dunder__` name for that attribute. Names with leading and trailing double underscores like that are reserved for the Python language designers. It's possible (though unlikely, I'll admit) that `__knownNumbers__` will get some interpreter-enforced meaning in the future, which would break code that used it for its own purposes. Just use a normal name instead. I'd also suggest that the questioner use `self.head` instead of `self.__head`. Name mangling is not at all necessary here (it's intended to help mixin and proxy classes avoid name clashes, not for data protection). — Blckknght, May 01 '18 at 09:48
@Blckknght changed `self.__knownNumbers__` to `self._knownNumbers` according to pep-8. Thanks & do not delete the comment - I like to find those gems at answers. — Patrick Artner, May 01 '18 at 09:56
@mini set is a datatype - esssentially an unordered "list" of unique values - no duplicates/no order with a very fast lookup. Think math, middle grades and set theory. Its very good at checking if something is in it, and has several cool operations like union, difference, symetric diff, subset/superset etc. and does lookups in O(1) - much faster then a list can do which has to traverse its element. — Patrick Artner, May 01 '18 at 09:58

How to remove duplicates from circular linked list

1 Answers1