Python: Lists
Mutable and ordered data structure. Ordered != sorted.
| Description | Command |
|---|---|
| Create an empty list. | list() or [] |
| Create and populate a list from a range. | list(range(ARGS)) |
| Create a list of single characters from a string. | list(STRING) |
| Retrieve the list item at INDEX. | list[INDEX] |
| Retrieve the final list item. | list[-1] |
| Retrieve the second to last item in a list. | list[-2] |
Slicing
| Description | Command |
|---|---|
| Return items from index START to (STOP-1). | list[START:STOP] |
| Return all items after and including index START. | list[START:] |
| Return all items before and including index (STOP-1). | list[:STOP] |
| Shallow copy (non-recursive) a list. | list[:] |
| Last n items in a list. | list[-n:] |
| Everything except the last n items in a list. | list[:-n] |
| When STEP is given, every STEP^TH^ value, starting at START, is returned. | list[START:STOP:STEP] |
| Return the value at every second index, starting at START. | list[START:STOP:2] |
| Reverse the list. | list[::-1] |
Methods
| Description | Command |
|---|---|
| Append an item to a list. | list.append(ITEM) |
| Append LIST to list. | list.extend(LIST) |
| Insert an item x at index i. | list.insert(i,x) |
Remove the first item of value y. Otherwise, raise ValueError. |
list.remove(y) |
| Pop the last item or item at INDEX i (if i is given). | list.pop([i]) |
| Remove all items from the list. | list.clear() |
Return the index of the first item with value x. Otherwise raise ValueError. Start and end specify substring indexes. |
list.index(x)[,start[,end]] |
| Return the number of times x appears in the list. | list.count(x) |
Sort the list. KEYF a custom function to be used for sorting. reverse=True reverse the sorting. Reverse the elements of the list. |
list.sort([key=KEYF],[reverse=False]) |
| Create a shallow copy (non-recursive) of a list. | list.copy() |
| Delete one or more values at specific indices. | del list[INDEX1[, INDEX2[, INDEXN]]] |
| Delete a range of values using a slice to define the indices. | del list[SLICE] |
Delete the list. listVariable references will raise an error afterwards. |
del listVariable |
Joining Lists
| Method | Python version | In-Place? | Notes |
|---|---|---|---|
a + b |
Any | No | Quadratic space complexity |
list(chain(a, b)) |
>=2.3 | No | import itertools. Linear space complexity. |
[*a, *b] |
>=3.5 | No | |
a += b |
Yes | Equivalent to extend() | |
a.extend(b) |
Yes | Equivalent to += |
-a + b is generally best for small lists and chain() for large lists.
List comprehensions
List comprehensions provide a concise way to create lists.
[ACTION for VAR in ITER [COND]]
Loop over an iterable (ITER) and perform an ACTION. CONDITIONALS (COND), such as if statements,
can optionally be specified.
[x**2 for x in range(10)]
Create a list of the squares of the numbers from 0 to 9.
[x**2 for x in range(10) if x % 2 == 0]
Create a list of the squares of the even numbers from 0 to 9.
Nested list comprehensions
[[ACTION for VAR2 in ITER2 [COND2]] for VAR IN ITER [COND]]
Equivalent to a nested for loop. The rightmost for loop iterates first.
matrix = [[1, 2], [3,4], [5,6], [7,8]]
transpose = [[row[i] for row in matrix] for i in range(2)]
print (transpose)
[[1, 3, 5, 7], [2, 4, 6, 8]]
Extract the first and second elements of each sub-list in matrix into two new lists.
Big-O
| Operation | Big O Efficiency |
|---|---|
| index [] | O(1) |
| index assignment | O(1) |
| append | O(1) |
| pop() | O(1) |
| pop(i) | O(n) |
| insert(i, item) | O(n) |
| del operator | O(n) |
| iteration | O(n) |
| contains (in) | O(n) |
| get slice [x:y] | O(k) |
| del slice | O(n) |
| reverse | O(n) |
| concatenate | O(k) |
| sort | O(nlogn) |
| multiply | O(nk) |
Creating other ADTs with lists
- Lists make good stacks.
- Lists make poor queues because inserts or pops at beginning of the list are slow.
Use
collections.dequefor queues.