Lists and Tuples in Python

Posted on

Lists are the workhorse of Python DSA. Almost every array-based algorithm, from sorting to sliding windows, starts with a list. Tuples are their immutable cousins, useful for fixed records and dictionary keys.

Lists: ordered and mutable#

A list holds items in order and lets you change them:

1nums = [10, 20, 30, 40]
2print(nums[0])    # 10  (first item, zero-indexed)
3print(nums[-1])   # 40  (last item)
4nums[1] = 99      # lists are mutable
5print(nums)       # [10, 99, 30, 40]

Negative indexing counts from the end, which is handy for grabbing the last element without knowing the length.

Slicing#

Slicing extracts a sub-list with list[start:stop:step]. The stop index is excluded:

1data = [0, 1, 2, 3, 4, 5]
2print(data[1:4])    # [1, 2, 3]
3print(data[:3])     # [0, 1, 2]  (from the start)
4print(data[3:])     # [3, 4, 5]  (to the end)
5print(data[::-1])   # [5, 4, 3, 2, 1, 0]  (reversed)

Slicing creates a new list, so it is a quick way to copy or reverse.

Common operations you will use constantly#

 1stack = []
 2stack.append(1)     # add to end, O(1)
 3stack.append(2)
 4top = stack.pop()   # remove from end, O(1) -> 2
 5
 6nums = [3, 1, 2]
 7nums.sort()         # sort in place -> [1, 2, 3]
 8ordered = sorted([3, 1, 2])  # returns a new sorted list
 9
10print(len(nums))    # 3
11print(2 in nums)    # True  (membership check, O(n) for lists)

Using append and pop on the end of a list gives you a stack for free. Both are O(1). Check the Big-O cheat sheet for the cost of other operations. Note that in scans the whole list (O(n)); for fast membership use a set (covered in the dictionaries and sets page).

Tuples: ordered and immutable#

A tuple looks like a list with parentheses, but you cannot change it after creation:

1point = (3, 4)
2x, y = point        # unpacking
3print(x, y)         # 3 4
4
5# point[0] = 5      # this would raise a TypeError

Because tuples are immutable, they can be used as dictionary keys or set members, which lists cannot:

1seen = set()
2seen.add((0, 1))    # store a coordinate
3print((0, 1) in seen)  # True

Reach for a tuple when you have a fixed group of values (a coordinate, a return of multiple values) and a list when the collection grows, shrinks, or changes.

Practice#

Try reversing a list two ways (data[::-1] and data.reverse()) and note that one returns a new list while the other changes it in place. Then continue to dictionaries and sets.