python - Python 递归列表

Question

所以我正在学习 RecursiveLists，我们的教授为我们提供了 recursivelist 类的 init

class RecursiveList:
    # === Private Attributes ===
    # _first:
    #     The first item in the list.
    # _rest:
    #     A list containing the items that come after
    #     the first one.
    _first: Optional[Any]
    _rest: Optional[RecursiveList]

    # === Representation Invariants ===
    # _first is None if and only if _rest is None.
    #     This represents an empty list.

    def __init__(self, items: list) -> None:
        """Initialize a new list containing the given items.

        The first node in the list contains the first item in <items>.
        """
        if items == []:
            self._first = None
            self._rest = None
        else:
            self._first = items[0]
            self._rest = RecursiveList(items[1:])

现在我想通过在列表前面插入一个项目来改变列表，但我不知道如何做到这一点。我知道 self._rest 以递归方式存储列表的其余部分，而且我应该将 self._first 的值移动到 self._rest ，但是如何移动 int 并将其转换以便递归函数拥有其余的内容？

def insert_first(self, item: object) -> None:
    """Insert item at the front of this list.

    This should work even if this list is empty.
    """

Answer 1

您创建一个新的 RecursiveList (顺便说一句:这通常称为 Linked List )，将当前值复制到其中，使其 rest 指向您当前的 rest，用要插入的元素覆盖您自己的元素，并将您的 rest 设置为新列表。

类似于:

def insert_first(self, item: object) -> None:
    """Insert item at the front of this list.

    This should work even if this list is empty.
    """
    if self._first is None:
        # handle case where list is "empty"
        self._first = item
    else:
        new = RecursiveList()
        new._first = self._first
        new._rest = self._rest
        self._first = item
        self._rest = new

<小时/>

Before:

1:"e" -→ 2:"l" -→ 3:"l" -→ 4:"o"

After:

1:"h"    2:"l" -→ 3:"l" -→ 4:"o"
   |        ↑
   └→5:"e" -┘

请注意，此过程是所谓的恒定时间操作，因为列表有多大并不重要:此过程始终花费大致相同的时间。这(在列表开头恒定时间插入)对于链接列表来说有些独特，并且不适用于基于数组的 Python 普通列表。