Python 链表 O(1) 插入/删除

Python linked list O(1) insert/remove

提问by eclectocrat

I am looking for a linked list and related algorithms implementation for Python. Everyone I ask just recommends using built in Python lists, but performance measurements indicate that list insertion and removal is a bottleneck for our application. It's trivial to implement a simple linked list, but I wonder if there is a mature library which includes some operations like sort, merge, splice, search, lower/upper bound, etc...

我正在寻找 Python 的链表和相关算法实现。我问的每个人都只推荐使用内置的 Python 列表，但性能测量表明列表插入和删除是我们应用程序的瓶颈。实现一个简单的链表是微不足道的，但我想知道是否有一个成熟的库，其中包括一些操作，如排序、合并、拼接、搜索、下/上界等......

I know this is a dupe, but searching for python list on any search engine gives predictably poor results, with most people just saying that linked lists are unneeded in python (pfft!).

我知道这是一个骗局，但是在任何搜索引擎上搜索 python 列表都会给出可预见的糟糕结果，大多数人只是说 python 中不需要链表（pfft！）。

PS: I need to insert and remove from anywhere in the list, not just the ends.

PS：我需要从列表中的任何位置插入和删除，而不仅仅是末端。

OK, you asked for it: I need to maintain an ordered list of several hundred thousand entries. I will iterate over the list forwards (one by one), using a visitor on each entry, starting from the beginning or a position found by a binary search. When an entry matching a predicate is found it is removed from the list, and then, another binary search is performed on a subset of the list beginning from the removed entry's previous position, until a position determined statistically beforehand. Ignoring the error condition, the modified entry may be used to create another linked list which is spliced into the new position found through the second binary search. Iteration is continued from the position where the entry was removed. On occasion, several thousand contiguous ordered entries may be added to/removed from any place in the list. Sometimes several thousand non-contiguous entries must be searched for and removed incrementally.

好的，您要求它：我需要维护一个包含数十万个条目的有序列表。我将遍历列表（一个接一个），在每个条目上使用一个访问者，从头开始或从二进制搜索找到的位置开始。当找到匹配谓词的条目时，将其从列表中删除，然后，从删除条目的先前位置开始，对列表的子集执行另一次二分搜索，直到预先统计确定的位置。忽略错误条件，修改后的条目可用于创建另一个链表，该链表拼接到通过第二次二分查找找到的新位置。从条目被移除的位置继续迭代。有时，可能会向列表中的任何位置添加/删除数千个连续的有序条目。

python's list is unnacceptable as the cost of insertion/removal is prohibitive, and the minor gains in speed for the binary search are totally irrelevant to the total cost. Our in house tests confirm this.

python 的列表是不可接受的，因为插入/删除的成本高得令人望而却步，而且二分查找速度的微小提高与总成本完全无关。我们的内部测试证实了这一点。

if I have neglected any detail perhaps I can e-mail you a copy of my company's non-disclosure agreement and I can privately correspond with you on the matter. sarcasm.end().

如果我忽略了任何细节，也许我可以通过电子邮件将我公司的保密协议的副本发送给您，然后我可以就此事私下与您通信。讽刺结束（）。

回答by Eli Bendersky

Here's a blog postsharing your pain. It includes an implementation of a linked list and a performance comparison.

这是一篇博文，分享您的痛苦。它包括一个链表的实现和一个性能比较。

---

---

Perhaps blistwould be better, though (from here)?

blist不过（从这里开始）也许会更好？

The use cases where the BList is slightly slower than Python's list are as follows (O(log n) vs. O(1)):

1. A large list that never changes length.
2. A large lists where inserts and deletes are only at the end of the list (LIFO).

With that disclaimer out of the way, here are some of the use cases where the BLists is dramatically faster than the built-in list:

1. Insertion into or removal from a large list (O(log n) vs. O(n))
2. Taking large slices of large lists (O(log n) vs O(n))
3. Making shallow copies of large lists (O(1) vs. O(n))
4. Changing large slices of large lists (O(log n + log k) vs. O(n + k))
5. Multiplying a list to make a large, sparse list (O(log k) vs. O(kn))

