Skip to content
inwo Python Learning

Lists

A list is an ordered, mutable sequence. It is the structure you reach for whenever you need a collection you will keep changing after you create it.

fruits = ["apple", "banana", "cherry"]
mixed  = [1, "two", 3.0, True]    # any types, freely mixed
nested = [[1, 2], [3, 4]]         # a list can hold other lists

How a list stores its data

Section titled “How a list stores its data”

A Python list is backed by a dynamic array: one block of memory holding a row of equal-sized slots, in order. The slots sit next to each other, so Python can jump straight to slot i by computing its address, without walking the slots before it. That is why reading lst[i] is O(1), constant time, however long the list gets.

What a slot holds is not the object itself. The backing array stores pointers, one per slot, 8 bytes each on a 64-bit machine. Each pointer holds the address of the actual Python object, which lives elsewhere in memory and can be any size. Only the pointers are contiguous; the objects they point to are scattered across the heap. That is what keeps all slots the same width: the strings may be long or short, but every slot is always 8 bytes.

The contiguous slots are also why changing the shape of the list costs more than reading it. Inserting or deleting anywhere except the end forces every later pointer to shift over by one slot, which is O(n) work.

  fruits = ["apple", "banana", "cherry"]


  backing array (3 slots × 8 bytes = 24 bytes):


    addr 1000          addr 1008           addr 1016
  ┌──────────┐        ┌──────────┐        ┌──────────┐
  │  0x2a10  │        │  0x3f80  │        │  0x4c20  │
  └──────────┘        └──────────┘        └──────────┘
   slot 0 (8 B)        slot 1 (8 B)        slot 2 (8 B)
       │                    │                   │
       ▼                    ▼                   ▼
  ┌─────────┐         ┌──────────┐        ┌──────────┐
  │ "apple" │         │ "banana" │        │ "cherry" │
  │  54 B   │         │   55 B   │        │   55 B   │
  └─────────┘         └──────────┘        └──────────┘
  Python str object   Python str object   Python str object
  (heap, any size)    (heap, any size)    (heap, any size)

The slot width is fixed at 8 bytes regardless of what the strings contain. lst[i] jumps straight to 1000 + i × 8, reads the pointer, and does no scanning. The actual string object sits wherever Python put it on the heap, and its size does not affect how long the lookup takes.

The list object itself also carries a small header alongside the pointer array: the current length, the allocated capacity, and a reference count. On CPython, sys.getsizeof([]) returns 56 bytes for that header alone on a 64-bit machine. Each additional element adds 8 bytes for its slot in the pointer array.

  sys.getsizeof([])           →  56 bytes   (header only, no elements)
  sys.getsizeof(["apple"])    →  64 bytes   (56 + 1 × 8)
  sys.getsizeof(fruits)       →  80 bytes   (56 + 3 × 8)


  Note: getsizeof counts only the list's own memory, the pointer array and header.
  It does not count the memory used by the string objects the pointers point to.

Append

Section titled “Append”

Most appends land in a spare slot the list pre-allocated when it last grew:

  Before:    [ "apple" | "banana" | "cherry" |  ___  ]   ← spare slot


  fruits.append("date"):


  After:     [ "apple" | "banana" | "cherry" | "date" ]   O(1)

When there are no spare slots, Python allocates a larger block, copies the existing elements across, then drops in the new one. That copy is O(n), but with a growth factor of roughly 1.125× it happens rarely. Each element gets copied about once on average over its lifetime, so the amortised cost per append stays O(1).

  Before (full):   [ "apple" | "banana" | "cherry" | "date" ]


  fruits.append("elderberry"):


  1. allocate:     [ ___ | ___ | ___ | ___ | ___ | ___ ]   (larger block)
  2. copy:         [ "apple" | "banana" | "cherry" | "date" | ___ | ___ ]
  3. add:          [ "apple" | "banana" | "cherry" | "date" | "elderberry" | ___ ]


  The copy is O(n), but it happens rarely enough that each append averages out to O(1).

Insert in the middle

Section titled “Insert in the middle”

