当前位置：首页 > article >正文

如何实现一个既保证顺序又有快速插入删除的数据结构？

article 2024/11/17 13:21:04

当我们要实现一个既保证顺序又支持快速插入和删除的自定义数据结构，可以考虑使用 双向链表 或跳表，甚至是结合字典和链表的方法，这些数据结构在不同需求场景下能够提供优化的性能。

在这里插入图片描述

1、问题背景

您需要一种既能保证元素顺序又不影响元素插入/删除速度的数据结构。您可以通过该数据结构快速查找、在给定元素前/后插入、删除给定元素、查找第一个和最后一个元素以及从给定元素开始双向迭代。您已经尝试了以下解决方法：一个继承了 collections.abc.Iterable 和 collections.abc.MutableSet 的类，它包含一个链表和一个字典。字典的键是元素，值是链表中的节点。字典用于根据元素查找节点。找到元素后，链表会处理插入前/后、删除和迭代。通过添加或删除相关的键/值对可以更新字典。很明显，使用这种方法，元素必须是可哈希和唯一的（否则，您需要另一层间接寻址，每个元素都由自动分配的数字标识符表示，只有那些标识符才作为键存储）。

2、解决方案

根据 Raymond Hettinger 的 OrderedSet 的配方，稍作修改就可以满足所有要求。只添加了位置访问和读/写支持。

代码示例：

class OrderedSetPlus(collections.MutableSet, collections.Iterable):
    '''
    >>> oset = OrderedSetPlus([3, 3, 3, 2, 1, 8, 8])
    >>> oset.add(13)
    >>> p = oset.find(2)
    >>> oset.add(15, p)
    >>> oset
    OrderedSetPlus([3, 15, 2, 1, 8, 13])
    >>> p = oset.next_pos(p)
    >>> oset[p]
    1
    >>> oset.add(7, p)
    >>> oset
    OrderedSetPlus([3, 15, 2, 7, 1, 8, 13])
    >>> oset[p] = 20
    >>> oset
    OrderedSetPlus([3, 15, 2, 7, 20, 8, 13])
    '''

    class DuplicateElement(Exception):
        pass

    def __init__(self, iterable=None):
        self.end = end = [] 
        end += [None, end, end]         # sentinel node for doubly linked list
        self.map = {}                   # key --> [key, prev, next]
        if iterable is not None:
            self |= iterable

    def __len__(self):
        return len(self.map)

    def __contains__(self, key):
        return key in self.map

    def find(self, key):
        return self.map.get(key, None)

    # inserts element before the specified position
    # if pos is None, inserts at the end
    # position can only be obtained by calling instance methods
    def add(self, key, pos = None):
        if pos is None:
            pos = self.end
        if key not in self.map:
            curr = pos[PREV]
            curr[NEXT] = pos[PREV] = self.map[key] = [key, curr, pos]

    def discard(self, key):
        if key in self.map:        
            key, prev, next = self.map.pop(key)
            prev[NEXT] = next
            next[PREV] = prev

    def __iter__(self):
        end = self.end
        curr = end[NEXT]
        while curr is not end:
            yield curr[KEY]
            curr = curr[NEXT]

    def get_end(self):
        return self.end[PREV]

    def get_start(self):
        return self.end[NEXT]

    def next_pos(self, pos):
        pos = pos[NEXT]
        return None if pos is self.end else pos

    def prev_pos(self, pos):
        pos = pos[PREV]
        return None if pos is self.end else pos

    def __getitem__(self, pos):
        return pos[KEY]

    def __setitem__(self, pos, key):
        if key in self.map:
            raise DuplicateElement
        pos[KEY] = key

    def __reversed__(self):
        end = self.end
        curr = end[PREV]
        while curr is not end:
            yield curr[KEY]
            curr = curr[PREV]

    def popleft(self):
        return self.pop(pos = self.get_start())


    def pop(self, pos=None):
        if not self:
            raise IndexError()
        if pos is None:
            pos = self.get_end()
        key = self[pos]
        #key = next(reversed(self)) if last else next(iter(self))
        self.discard(key)
        return key

    def __repr__(self):
        return '{}({})'.format(self.__class__.__name__, list(self))

    def __eq__(self, other):
        if isinstance(other, OrderedSet):
            return len(self) == len(other) and list(self) == list(other)
        return set(self) == set(other)