BList 比 Python 的列表稍慢的用例如下（O(log n) vs. O(1)）：

1. 一个永远不会改变长度的大列表。
2. 插入和删除仅在列表末尾 (LIFO) 的大型列表。

有了免责声明，这里有一些用例，其中 BLists 比内置列表快得多：

1. 插入大列表或从大列表中删除（O(log n) vs. O(n)）
2. 获取大列表的大切片（O(log n) vs O(n)）
3. 制作大列表的浅拷贝（O(1) vs. O(n)）
4. 改变大列表的大片（O(log n + log k) vs. O(n + k)）
5. 将一个列表相乘以生成一个大的、稀疏的列表（O(log k) vs. O(kn)）

Note that it's actually implemented as a B+ tree, allowing great performance for all those operations.

请注意，它实际上是作为 B+ 树实现的，从而为所有这些操作提供了出色的性能。

回答by C. A. McCann

Python lists are O(1) for operations at the end of the list. If you'll be doing all your inserting in a semi-sequential fashion--by analogy to C, only keeping a single pointer into the middle of the list as a "cursor" of sorts--you could save yourself a lot of effort by just using two Python lists. One list for what's before the cursor, one for what's after; moving the cursor involves pulling the next item from one list and appending it to the other. That gives you arbitrary O(1) inserting at the cursor location with far less effort and wheel reinventing than making an entire new data structure, letting you reuse a lot of the existing list functions.

对于列表末尾的操作，Python 列表的复杂度为O(1)。如果您将以半顺序方式进行所有插入操作——与 C 类比，只在列表中间保留一个指针作为某种“游标”——您可以节省大量精力只需使用两个 Python 列表。一份列表显示光标之前的内容，一份列表显示光标之后的内容；移动光标涉及从一个列表中拉出下一项并将其附加到另一个列表中。与创建全新的数据结构相比，这使您可以在光标位置进行任意 O(1) 插入，而无需花费太多精力和重新发明轮子，让您可以重用许多现有的列表函数。

For the fully general case allowing multiple references into the list, though, you're probably stuck making a linked list of some sort.

但是，对于允许对列表进行多个引用的完全一般情况，您可能无法制作某种类型的链表。

Edit:You're not seriously thinking of actually doing a "binary search" on a linked list, are you? Binary search doesn't even make sense on an intrinsically sequential data structure...

编辑：您并没有认真考虑在链表上实际进行“二分搜索”，是吗？二进制搜索在本质上是顺序数据结构上甚至没有意义......

Anyway, if you're okay with linear-time searching and your insertions will always preserve the list order without re-sorting, then a simple linked list might be all you need. If you do as much searching as iterating you should consider something with fast indexing, and if resorting might be required something like a tree would be better.

无论如何，如果您对线性时间搜索没问题，并且您的插入将始终保留列表顺序而无需重新排序，那么您可能只需要一个简单的链表。如果您进行尽可能多的搜索和迭代，您应该考虑使用快速索引的方法，如果可能需要求助于树之类的东西会更好。

回答by Glenn Maynard

It's puzzling that everyone demands justification to need a linked list. Linked lists are one of the most elementary data structures for a reason: they have properties that the other major data structures lack, and if you need those properties, you need a linked list or one of its close relatives. If you don't understand why linked lists are an important data structure that can't always be replaced with a deque or a binary tree, you should never have passed your "intro to data structures" class.

令人费解的是，每个人都要求证明需要一个链表。链表是最基本的数据结构之一，这是有原因的：它们具有其他主要数据结构所缺乏的属性，如果您需要这些属性，则需要一个链表或其近亲之一。如果你不明白为什么链表是一种不能总是用双端队列或二叉树代替的重要数据结构，你就不应该通过你的“数据结构介绍”课程。

Here's a quick implementation, supporting the usual stuff: constant-time insertion at any point given a reference to the node, splitting the list into two lists, and inserting a list into the middle of another list (splice). Generic Python interfaces are supported: push, pop, pushleft, popleft, extend, ordinary iteration, iteration over a slice (getiter).