insert(1, "avocado") must open a gap at index 1. Every element from that position onward shifts one slot to the right before the new value goes in:

  Before:          [ "apple" | "banana" | "cherry" ]


  fruits.insert(1, "avocado"):


  1. shift right:  [ "apple" |  _______  | "banana" | "cherry" ]
                                  ↑ gap opened at index 1


  2. place value:  [ "apple" | "avocado" | "banana" | "cherry" ]


  Cost: O(n).  Worst case is insert(0, x): every element shifts.

Delete at the end

Section titled “Delete at the end”

pop() with no argument drops the last slot. Nothing else moves:

  Before:   [ "apple" | "banana" | "cherry" ]


  fruits.pop():


  After:    [ "apple" | "banana" ]   O(1)

Delete in the middle

Section titled “Delete in the middle”

Removing from anywhere except the end leaves a hole. Python closes it by shifting every later element one slot to the left:

  Before:         [ "apple" | "avocado" | "banana" | "cherry" ]


  fruits.pop(1)   or   fruits.remove("avocado"):


  1. remove:      [ "apple" |     ✗      | "banana" | "cherry" ]


  2. shift left:  [ "apple" | "banana" | "cherry" ]


  Cost: O(n).  Worst case is pop(0): every element shifts.

Core operations

Section titled “Core operations”

The list API covers access, modification, search, and sorting. Anything that touches a single slot at a known index is O(1); anything that scans the contents or shifts elements is O(n). The cost is noted in the comments where it matters.

fruits = ["apple", "banana", "cherry"]


# Access by position, O(1)
fruits[0]      # "apple"    first element
fruits[-1]     # "cherry"   last element (negative counts from the end)


# Slicing [start:stop:step] returns a NEW list, O(k)
fruits[0:2]    # ["apple", "banana"]   the stop index is excluded
fruits[::2]    # every second element
fruits[::-1]   # the whole list reversed


# Add
fruits.append("date")           # one item at the end      O(1) amortised
fruits.insert(1, "avocado")     # at index 1               O(n), shifts the rest
fruits.extend(["fig", "grape"]) # many at the end          O(k)


# Remove
fruits.remove("banana")         # first match by value     O(n), scan + shift
fruits.pop()                    # take the last item       O(1)
fruits.pop(0)                   # take the first item      O(n), shifts the rest


# Search
"cherry" in fruits              # is it present?           O(n), scans
fruits.index("cherry")          # its position, errors if absent   O(n)
fruits.count("apple")           # how many times it appears        O(n)


# Sort
fruits.sort()                   # in place, ascending      O(n log n)
fruits.sort(reverse=True)       # in place, descending
sorted(fruits)                  # a NEW sorted list, original untouched

Checking if an element is in the list

Section titled “Checking if an element is in the list”

Use the in operator. It returns True or False, so it reads naturally inside an if:

fruits = ["apple", "banana", "cherry"]


"banana" in fruits         # → True
"mango" in fruits          # → False
"mango" not in fruits      # → True   the negated form


if "cherry" in fruits:
    print("found it")

in scans the list from the start and stops at the first match, so the cost is O(n) in the worst case. For a handful of checks on a small list this is fine.

If you need to find where the element is, not just whether it exists, use index. It returns the position, but raises ValueError when the value is absent, so check with in first:

if "cherry" in fruits:
    pos = fruits.index("cherry")   # → 2

One thing to know for later: if you check membership many times, or the list is large, a set does the same test in O(1) instead of O(n). Convert once with set(fruits) and check against that. The trade-off is that a set does not keep order or duplicates. The Sets page covers this.

Looping over the elements

Section titled “Looping over the elements”

The standard way to go through a list is to loop over it directly. You get each element in order, and you never touch an index:

fruits = ["apple", "banana", "cherry"]


for fruit in fruits:
    print(fruit)        # apple / banana / cherry

This is the form to reach for by default. It reads like plain English, works on any iterable, and cannot run off the end or skip an item the way manual index bookkeeping sometimes does. Use it whenever the loop only needs the values themselves.

