List class with O(1) operations

Question

I'm in the process of trying to create this kind of list class where each operation would be of O(1). I found that reverse() will be of O(1), but it seems that insert is not? Is there a way to accomplish this with pythons standard methods?

class TimeList:
    def __init__(self):
        self.arr = []

    def push_last(self, x):
        self.arr.insert(len(self.arr), x)

    def push_first(self,x):
        self.arr.insert(0, x)

    def rev(self):
        self.arr.reverse()

    def pop_last(self):
        """
        Remove and return last element
        """
        rem = self.arr[-1]
        self.arr = self.arr[:-1]
        return rem

    def pop_first(self):
        """
        Remove and return first element
        """
        rem = self.arr[0]
        self.arr = self.arr[1:]
        return rem

`.arr.reverse()` is **not** O(1). Note, your `pop` method is not O(1). Why do you think this is possible, to create a list with all O(1) operations? And if it were, why wouldnt the built-in list do this already? — juanpa.arrivillaga, Oct 03 '20 at 16:48
Here you can find complexity for different types of data structures: https://www.bigocheatsheet.com/img/big-o-cheat-sheet-poster.png — xszym, Oct 03 '20 at 16:52
It isn't possible to reverse a list in constant time. Inserting to the front of a standard list is also incredibly expensive, as are operations like `self.arr = self.arr[:-1]` that create an entire copy of `arr`. — Carcigenicate, Oct 03 '20 at 16:52
Sorry, I stand corrected regarded reversing a list. I guess technically you can simply alter how a list is iterated/added to give the appearance of a reversal, even without any structural changes happening. — Carcigenicate, Oct 03 '20 at 17:49
quoting @juanpa.arrivillaga, If there was a way why wouldn't the original list implement it — , Oct 03 '20 at 18:18

score 1 · Answer 1 · answered Oct 03 '20 at 17:28

It's a bit complicate but you may create somewhat c++ vector like class to have amortized O(1) for push/pop front & last.

Below is skeleton code (I don't guarantee it will work properly. Such as [] operator, len(), list size getting less than 0 etc.) to show how it works.

Basically, you create list size of INIT_SIZE at first, and starting from the middle of the list, you push to the front_idx or back_idx. If the idx reaches 0 or len(self.arr) double the size of self.arr. This is proven to be amortized O(1).

Reversing works with self.is_reversed flag. So it decides which idx class needs to use for front/back push/pop operation. Tricky part is how you will gonna handle [] operator. I'll leave that to you for the detail implementation. (Use front_idx & back_idx wisely based on the is_reversed flag.)

class TimeList:
    INIT_SIZE = 100

    def __init__(self):
        self.arr = [None] * TimeList.INIT_SIZE
        self.is_reversed = False
        self.front_idx = TimeList.INIT_SIZE // 2
        self.back_idx = TimeList.INIT_SIZE // 2

    # Implement below two methods in order to make [] operator work properly.
    def __getitem__(self, key):
        return

    def __setitem__(self, key, value):
        return

    def __expand_arr(self):
        new_arr = [None] * len(self.arr) * 2
        for i in range(self.front_idx, self.back_idx):
            new_arr[i + (len(new_arr) - len(self.arr)) // 2] = self.arr[i]
        self.front_idx = self.front_idx + (len(new_arr) - len(self.arr)) / 2
        self.back_idx = self.back_idx + (len(new_arr) - len(self.arr)) / 2

    def __insert_front(self, x):
        if self.front_idx == 0:
            self.__expand_arr()
        self.front_idx -= 1
        self.arr[self.front_idx] = x

    def __insert_back(self, x):
        if self.back_idx == len(self.arr):
            self.__expand_arr()
        self.arr[self.back_idx] = x
        self.back_idx += 1

    def push_last(self, x):
        if self.is_reversed:
            self.__insert_front(x)
        else:
            self.__insert_back(x)

    def push_first(self, x):
        if self.is_reversed:
            self.__insert_back(x)
        else:
            self.__insert_front(x)

    def rev(self):
        self.is_reversed = not self.is_reversed

    def __remove_front(self):
        self.front_idx += 1

    def __remove_back(self):
        self.back_idx -= 1

    def pop_last(self):
        """
        Remove and return last element
        """
        if self.is_reversed:
            rem = self.arr[self.front_idx]
            self.__remove_front()
        else:
            rem = self.arr[self.back_idx - 1]
            self.__remove_back()
        return rem

    def pop_first(self):
        """
        Remove and return first element
        """
        if self.is_reversed:
            rem = self.arr[self.back_idx - 1]
            self.__remove_back()
        else:
            rem = self.arr[self.front_idx]
            self.__remove_front()
        return rem

List class with O(1) operations

1 Answers1