时间戳

首页 > 解决方案 > 递归列表 Python

python - 递归列表 Python

问题描述

所以我正在学习 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._firstinto 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.
    """

标签： python

解决方案

您创建一个新的RecursiveList（顺便说一句：这通常称为Linked List），将当前值复制到其中，使其rest指向您的 current 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 的基于数组的普通列表。

推荐阅读