Reach for an index only when you actually need one, for example to know the position of each item or to walk two lists together. Those cases are next.

Iterating with index and pairing lists

Section titled “Iterating with index and pairing lists”

range(len(lst)) works but is not idiomatic Python. enumerate() gives you the index and the value together without the boilerplate, and zip() lets you walk two lists in lockstep without managing a shared counter. Both return lazy iterators, so they do not build a second list in memory.

fruits = ["apple", "banana", "cherry"]
prices = [1.20, 0.50, 2.00]


# enumerate() gives (index, value) pairs — prefer it over range(len(...))
for i, fruit in enumerate(fruits):
    print(i, fruit)                    # 0 apple / 1 banana / 2 cherry


# start= shifts the counter without changing the list
for i, fruit in enumerate(fruits, start=1):
    print(f"{i}. {fruit}")             # 1. apple / 2. banana / 3. cherry


# zip() pairs two lists element by element, stops at the shorter one
for fruit, price in zip(fruits, prices):
    print(f"{fruit}: ${price:.2f}")    # apple: $1.20 / banana: $0.50 / cherry: $2.00


# unzip: turn a list of pairs back into two lists
pairs = [("apple", 1.20), ("banana", 0.50), ("cherry", 2.00)]
names, costs = zip(*pairs)             # names = ("apple", "banana", "cherry")

How zip() works

Section titled “How zip() works”

zip() takes two or more lists and walks them in parallel, pairing up the elements that sit at the same position. The first items of each list become one group, the second items become the next group, and so on. Each group is a tuple.

  fruits = ["apple",  "banana", "cherry"]
  prices = [ 1.20,     0.50,     2.00   ]
             │          │         │
             ▼          ▼         ▼
  zip(fruits, prices) yields:
     ("apple", 1.20)   ("banana", 0.50)   ("cherry", 2.00)
       pos 0             pos 1              pos 2

What it produces is a lazy iterator, not a list. It hands over one tuple at a time as you loop, and builds nothing extra in memory. You usually consume it in a for loop, unpacking each tuple into two names at once:

for fruit, price in zip(fruits, prices):
    #   ^^^^^  ^^^^^ each tuple is unpacked here
    print(fruit, price)

If you want to see the pairs as an actual list rather than loop over them, wrap the call in list():

list(zip(fruits, prices))
# → [("apple", 1.20), ("banana", 0.50), ("cherry", 2.00)]

When the lists are different lengths, zip() stops at the shortest one and drops the leftover tail of the others, without raising an error. Keep that in mind when the inputs might not line up.

Reach for zip() whenever you have two (or more) related lists and need matching elements together: names with scores, keys with values, x-coordinates with y-coordinates. It replaces the older habit of looping over range(len(...)) and indexing both lists by hand, which is easier to get wrong.

Aggregates and boolean tests

Section titled “Aggregates and boolean tests”

min(), max(), and sum() reduce a list to a single value. any() and all() do the same for boolean questions: any() stops as soon as it finds one match, all() stops as soon as it finds one failure, so neither one scans the whole list if the answer is clear early. Both accept a generator expression, which avoids building an intermediate list just to test a condition.

The key= parameter on sort() and sorted() lets you sort by a derived value without touching the elements themselves. Python’s sort is stable, meaning elements that compare equal keep their original relative order, which matters when you sort by one field and then by another.

numbers = [3, 1, 4, 1, 5, 9, 2, 6]


min(numbers)                        # 1
max(numbers)                        # 9
sum(numbers)                        # 31


any(x > 8 for x in numbers)        # True   — at least one element satisfies the condition
all(x > 0 for x in numbers)        # True   — every element satisfies the condition
any(x > 100 for x in numbers)      # False  — none match


# sort by a key without changing the original order of equal elements (stable sort)
words = ["banana", "apple", "cherry", "apricot"]
words.sort(key=len)                 # ["apple", "banana", "cherry", "apricot"]
                                    # "apple" and "banana" are both length 5 or 6 —
                                    # their relative order from the original is kept

Removing by index and slice assignment

Section titled “Removing by index and slice assignment”

