Python Basic Data Structures - Getting Started / Basic Data Structures

For the below, wouldn’t accessing the top of the stack be l[-1]:

Python’s list also doubles as a stack. For a list l = []

top: l[0], O(1)

top: l[0] will return the first item in a stack.

There’s an error in top of stack in a python list. It should be l[-1] and NOT l[0]. This is the third comment pointing the same issue, hope someone will fix.

For Stack data structure, top: l[0], O(1) is incorrect. top: l[-1], O(1) . Because -1 is the last index of the list and it contains the last element of the list which is the topmost of the stack.

hi can you make an article on python’s Counter class? examples, etc.


You write:
“removing a from set: s.remove(a), O(1). Does nothing if a is not in a set.”
This is incorrect. s.remove(a) where ‘a’ is not in the set raises a KeyError exception.
Use s.discard(a) if you want to safely discard elements that might not be in the set.

I think tuples should also be mentioned here as it is very useful in many situations.

How is appending to end of LinkedList O(1)? Wouldn’t it be O(n) given you would have to traverse through the entire list if the node (which would probably be the ‘head’ in most cases) only has next and you’d have to traverse until null?

You are right that it would be O(n) if we are only given a head node in a singly linked list, however some linked lists have head and tail properties so if it has the tail property then we can access the tail in O(1) time and then append right there.

There’s a typo here: " to represent an empty array we can write a[i:i] instead of the more awkward ar[i:i-1]."

‘ar’ instead of ‘a’ in the last expression

Hi, I have a question on the time complexity of len(l) for stacks. How is it O(1)? I thought it would be O(n) to count how many elements are in the stack.

You can keep the length as a counter and increment (push) / decrement (pop) it based on the operations you perform on the stack. In this way, you could return the counter itself, instead of calculating it each time by counting the elements of the stack.