 # Python Basic Data Structures

## Array

Python's `list` is internally implemented as an array. Access an element by an index is `O(1)`.

### Indexing

Negative indices are also allowed. A handy way to access the last element is:

``````1a = [1, 2, 3]
2print(a[-1])  # print out 3``````

Subarray slicing indices are left-inclusive and right-exclusive. For example

``````1a = [0, 10, 20, 30, 40, 50]
2subarray = a[2:5]  # element from index 2 to index 4 (cuz right exclusive, 5-1=4)
3# subarray = [20, 30, 40]``````

This is very important. Mishandling the right-exclusivity is a common source of error in coding interview problems such as two-pointer problems.

There's also a shorthand for slicing from element 0. For example:

``````1a = [0, 10, 20, 30, 40, 50]
2subarray = a[:2]
3# subarray = [0, 10]``````

and slicing until

``````1a = [0, 10, 20, 30, 40, 50]
2subarray = a[2:]
3# subarray = [20, 30, 40, 50]``````

A note on right-exclusivity. Array and list indices are left inclusive and right exclusive in most languages including Python and Java. The reason for this design is up for speculation. According to a stackover flow post, Python inventor Guido Van Rossum was quoted as saying "I was swayed by the elegance of half-open intervals. Especially the invariant that when two slices are adjacent, the first slice's end index is the second slice's start index is just too beautiful to ignore. For example, suppose you split a string into three parts at indices i and j -- the parts would be `a[:i]`, `a[i:j]`, and `a[j:]`." For our practical purposes in solving coding problems, we often have to deal with edge cases such as an empty list. And this notation becomes convenient because to represent an empty array we can write `a[i:i]` instead of the more awkward `a[i:i-1]`.

In general, to iterate through a list, `for` loop is easier to reason than `while` since there's no condition to manage that could skip elements. You can also use `enumerate` to get both index and element at the same time.

``````1nums = [0, 10, 20, 30, 40, 50]
2for i, num in enumerate(nums):
3    print(i, num)
4
5# 0 0
6# 1 10
7# 2 20
8# 3 30
9# 4 40
10# 5 50``````

Python doesn't have a built-in linked list. Normally at an interview, you'll be given a definition like this

``````1class LinkedListNode:
2    def __init__(self, val, next=None):
3        self.val = val
4        self.next = next``````
• append to end is `O(1)`.
• finding an element is `O(N)`.

Besides problems that specifically ask for linked lists, you don't normally define and use linked list. If you need a list with `O(1)` append you can use the built-in `list`, and if you want `O(1)` for both prepend and append you can use the built-in `deque`.

## Stack

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

• push: `append`, `O(1)`
• pop: `pop`,`O(1)`
• size: `len(l)`, `O(1)`
• top: `l[-1]`, `O(1)`

Stack is arguably the most magical data structure in computer science. In fact, with two stacks and a finite-state machine you can build a Turing Machine that can solve any problem a computer can solve.

Recursion and function calls are implemented with stack behind the scene. We'll discuss this in the recursion review module.

## Queue

Python's `collections.deque` is a double-ended queue, which means you can push and pop an element from either end in constant time. In the coding interviews, this is what we normally use when we need a queue. For a deque `q = deque()`

• enqueue: `q.append`, `O(1)`
• dequeue: `q.popleft()`, `O(1)`. Note that it's `pop*left*`. `pop` is also supported but it's for getting element at the end of the double-ended queue.
• size: `len(q)`, `O(1)`

In coding interviews, we see queues most often in breadth-first search. We'll also cover monotonic deque where elements are sorted inside the deque that is useful in solving some advanced coding problems.

## Hash Table

Python's `dict` is an implementation of the hash table. For a dictionary `d = {}`,

• get using a key: `d[key]`, `O(1)`
• set a key, value: `d[key] = value`, `O(1)`
• remove a key: `del d[key]`, `O(1)`

It's worth mentioning that these are average case time complexity. A hash table's worst time complexity is actually `O(N)` due to hash collision and other things. For the vast majority of the cases and certainly most coding interviews, the assumption of constant time lookup/insert/delete is valid.

Use a hash table if you want to create a mapping from A to B. Many starter interview problems can be solved with a hash table.

Python `dict` has a convenient subclass `Counter` for counting hashable objects. When you pass an iterable object, such as a list or a string, to `Counter()`, it will return a new `dict` with elements as keys and their counts as values.