这是一个快速实现，支持通常的东西：在给定对节点的引用的任何点上的常量时间插入，将列表拆分为两个列表，并将列表插入另一个列表的中间（拼接）。支持通用 Python 接口：push、pop、pushleft、popleft、extend、普通迭代、切片迭代 (getiter)。

I just wrote this, so it's doctested but not production tested; there are probably still bugs.

我刚刚写了这个，所以它已经过文档测试但没有经过生产测试；可能仍然存在错误。

def _ref(obj):
    """
    weakref.ref has a bit of braindamage: you can't take a weakref to None.
    This is a major hassle and a needless limitation; work around it.
    """
    from weakref import ref
    if obj is None:
        class NullRef(object):
            def __call__(self): return None
        return NullRef()
    else:
        return ref(obj)

class _node(object):
    def __init__(self, obj):
        self.obj = obj
        self._next = None
        self._prev = _ref(None)
    def __repr__(self):
        return "node(%s)" % repr(self.obj)

    def __call__(self):
        return self.obj

    @property
    def next(self):
        return self._next

    @property
    def prev(self):
        return self._prev()

# Implementation note: all "_last" and "prev" links are weakrefs, to prevent circular references.
# This is important; if we don't do this, every list will be a big circular reference.  This would
# affect collection of the actual objects in the list, not just our node objects.
#
# This means that _node objects can't exist on their own; they must be part of a list, or nodes
# in the list will be collected.  We also have to pay attention to references when we move nodes
# from one list to another.
class llist(object):
    """
    Implements a doubly-linked list.
    """
    def __init__(self, init=None):
        self._first = None
        self._last = _ref(None)
        if init is not None:
            self.extend(init)

    def insert(self, item, node=None):
        """
        Insert item before node.  If node is None, insert at the end of the list.
        Return the node created for item.

        >>> l = llist()
        >>> a = l.insert(1)
        >>> b = l.insert(2)
        >>> d = l.insert(4)
        >>> l._check()
        [1, 2, 4]
        >>> c = l.insert(3, d)
        >>> l._check()
        [1, 2, 3, 4]
        """
        item = _node(item)

        if node is None:
            if self._last() is not None:
                self._last()._next = item
                item._prev = _ref(self._last())
            self._last = _ref(item)
            if self._first is None:
                self._first = item
        else:
            assert self._first is not None, "insertion node must be None when the list is empty"
            if node._prev() is not None:
                node._prev()._next = item
            item._prev = node._prev
            item._next = node
            node._prev = _ref(item)
            if node is self._first:
                self._first = item
        return item

    def remove(self, node):
        """
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l.remove(c) # Check removing from the middle
        3
        >>> l._check()
        [1, 2, 4, 5]
        >>> l.remove(a) # Check removing from the start
        1
        >>> l._check()
        [2, 4, 5]
        >>> l.remove(e) # Check removing from the end
        5
        >>> l._check()
        [2, 4]
        """
        if self._first is node:
            self._first = node._next
        if self._last() is node:
            self._last = node._prev
        if node._next is not None:
            node._next._prev = node._prev
        if node._prev() is not None:
            node._prev()._next = node._next
        node._next = None
        node._prev = _ref(None)
        return node.obj

    def __nonzero__(self):
        """
        A list is true if it has any elements.

        >>> l = llist()
        >>> bool(l)
        False
        >>> l = llist([1])
        >>> bool(l)
        True
        """
        return self._first is not None


    def __iter__(self):
        """
        >>> l = llist([1,2,3])
        >>> [i() for i in l]
        [1, 2, 3]
        """
        return self.getiter(self._first, self._last())

    def _check(self):
        if self._last() is None:
            assert self._last() is None
            return []
        node = self._first
        ret = []
        while node is not None:
            if node._next is None:
                assert node == self._last()
            if node._prev() is None:
                assert node == self._first
            if node._next is not None:
                assert node._next._prev() == node
            if node._prev() is not None:
                assert node._prev()._next == node
            ret.append(node.obj)
            node = node._next
        return ret

    def getiter(self, first, last):
        """
        Return an iterator over [first,last].

        >>> l = llist()
        >>> l.append(1)
        node(1)
        >>> start = l.append(2)
        >>> l.extend([3,4,5,6])
        >>> end = l.append(7)
        >>> l.extend([8,9])
        >>> [i() for i in l.getiter(start, end)]
        [2, 3, 4, 5, 6, 7]
        """
        class listiter(object):
            def __init__(self, first, last):
                self.node = first
                self.final_node = last

            def __iter__(self): return self
            def next(self):
                ret = self.node
                if ret is None:
                    raise StopIteration
                if ret is self.final_node:
                    self.node = None
                else:
                    self.node = self.node._next
                return ret
        return listiter(first, last)

    def append(self, item):
        """
        Add an item to the end of the list.

        >>> l = llist()
        >>> l.append(1)
        node(1)
        >>> l.append(2)
        node(2)
        >>> l._check()
        [1, 2]
        """
        return self.insert(item, None)

    def appendleft(self, item):
        """
        Add an item to the beginning of the list.

        >>> l = llist()
        >>> l.appendleft(1)
        node(1)
        >>> l.appendleft(2)
        node(2)
        >>> l._check()
        [2, 1]
        """
        return self.insert(item, self._first)

    def pop(self):
        """
        Remove an item from the end of the list and return it.

        >>> l = llist([1,2,3])
        >>> l.pop()
        3
        >>> l.pop()
        2
        >>> l.pop()
        1
        >>> l.pop()
        Traceback (most recent call last):
        ...
        IndexError: pop from empty llist
        """
        if self._last() is None:
            raise IndexError, "pop from empty llist"
        return self.remove(self._last())

    def popleft(self):
        """
        Remove an item from the beginning of the list and return it.

        >>> l = llist([1,2,3])
        >>> l.popleft()
        1
        >>> l.popleft()
        2
        >>> l.popleft()
        3
        >>> l.popleft()
        Traceback (most recent call last):
        ...
        IndexError: popleft from empty llist
        """
        if self._first is None:
            raise IndexError, "popleft from empty llist"
        return self.remove(self._first)

    def splice(self, source, node=None):
        """
        Splice the contents of source into this list before node; if node is None, insert at
        the end.  Empty source_list.  Return the first and last nodes that were moved.

        # Test inserting at the beginning.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, a)
        (node(4), node(6))
        >>> l._check()
        [4, 5, 6, 1, 2, 3]
        >>> l2._check()
        []

        # Test inserting in the middle.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, b)
        (node(4), node(6))
        >>> l._check()
        [1, 4, 5, 6, 2, 3]
        >>> l2._check()
        []

        # Test inserting at the end.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, None)
        (node(4), node(6))
        >>> l._check()
        [1, 2, 3, 4, 5, 6]
        >>> l2._check()
        []

        # Test inserting a list with a single item.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4])
        >>> l.splice(l2, b)
        (node(4), node(4))
        >>> l._check()
        [1, 4, 2, 3]
        >>> l2._check()
        []
        """
        if source._first is None:
            return
        first = source._first
        last = source._last()

        if node is None:
            if self._last() is not None:
                self._last()._next = source._first
            source._first._prev = self._last
            self._last = source._last
            if self._first is None:
                self._first = source._first
        else:
            source._first._prev = node._prev
            source._last()._next = node
            if node._prev() is not None:
                node._prev()._next = source._first
            node._prev = source._last
            if node is self._first:
                self._first = source._first
        source._first = None
        source._last = _ref(None)
        return first, last

    def split(self, start, end=None):
        """
        Remove all items between [node, end] and return them in a new list.  If end is None,
        remove until the end of the list.

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l._check()
        [1, 2, 3, 4, 5]
        >>> l2 = l.split(c, e)
        >>> l._check()
        [1, 2]
        >>> l2._check()
        [3, 4, 5]

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l2 = l.split(a, c)
        >>> l._check()
        [4, 5]
        >>> l2._check()
        [1, 2, 3]

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l2 = l.split(b, d)
        >>> l._check()
        [1, 5]
        >>> l2._check()
        [2, 3, 4]
        """
        if end is None:
            end = self._last()

        ret = llist()

        # First, move the region into the new list.  It's important to do this first, or
        # once we remove the nodes from the old list, they'll be held only by weakrefs and
        # nodes could end up being collected before we put it into the new one.
        ret._first = start
        ret._last = _ref(end)

        # Hook our own nodes back together.
        if start is self._first:
            self._first = end._next
        if end is self._last():
            self._last = start._prev

        if start._prev() is not None:
            start._prev()._next = end._next
        if end._next is not None:
            end._next._prev = start._prev
        start._prev = _ref(None)
        end._next = None

        return ret

    def extend(self, items):
        """
        >>> l = llist()
        >>> l.extend([1,2,3,4,5])
        >>> l._check()
        [1, 2, 3, 4, 5]
        """
        for item in items:
            self.append(item)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