del removes by index or by slice and has no return value, unlike pop() which hands the removed item back. Slice assignment goes further: you can replace a range of elements with a different-length sequence, so the list grows or shrinks in place without you having to loop.

The difference between clear() and reassigning to [] matters when more than one variable points at the same list. clear() modifies the object every reference sees. Reassigning just rebinds one name to a new object and leaves the original untouched.

fruits = ["apple", "avocado", "banana", "cherry"]


# del removes by index or slice — no return value
del fruits[0]             # removes "apple"         O(n), same shift as pop(0)
del fruits[0:2]           # removes first two items O(n)


# slice assignment replaces a range with new values in place
fruits = ["apple", "banana", "cherry"]
fruits[1:3] = ["kiwi", "lime", "mango"]  # replaces 2 elements with 3; list grows
# → ["apple", "kiwi", "lime", "mango"]


fruits[1:3] = []          # delete a range without del; same effect as del fruits[1:3]
# → ["apple", "mango"]


# clear() empties in place — every reference to the list sees the change
a = [1, 2, 3]
b = a
a.clear()
print(b)                  # []   b sees the same empty list


# reassignment creates a new object — other references are unaffected
a = [1, 2, 3]
b = a
a = []
print(b)                  # [1, 2, 3]   b still points at the original list

Concatenation, repetition, and copying

Section titled “Concatenation, repetition, and copying”

+ builds a new list from two existing ones and leaves both unchanged. += looks similar but works differently: it calls extend() on the left-hand list in place, which is O(k) where k is the length of the right side, and no new list is created. [x] * n fills a fixed-length list with a repeated value, useful when you need a default-filled buffer before writing into it by index.

All three copy forms (a.copy(), a[:], list(a)) produce a shallow copy: a new list whose slots point at the same objects as the original. For a list of immutable values like numbers or strings that is fine. For a list of mutable objects like dicts or other lists, a mutation inside one of those objects will be visible through both copies, because both copies hold references to the same object. Use copy.deepcopy(a) when you need full independence.

a = [1, 2, 3]
b = [4, 5, 6]


a + b                     # [1, 2, 3, 4, 5, 6]   new list, a and b unchanged
a += b                    # extends a in place: [1, 2, 3, 4, 5, 6]  (same as a.extend(b))


[0] * 5                   # [0, 0, 0, 0, 0]   fill a fixed-length list with a default


# shallow copy — three equivalent forms
a.copy()                  # explicit, clearest intent
a[:]                      # slice of the whole list
list(a)                   # construct a new list from any iterable

Nested lists

Section titled “Nested lists”

A list can hold other lists, which is the simplest way to represent a 2-D matrix or any ragged structure in Python. Access is chained indexing: matrix[row][col] reads the outer list first to get the inner one, then indexes into that. There is no special matrix syntax.

One trap: [[0] * 3] * 3 looks like a 3×3 grid of zeros, but the three rows are the same object repeated. Writing matrix[0][0] = 1 changes all three rows at once. The comprehension form below creates three independent row lists.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]


matrix[1][2]              # 6   → row 1, column 2


# transpose: swap rows and columns
transposed = [[row[i] for row in matrix] for i in range(len(matrix[0]))]
# → [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Insert and retrieve: where the cost comes from

Section titled “Insert and retrieve: where the cost comes from”

Why lst[i] is O(1)

Section titled “Why lst[i] is O(1)”

Every slot in the backing array is the same size: a pointer, 8 bytes on a 64-bit machine. Python records two things when it creates the list: the address of the first slot and the slot size. To reach element i, it computes where that slot lives:

  lst = ["apple", "banana", "cherry"]


  slot size: 8 bytes (one pointer)
  first slot at address: 1000


  index 0  →  1000 + 0 × 8  =  1000   "apple"
  index 1  →  1000 + 1 × 8  =  1008   "banana"
  index 2  →  1000 + 2 × 8  =  1016   "cherry"

That calculation takes the same amount of work whether the list has 3 elements or 3 million. Python goes straight to the slot without looking at anything else in the list. The length of the list does not affect how long the lookup takes, which is why it is O(1).

