如何从循环链表中删除重复项

How to remove duplicates from circular linked list

我的代码如下。它将一些数字附加到循环列表中。我的程序运行良好。它给出 [5,3,3] 或输入的任何数字的精确输出。但我想对输出进行一些更改。在不添加任何新函数的情况下,在 def append(....)def add_before(...) 中进行什么样的更改,因此它提供了一个唯一的数字,这意味着它摆脱了重复项。例如,将给出 [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 

测试

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

两个选项(我能想到的):

不要重复添加:

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

或者干脆不要重复打印:

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 

如果你想让它模仿这种行为,你必须相应地修改你的 printall() - 你仍然会存储所有重复项,所以对我来说没有多大意义,除非你创建一个单独的 def printNoDuplicates(self) 专门用于此目的。