RecursiveList Python

Question

So i'm learning about RecursiveLists and our prof has given us a init for the recursivelist class

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:])

now I want to mutate the list by inserting an item to the front of the list but I can't wrap my head around how to do so. I understand that self._rest stores the rest of the list recursively and also that I should move the value of self._first into self._rest, but how do I move an int and turn it so that the recursive function has the rest of them?

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

You make a new RecursiveList (btw: This is usually called a Linked List) that you copy your current value to, make its rest point to your current rest, overwrite your own element with the element to be inserted, and set your rest to the new list.

Something like:

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" -┘

Note that this process is a what is called constant-time operation, because it doesn't matter how large the list is: this process always takes roughly the same amount of time. This (constant-time insertion at the beginning of the list) is somewhat unique to Linked Lists, and does not apply to Python's normal lists, which are based on arrays.