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

You can use your method recursively on self._rest, using previous first element value as item. — Qiu
– Qiu, Commented Nov 5, 2018 at 18:11
Hopefully, your prof will make it clear that although the class is named RecursiveList, it is actually a Linked List (as @L3viathan noted). Lists can be Linked Lists and methods can be recursive, as any computer science document from the past several decades will support. — John Anderson
– John Anderson, Commented Nov 5, 2018 at 18:31

L3viathan · Accepted Answer · 2018-11-05 18:03:12Z

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.

Collectives™ on Stack Overflow

RecursiveList Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related