回答by Alex Martelli

There's a single-linked list here(recipe 17.14 in the Python Cookbook 1st ed) but it's hardly "mature" or rich -- it's just doing a FIFO queue so it's pretty minimal.

有一个单链表这里（配方17.14在Python食谱第1版），但它几乎没有“成熟”或富-它只是做一个FIFO队列所以这是相当小。

This recipeis a very concise C implementation of (read-only) Lisp-like cons-boxes -- just car, cdr and cons; again, not a rich type, rather a minimal one (and to use it for mutable data, as opposed to pure functional approaches, you'd need to add setcar and setcdr at least). It may be a better starting point for you simply because cons-cells are so notoriously flexible and familiar.

这个秘籍是（只读）类似 Lisp 的 cons-boxes 的非常简洁的 C 实现——只是 car、cdr 和 cons；同样，不是丰富的类型，而是最小的类型（并且要将它用于可变数据，与纯函数方法相反，您至少需要添加 setcar 和 setcdr）。这对您来说可能是一个更好的起点，因为 cons-cell 非常灵活和熟悉。

Some of the operations you require will be likely best done by existing Python primitives. For example, for sorting, it's hard to see how rolling your own sort can beat the performance of Python's sorted(linkedlist)(as long of course as you make the linkedlisttype a Python iterable so it plays well with the rest of the language and library;-), considering the power of the timsortalgorithm implemented in the Python runtime.

您需要的一些操作可能最好由现有的 Python 原语完成。例如，对于排序，很难看出滚动你自己的排序如何能打败 Python 的性能sorted(linkedlist)（当然，只要你使linkedlist类型成为 Python 可迭代的，这样它就可以与语言和库的其余部分很好地配合；-)，考虑到timsort在 Python 运行时中实现的算法的强大功能。