Why append is O(1) amortised

Section titled “Why append is O(1) amortised”

Python does not allocate exactly as many slots as the list currently holds. It always reserves a few extra. An append that finds a free slot just writes into it and updates the length counter: one step, O(1).

  lst = [1, 2, 3]   after three appends


  [ 1 | 2 | 3 | _ | _ | _ | _ | _ ]
                ↑
                three spare slots — next append lands here, no copy needed

The spare slots run out eventually. When they do, Python allocates a larger block, copies the existing elements across, and only then writes the new value. That copy is O(n).

  lst = [1, 2, 3, 4, 5, 6, 7, 8]   all slots used


  [ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 ]   full


  append(9):


  1. allocate new block (roughly 1.125× larger):
     [ _ | _ | _ | _ | _ | _ | _ | _ | _ ]


  2. copy all 8 elements across:
     [ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | _ ]


  3. write the new value:
     [ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ]   O(n) this one time

The O(n) copy is expensive but rare. If you append n times to an empty list, the copies happen at sizes 1, 2, 4, 8, … totalling roughly n copy operations spread over n appends, which averages out to O(1) per append. That is what “amortised O(1)” means: not that each append is fast, but that the total work across all appends is proportional to n.

  10 appends — when does a copy happen?


  append(1)  →  copy at size 0          1 copy
  append(2)  →  copy at size 1          1 copy
  append(3)  →  copy at size 2          2 copies
  append(4)  →  spare slot, no copy     —
  append(5)  →  copy at size 4          4 copies
  append(6)  →  spare slot, no copy     —
  append(7)  →  spare slot, no copy     —
  append(8)  →  spare slot, no copy     —
  append(9)  →  copy at size 8          8 copies
  append(10) →  spare slot, no copy     —
                                        ────────
                                        16 copies total for 10 appends → ~1.6 copies/append → O(1)

Why insert(0, x) is O(n)

Section titled “Why insert(0, x) is O(n)”

insert(0, x) must open a gap at position 0. There is no way to do that without moving every existing element one slot to the right first.

  lst = [2, 3, 4, 5]


  insert(0, 1):


  step 1 — shift every element right by one:


    before:  [ 2 | 3 | 4 | 5 | _ ]
              ↓   ↓   ↓   ↓
    after:   [ _ | 2 | 3 | 4 | 5 ]   4 moves for 4 elements


  step 2 — write the new value at index 0:


             [ 1 | 2 | 3 | 4 | 5 ]

The number of moves equals the number of elements after the insertion point. At index 0 that is every element, so the cost grows with the list. At index k it is n - k moves, still O(n) in the worst case.

  insert(0, x)   →  shifts n elements      O(n)   worst case
  insert(k, x)   →  shifts n−k elements    O(n)   still linear in general
  append(x)      →  shifts 0 elements      O(1)   amortised

If your code frequently adds or removes at the front, use a collections.deque. Its appendleft() and popleft() are O(1) because it is not a contiguous array, so nothing needs to shift.

Complexity reference

Section titled “Complexity reference”

The table below collects the cost of every common list operation in one place. The “Why” column ties each cost back to the dynamic array structure: contiguous slots make reads and writes O(1), but they also mean that reshaping the list (opening or closing a gap anywhere except the end) forces a shift.

OperationCostWhy
lst[i]O(1)direct address into a contiguous block
lst[i] = xO(1)overwrite one slot in place
append(x)O(1) amortisedspare slot → one write; full → copy all then write; copies are rare
insert(0, x)O(n)shifts every later element right
pop()O(1)drops the last slot
pop(0)O(n)shifts every later element left
x in lstO(n)linear scan
lst.sort()O(n log n)Timsort
len(lst)O(1)stored as metadata

List comprehensions

Section titled “List comprehensions”

A comprehension builds a list from any iterable in a single expression. It replaces the common pattern of starting with an empty list and appending inside a loop, and states the intent upfront instead.

The pattern has three parts, always in this order:

  [ expression   for item in iterable   if condition ]
    ─────────    ──────────────────    ──────────────
    what to      where each value       which values
    put in the   comes from             to keep
    new list                            (optional)

