Bytebook Compiler

Data Structures in Python

Lists

Python's workhorse collection: creating, indexing and slicing lists, adding and removing items, sorting, copying, 2D lists and the list methods you will use daily.

4 min read6 runnable examples4-question quiz

A list is an ordered, mutable collection that can hold items of any type. It is a dynamic array underneath — like C++'s vector.

Python
marks = [78, 92, 65, 88]
mixed = [1, "two", 3.0, True, [5, 6]]
empty = []
print(marks[0], marks[-1], marks[1:3], len(marks))
marks[2] = 70                   # lists are mutable
print(marks)
print(mixed[4][1])              # a list inside a list
Output
78 88 [92, 65] 4
[78, 92, 70, 88]
6
Try it Yourself

Adding and removing

Method Effect
append(x) add x at the end
insert(i, x) insert x before index i
extend(iterable) add every item of another collection
remove(x) remove the first occurrence of x (error if absent)
pop() / pop(i) remove and return the last item / item at i
clear() remove everything
del lst[i], del lst[a:b] delete by index or slice
Python
cart = ["pen", "notebook"]
cart.append("eraser")
cart.insert(1, "pencil")
cart.extend(["ruler", "glue"])
print(cart)
cart.remove("glue")
last = cart.pop()
print("popped", last, "->", cart)
del cart[0]
print(cart, "pencil" in cart, cart.index("eraser"))
Output
['pen', 'pencil', 'notebook', 'eraser', 'ruler', 'glue']
popped ruler -> ['pen', 'pencil', 'notebook', 'eraser']
['pencil', 'notebook', 'eraser'] True 2
Try it Yourself

Sorting and searching

Python
nums = [42, 7, 19, 7, 88, 3]
print(sorted(nums))                  # new sorted list; nums unchanged
nums.sort(reverse=True)              # sorts in place
print(nums)
print(min(nums), max(nums), sum(nums), nums.count(7))

students = [("Asha", 88), ("Ravi", 95), ("Meera", 88)]
students.sort(key=lambda s: (-s[1], s[0]))     # marks descending, then name
print(students)

words = ["banana", "apple", "Cherry", "fig"]
print(sorted(words))                  # uppercase sorts before lowercase
print(sorted(words, key=str.lower))   # case-insensitive
print(sorted(words, key=len))         # by length (ties keep their order)
Output
[3, 7, 7, 19, 42, 88]
[88, 42, 19, 7, 7, 3]
3 88 166 2
[('Ravi', 95), ('Asha', 88), ('Meera', 88)]
['Cherry', 'apple', 'banana', 'fig']
['apple', 'banana', 'Cherry', 'fig']
['fig', 'apple', 'banana', 'Cherry']
Try it Yourself

Lists are references: copying correctly

Python
a = [1, 2, [3, 4]]
b = a                 # same list
c = a[:]              # shallow copy (also list(a) or a.copy())
import copy
d = copy.deepcopy(a)  # copies nested lists too

a[0] = 100
a[2].append(5)
print("a", a)
print("b", b)         # sees everything
print("c", c)         # own outer list, but shares the inner list
print("d", d)         # fully independent
Output
a [100, 2, [3, 4, 5]]
b [100, 2, [3, 4, 5]]
c [1, 2, [3, 4, 5]]
d [1, 2, [3, 4]]
Try it Yourself

2D lists

Python
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]      # correct way
grid[1][2] = 9
for row in grid:
    print(row)

wrong = [[0] * cols] * rows                   # three references to ONE row!
wrong[1][2] = 9
print(wrong)

matrix = [[1, 2, 3], [4, 5, 6]]
transpose = [list(col) for col in zip(*matrix)]
print(transpose)
Output
[0, 0, 0, 0]
[0, 0, 9, 0]
[0, 0, 0, 0]
[[0, 0, 9, 0], [0, 0, 9, 0], [0, 0, 9, 0]]
[[1, 4], [2, 5], [3, 6]]
Try it Yourself

Using a list as a stack or queue

Python
stack = []
stack.append(1); stack.append(2); stack.append(3)
print(stack.pop(), stack.pop())           # LIFO: 3 2

from collections import deque
queue = deque(["a", "b"])
queue.append("c")
print(queue.popleft(), queue.popleft())   # FIFO: a b — O(1) at both ends
Output
3 2
a b
Try it Yourself

list.pop(0) also works as a queue, but it is O(n) because every element shifts. Use collections.deque for queues.

List operation costs

Operation Cost
lst[i], lst[i] = x, len(lst) O(1)
append, pop() O(1) amortised
insert(0, x), pop(0), remove(x) O(n)
x in lst, index, count O(n)
sort() (Timsort) O(n log n)

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What is [10, 20, 30, 40][1:3]?

  2. 2

    What is the difference between lst.sort() and sorted(lst)?

  3. 3

    After a = [1, 2]; b = a; b += [3], what is a?

  4. 4

    Which is the best way to implement a queue with fast removal from the front?

Esc
↑↓ move↵ open