Efficient Stack implementation in Python

Question

1st Implementation: The following stack implementation assumes that the end of the list will hold the top element of the stack. As the stack grows, new items will be added on the end of the list.

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

2nd Implementation : The second implementation assumes that the beginning of the list holds the top element of the stack and new items are added at the index 0.

 class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.insert(0,item)

     def pop(self):
         return self.items.pop(0)

     def peek(self):
         return self.items[0]

     def size(self):
         return len(self.items)

Being a beginner to Data Structures, I would like to know:
1. Which implementation is more efficient with respect to time or space, and why ?
2. Is the time complexity of the insert(0) in the 2nd implementation O(n). If yes, how ?

Answer 1

Lists are optimized for appending and popping from the end. Inserting or removing an item from the beginning of a list is much more expensive, because all the items need to be moved.

Python does have a data structure, collections.deque, which is optimized for appending at both ends.

Answer 2

In Python, lists are implemented with resizeable arrays of references to other objects.

See How are lists implemented?

Because of this, pushing/popping elements at the end of the list will be more efficient than pushing/popping at the start of the list.

Adding/removing elements to the start of an array is very expensive because you will have to shift all the other elements over one space. On the other hand, it is relatively cheap to add/remove elements to the end of an array assuming there is sufficient empty space at the end of the array.

When the array is full, Python will dynamically allocate more memory to the end of that array, which is expensive, but the amortized performance is still excellent.