More generally I suggest you carefully timeitthings every step along the way to consider how much the C-coded approach is really buying you (when compared to the trivial C-coded one exemplified by the recipe in the printed Cookbook whose URL I give at the start of this answer) -- that will crucially depend on the size and nature of your application's lists, so you're the one best placed to organize these benchmarks of course.

更一般地说，我建议您仔细timeit考虑沿途的每一步，以考虑 C 编码方法真正为您带来多少（与我在开始时给出的印刷食谱中的配方所举例说明的微不足道的 C 编码方法相比）这个答案的）——这将在很大程度上取决于您的应用程序列表的大小和性质，因此您当然是组织这些基准测试的最佳人选。

回答by Daniel Roseman

Python's dequeclass is 0(1) for insertion and deletion at the beginning and end of the list.

Python 的deque类是 0(1) 用于在列表的开头和结尾插入和删除。

回答by Dave Kirby

" I will iterate over the list forwards (one by one), using a visitor on each entry, starting from the beginning or a position found by a binary search. When an entry matching a predicate is found it is removed from the list, and then, another binary search is performed on a subset of the list beginning from the removed entry's previous position"

" 我将遍历列表（一个接一个），在每个条目上使用访问者，从头开始或从二进制搜索找到的位置开始。当找到与谓词匹配的条目时，它将从列表中删除，并且然后，从删除条目的前一个位置开始，对列表的子集执行另一个二分搜索”

It sounds like a linked list is absolutely the wrong data structure for this - doing a binary search will require random access to the list, which will mean repeatedly iterating through the elements. This is likely to be slower on a linked list than inserting and deleting items in a python list.

听起来链接列表绝对是错误的数据结构 - 进行二进制搜索将需要随机访问列表，这意味着重复遍历元素。这在链表上可能比在 python 列表中插入和删除项目慢。