Read it left to right: first the value you want, then where the values come from, then an optional filter that decides which ones make it in. The if part can be left off when you want every element.

It maps directly onto the loop you would otherwise write. These two produce the same list:

# The loop version
result = []
for x in range(10):
    if x % 2 == 0:
        result.append(x * x)


# The comprehension: same three pieces, one line
result = [x * x for x in range(10) if x % 2 == 0]
#         ^^^^^     ^^^^^^^^^^^^^^     ^^^^^^^^^^^^
#         value     source            filter

The order inside the comprehension is the same order the loop runs in: take the source, apply the filter, then produce the value. Only the value expression moves to the front so you can see the result at a glance.

For more on comprehensions, filtering, flattening, and the difference from map()/filter(), see the List comprehensions page.

# Transform: square each number from 0 to 9.
# No if clause, so nothing is dropped.
squares = [x**2 for x in range(10)]
# → [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]


# Filter: keep only the even numbers from 0 to 19.
# The value is just x, because items are kept as they are, with no transform.
evens = [x for x in range(20) if x % 2 == 0]
# → [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]


# Flatten: two for clauses run left to right, like nested loops.
# The outer picks each inner list, then the inner walks its numbers.
flat = [n for row in [[1, 2], [3, 4]] for n in row]
# → [1, 2, 3, 4]

Common pitfalls

Section titled “Common pitfalls”

Two mistakes come up often enough to be worth calling out explicitly. The first is assuming that assigning a list to a new variable copies it. It does not. Both names end up pointing at the same object, so a change through one is visible through the other. The second is forgetting that Python’s sort is stable and what that implies when you sort by a key: elements with equal keys stay in their original order, which is either exactly what you want or completely invisible until something breaks.

# 1. Assignment does not copy. It makes a second name for the SAME list.
a = [1, 2, 3]
b = a            # a and b point at one list
b.append(4)
print(a)         # [1, 2, 3, 4]   changing b changed a


b = a.copy()     # make a real (shallow) copy: a.copy(), a[:], or list(a)


# 2. Sorting is stable: items with an equal key keep their original order.
data = [("Bob", 2), ("Alice", 1), ("Bob", 1)]
data.sort(key=lambda x: x[1])    # sort by the number
# [("Alice", 1), ("Bob", 1), ("Bob", 2)]   the two Bobs stay in input order

Adding many elements at once

Section titled “Adding many elements at once”

When you add items one at a time with append, the list has to resize itself several times as it fills up, and each resize copies everything it already holds into a bigger block. If you already have the items together, you can skip most of that: hand them all over in one call with extend (or +=), and Python sizes the list once for the whole batch.

new_items = list(range(50))    # 50 values you want to add


# One at a time: the list resizes 7 times while growing to hold 50
result = []
for x in new_items:
    result.append(x)


# All at once: the list is sized for 50 in a single step
result = []
result.extend(new_items)       # same effect: result += new_items

The difference is how many times the backing array is reallocated:

  Adding 50 items with append(), one by one:


    []  grows at  4 → 8 → 16 → 24 → 32 → 40 → 52
        7 reallocations, each one copies the elements added so far


  Adding the same 50 items with extend():


    []  ──extend(50 items)──►  capacity 52 in one step
        1 reallocation, no repeated copying

Because extend receives the whole batch, it can ask Python for enough room straight away. The for loop cannot: it sees the items one at a time, so the list grows in stages and copies its contents at each stage.

This works when the source has a known length, like a list, a tuple, or a range. A generator does not know its length in advance, so extend cannot pre-size for it and grows in stages as before. If you want the single-allocation behaviour, turn it into a list first with extend(list(gen)).

One honest caveat: for 50 elements none of this matters for speed. Seven reallocations of tiny arrays cost nothing you could measure. The batch approach earns its keep when you add many thousands of elements in a hot loop. For small lists, pick whichever reads best, which is usually a comprehension when you are generating values:

result = [x * 2 for x in range(50)]    # clear, and already efficient