Lists

A list is an ordered, mutable sequence of references. Order is preserved, duplicates are allowed, and elements can be of mixed types (although mixed-type lists are usually a code smell).

Indexing and length both work in O(1). Appending to the end is also O(1) amortized, which is why append is the workhorse of list construction. Inserting in the middle requires shifting everything to the right, which is O(n).

Lists in Python feel like dynamic arrays in any language. The behavior, the costs, and the syntax are all close enough to what you would expect that the only thing to internalize is that the bracket form is the standard syntax.

Lists support the same slicing syntax as strings. lst[1:4] returns a new list with elements at indices 1, 2, and 3. The slice is independent of the original.

For mutation, the basic operations are append(item) to add to the end, insert(i, item) to add at a position, pop(i) to remove and return, and remove(value) to find and delete. Each modifies the list in place and returns either nothing or the popped element.

Slice assignment is the most flexible mutation. lst[1:3] = [x] replaces two elements with one. lst[:] = [] empties the list. The slice on the left tells Python where to splice in whatever is on the right.

lst = [1, 2, 3, 4]
lst.append(5)        # [1, 2, 3, 4, 5]
lst.pop(0)           # returns 1; lst is now [2, 3, 4, 5]
lst[1:3] = [9]       # [2, 9, 5]

There are two ways to sort. lst.sort() sorts in place and returns None. sorted(lst) returns a new sorted list and leaves the original alone. The choice depends on whether you want to keep the original around.

Both take a key= argument that lets you sort by a derived value. sorted(words, key=len) sorts by string length. sorted(items, key=lambda x: x.score) sorts by an attribute. The function gets called once per element and the return value is what gets compared.

Reverse order is reverse=True on either function, or you can call .reverse() for an in-place reversal that does not sort. Reversing without sorting is rare; in real code, you almost always combine the two.

nums = [3, 1, 2]
sorted(nums)                # [1, 2, 3], nums unchanged
nums.sort(reverse=True)     # nums = [3, 2, 1], returns None

words = ["bee", "a", "cat"]
sorted(words, key=len)      # ['a', 'bee', 'cat']