It sounds like the data structure you want is a skip list. Google throws up several implementations, but I cannot comment on their completeness or quality.

听起来您想要的数据结构是一个跳过列表。谷歌抛出了几个实现，但我不能评论它们的完整性或质量。

edit:

编辑：

Another data structure that may be suitable is a threaded binary tree. this is like a regular binary tree but each leaf node points to next/previous subtree, so it can be iterated through as efficiently as a linked list. Implementing it in Python is left as an exercise for the reader (or Google).

另一种可能适用的数据结构是线程化二叉树。这就像一个普通的二叉树，但每个叶节点都指向下一个/上一个子树，所以它可以像链表一样高效地迭代。在 Python 中实现它作为练习留给读者（或谷歌）。

回答by Angel

For large data， keep a sorted list is a trick. Don't insert but append new items at the end and then sort it. Don't delet item but replace with a special value, sort them to the end and then pop out. For finding, a sorted list also has very quick performance with bisection method. As for small data, iterate old list， filter and build a new one, like list comprehensions method, is always the fast way.

对于大数据，保持排序列表是一个技巧。不要插入而是在末尾附加新项目，然后对其进行排序。不要删除项目而是用特殊值替换，将它们排序到最后然后弹出。对于查找，排序列表使用二分法也具有非常快的性能。对于小数据，迭代旧列表，过滤并构建一个新列表，就像列表理解方法一样，总是最快的方法。

For me, what is large data? it should be over 1000000 items...

对我来说，什么是大数据？它应该超过1000000个项目......

回答by dividebyzero

I recently had the need for a circular and doubly linked list. Since I am very familiar with the Linux kernel's linked list. I wrote a copycat linked list in Python. It provides O(1) random insertion and deletion. It is much faster than Python's list when you are doing random insertion and deletion on a big list. The code is here: https://github.com/ningke/Pylnklist. I also wrote a little bit of introduction here: http://710003.blogspot.com/2012/06/copycat-linked-list-in-python.html

我最近需要一个循环和双向链表。由于我对Linux内核的链表非常熟悉。我用 Python 写了一个模仿链表。它提供 O(1) 随机插入和删除。当您在大列表上进行随机插入和删除时，它比 Python 的列表快得多。代码在这里：https: //github.com/ningke/Pylnklist。我这里也写了一点介绍：http: //710003.blogspot.com/2012/06/copycat-linked-list-in-python.html

回答by fork0

How about using any of data structures which provide sorted data access? Binary (AVL trees, AVL, Red-black), for instance? These guarantee O(log(N)) insertion complexity. Not O(1), but better than what you have.

如何使用任何提供排序数据访问的数据结构？二进制（AVL 树、AVL、红黑），例如？这些保证 O(log(N)) 插入复杂度。不是 O(1)，但比你拥有的要好。

回答by fork0

Here's an idea, that would require a little coding, but may give you hugely better performance. It may or may not be suitable for your use case.

这是一个想法，它需要一些编码，但可能会给您带来更好的性能。它可能适合也可能不适合您的用例。

You can splice a new list into your list by replacing a single element. To insert the list [6, 7, 8] into [1, 2, 3, 4, 5] at index 2, you would end up with

您可以通过替换单个元素将新列表拼接到您的列表中。要将列表 [6, 7, 8] 插入索引 2 处的 [1, 2, 3, 4, 5] 中，您将得到

[1, 2, [3, 6, 7, 8], 4, 5]

[1, 2, [3, 6, 7, 8], 4, 5]

By not changing the length of the large (here 5 element) list, you'll not have the speed problems you're currently having.

通过不更改大（此处为 5 个元素）列表的长度，您将不会遇到当前遇到的速度问题。

You can 'delete' an element from the list in the same way, by replacing it with an empty list.

你可以用同样的方式从列表中“删除”一个元素，用一个空列表替换它。

[1, 2, [], 4, 5]

[1, 2, [], 4, 5]

To iterate over this mixed list is straightforward.

迭代这个混合列表很简单。

def IterateNestedList(xs):
    for x in xs:
        if isinstance(x, list):
            for y in IterateNestedList(x): yield y
        else: yield x