Interact with lists dynamically. Supports nested lists, negative indexing, and slicing complexity.
Overview
A dynamic array, not a linked list
A Python list is a contiguous block of pointers to objects, with spare capacity at the end. That single implementation fact explains every performance characteristic it has.
Operation
Complexity
Why
lst[i]
O(1)
Direct offset into the block
lst.append(x)
O(1) amortised
Writes into spare capacity
lst.pop()
O(1)
Removes from the end
lst.insert(0, x)
O(n)
Shifts every element right
lst.pop(0)
O(n)
Shifts every element left
x in lst
O(n)
Linear scan
lst.remove(x)
O(n)
Scan, then shift
len(lst)
O(1)
Stored, not counted
Slicing lst[a:b]
O(b−a)
Copies
The two O(n) operations at the front are the ones that cause real performance problems, because the code looks innocent. A loop doing lst.pop(0) n times is O(n²) and works fine on 100 items and unusably on 100,000.
Use collections.deque when you need to add or remove at the front. It gives O(1) at both ends.
Operations
Tip: Use [ ] for nested lists
Snippet
List State
my_list = [ ... ]
len: 4
Select an operation or click boxes to pop elements.
Insight
Python lists can contain heterogeneous data, including other lists (nesting).
•Nested Lists: Multi-dimensional structures like `[[1,2], [3,4]]`.
•Slicing: Creates a shallow copy of a sub-range.
•Center-Aligned: All items in the visualization are precisely centered.
Complexity Bar
Current Op ComplexityO(1)
Python List Lab: A Practical Guide
A Python list is a dynamic array, not a linked list. That single fact explains why appending is fast, inserting at the front is slow, and slicing always costs a copy.
Indexing and slicing
Indices count from 0, and negative indices count from the end: lst[-1] is the last element, lst[-2] the second-last.
A slice takes [start:stop:step], where start is inclusive, stop is exclusive, and any part may be omitted. With lst = [10, 20, 30, 40, 50]:
lst[1:4] → [20, 30, 40] # stop is excluded
lst[:3] → [10, 20, 30]
lst[::2] → [10, 30, 50] # every second element
lst[::-1] → [50, 40, 30, 20, 10] # reversed
The exclusive stop is deliberate: it makes lst[:k] + lst[k:] reconstruct the original for any k, and it makes the length of a slice simply stop − start. Every slice returns a new list, so slicing an n-element list costs O(n) time and O(n) memory — slicing in a loop is a common accidental quadratic.
What each operation costs
lst[i] # O(1) direct address
lst.append(x) # O(1) amortised
lst.pop() # O(1) from the end
lst.insert(0, x) # O(n) shifts everything
lst.pop(0) # O(n) shifts everything
x in lst # O(n) linear scan
lst[a:b] # O(b−a) copies
Amortised O(1) for append means individual appends are occasionally expensive. When the underlying array fills, Python allocates a larger one and copies everything across — O(n) for that one call. Because the array grows by a proportion rather than a fixed amount, those resizes become rarer as the list grows, and the average over many appends is constant.
Why append is amortised O(1)
The list holds more capacity than its length. When it fills, Python allocates a larger block — growing by roughly an eighth of the current size — and copies everything across.
That resize is O(n). Spread across the many appends that fit in the new capacity, the average cost per append is constant. That is what amortised means: individual operations can be expensive, the sequence is cheap.
The practical consequence is that appending in a loop is fine, and it is worth knowing that a list comprehension is faster still because the append happens in C rather than through the interpreter:
squares = [x * x for x in range(1000)] # fastest
squares = list(map(lambda x: x*x, range(1000)))
squares = []
for x in range(1000):
squares.append(x * x) # slowest of the three
If you know the final size and need a fixed-length list, [None] * n allocates once.
Copying, and the aliasing trap
A list holds references, so copying has two levels.
a = [1, 2, 3]
b = a # NOT a copy - another name for the same list
b.append(4)
print(a) # [1, 2, 3, 4]
c = a.copy() # shallow copy - a new list, same objects inside
c = a[:] # same thing
c = list(a) # same thing
Shallow means the new list is separate, and the objects it points to are shared:
Use copy.deepcopy() when the nested objects must be independent.
The same aliasing produces the most notorious Python gotcha:
board = [[0] * 3] * 3 # three references to ONE row
board[0][0] = 1
print(board) # [[1,0,0], [1,0,0], [1,0,0]]
board = [[0] * 3 for _ in range(3)] # three separate rows - correct
[x] * n repeats the reference n times. For immutable values that is harmless; for mutable ones it is a bug.
Exploration guide
Watch the exclusive stop. Set Start to 1 and Stop to 4, then press Run Expression. Three elements come back, not four — index 4 is the boundary, not a member.
Reverse with a negative step. Set Step to −1 and leave start and stop empty. The whole list comes back reversed, and it is a copy: the original is untouched.
Index from the end. Set Index (i) to −1 and run. You get the last element without needing to know the length — the idiom that replaces lst[len(lst)−1].
Compare a front insert with an append. Use Select Method to insert at index 0, then to append. Both look instant here, but only one avoids shifting every element — the difference shows up at a hundred thousand elements, not five.
What trips people up
Using pop(0) as a queue. Every removal shifts the whole list, so a queue built this way is O(n²). Use collections.deque, which is O(1) at both ends.
The mutable default argument.def f(items=[]) creates the list once, at definition time, and every call shares it. Use None as the default and build the list inside.
Assuming assignment copies.b = a binds another name to the same list; mutating b changes a. Use a[:] or list(a) for a shallow copy.
Removing items while iterating. Deleting during a for loop shifts the remaining elements and the loop skips items. Iterate over a copy, or build a new list with a comprehension.
Multiplying to build a grid.[[0]*3]*3 makes three references to the same row. Use a comprehension: [[0]*3 for _ in range(3)].
What to remember
A Python list is a contiguous dynamic array, so indexing is O(1), appending is amortised O(1), and anything touching the front is O(n) because every later element must shift. Slices are always copies, negative indices count from the end, and the stop bound is exclusive. Most list performance bugs are one of two things: treating the front like the back, or slicing inside a loop.
Sorting, and the in-place trap
items = [3, 1, 2]
items.sort() # sorts IN PLACE, returns None
new = sorted(items) # returns a NEW sorted list
items = items.sort() # BUG - items is now None
That last line is the classic mistake, and it follows a Python convention: methods that mutate return None, precisely so this error fails loudly rather than silently.
The key parameter is where the useful power is:
words.sort(key=len) # by length
people.sort(key=lambda p: (p.surname, p.first)) # by surname, then first name
items.sort(key=lambda x: -x.score) # descending by score
Sorting by a tuple gives multi-key sorting in one pass. And because Timsort is stable, sorting by one key and then another also works — the second sort preserves the first's order within ties, which is how "sort by department, then by name within department" is done as two sorts.
Choosing the right structure
Need
Use
Indexed access, ordered items
list
Add/remove at both ends
collections.deque
Membership testing
set — O(1) instead of O(n)
Key-value lookup
dict
Fixed record, hashable
tuple
Counting
collections.Counter
Grouping
collections.defaultdict(list)
Numeric arrays, maths
numpy.ndarray
Sorted order maintained
bisect.insort, or sortedcontainers
The membership row is the one that most often matters:
# O(n^2) - 'in' scans the list for every item
for x in items:
if x in other_list: ...
# O(n) - build a set once
other = set(other_list)
for x in items:
if x in other: ...
That transformation is the most common real-world optimisation in Python, and it usually shortens the code as well.
Memory
A Python list of a million integers uses considerably more memory than a million integers' worth of data: the list holds a million pointers (8 bytes each), and each small integer is itself an object with a header.
Two alternatives when that matters:
numpy.ndarray stores raw values contiguously — a million 64-bit integers is 8MB, against roughly 40MB for a list. It also enables vectorised operations that run in C.
Generators avoid materialising the list at all:
total = sum(x * x for x in range(10_000_000)) # no list built
For a large intermediate that is consumed once, a generator expression is both faster and dramatically lighter.
The costs behind the operations you use every day
A Python list is a dynamic array, and almost every surprising thing about its performance follows from that one fact. Measuring the operations side by side turns a table of complexities into something you can predict from.
example_01.pyPython
import time
def timed(fn, reps=5):
best = None
for _ in range(reps):
t0 = time.time(); fn(); dt = time.time() - t0
best = dt if best is None else min(best, dt)
return best * 1000
n = 30000 # kept modest: the O(n^2) row runs in the browser
base = list(range(n))
set_base = set(base)
def front_insert(k):
a = []
for i in range(k):
a.insert(0, i) # every element shifts one slot right
print("%-34s %12s" % ("operation, repeated %d times" % n, "ms"))
print("%-34s %12.1f" % ("append to the end",
timed(lambda: [x for x in range(n)])))
print("%-34s %12.1f" % ("insert(0, x) at the front",
timed(lambda: front_insert(n))))
print("%-34s %12.1f" % ("index a[i]",
timed(lambda: [base[i] for i in range(n)])))
print("%-34s %12.1f" % ("x in list (linear scan, x200)",
timed(lambda: [(n - 1) in base for _ in range(200)])))
print("%-34s %12.1f" % ("x in set (hash lookup, x200)",
timed(lambda: [(n - 1) in set_base for _ in range(200)])))
# Indexing is one address calculation, so it does not care where in the
# list you look. Inserting at the FRONT has to move every element right,
# which is why it is the one to avoid -- and `in` on a list is the same
# problem in a different costume: a scan, not a lookup.
#
# The famous one is append, which is amortised O(1). Python over-allocates
# so most appends are free and occasional ones copy everything. You can
# see the over-allocation directly:
import sys
print()
print("%8s %14s %10s" % ("length", "bytes", "grew?"))
a = []
last = sys.getsizeof(a) # so row 0 is the starting size, not a jump
for i in range(17):
size = sys.getsizeof(a)
print("%8d %14d %10s" % (len(a), size, "yes" if size != last else ""))
last = size
a.append(i)
# The size jumps at a few lengths and is flat between them. Each jump
# copies the whole list, but the new capacity is proportional to the
# current size, so the copies get rarer exactly as fast as they get more
# expensive. Averaged over n appends, that is a constant per append.
#
# The aliasing trap, which is a consequence of lists being references:
grid = [[0] * 3] * 3 # three references to ONE row
grid[0][0] = 9
print()
print("[[0]*3]*3 after setting grid[0][0] = 9:", grid)
grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 9
print("the comprehension version: ", grid)
# The first form copied the REFERENCE three times, so every row is the
# same object and writing through one writes through all of them. This is
# the single most common bug when building a grid, and the fix is the
# comprehension, which evaluates [0]*3 afresh each time.
import copy
outer = [[1, 2], [3, 4]]
shallow = outer[:]
deep = copy.deepcopy(outer)
outer[0][0] = 99
print()
print("original mutated -> shallow copy sees it:", shallow[0][0] == 99)
print(" deep copy does not: ", deep[0][0] == 1)
# Slicing gives a new outer list holding the SAME inner lists. For nested
# data that is usually not the copy you meant.
Output
Questions people ask
Is a Python list a linked list? No — it is a dynamic array of pointers, contiguous, with O(1) indexing.
Why is insert(0, x) slow? Every existing element shifts one position right. Use deque.appendleft.
Why does list.sort() return None? By convention, mutating methods return None, so x = x.sort() fails visibly.
What is the difference between list and tuple? Tuples are immutable and can be dictionary keys; lists are mutable and cannot.
How do I remove duplicates?list(set(items)) loses order; list(dict.fromkeys(items)) preserves it.
When should I use NumPy instead? For numeric data of uniform type, especially with arithmetic across the whole array — far less memory and far faster.
Recap in one screen
A list is a contiguous array of pointers with spare capacity, which is why indexing and appending are O(1).
Operations at the front are O(n) because everything shifts — use deque there.
Assignment shares the list; copy() is shallow; [x]*n repeats a reference.
sort() mutates and returns None; sorted() returns a new list; both are stable.
Replacing in list with in set is the most common Python speed-up available.
Run it in Python
What a Python list actually is underneath — a resizable array of references — and the four consequences that follow, each measured: O(1) indexing, O(n) inserts at the front, over-allocated growth, and the aliasing trap.
lists.pyPython 3
# A Python list is a resizable array of references. Everything follows.
import sys, time
a = [10, 20, 30, 40, 50]
print("list :", a)
print("a[2] :", a[2], "- computed address, O(1), whatever the length")
print("a[-1] :", a[-1], "- negative indices count from the end")
print("a[1:4] :", a[1:4], "- a slice is a NEW list, O(k) to build")
# --- where the cost is -------------------------------------------------
N = 30_000
for label, action in [
("append (end)", lambda lst: lst.append(1)),
("insert (front)", lambda lst: lst.insert(0, 1)),
]:
lst = []
start = time.time()
for _ in range(N):
action(lst)
print(f"{label:>15}: {N} operations in {time.time() - start:.3f}s")
print("insert(0, x) shifts every existing element one place right.")
# --- growth is over-allocated ------------------------------------------
print()
lst = []
previous = sys.getsizeof(lst)
print("length bytes")
for i in range(1, 18):
lst.append(i)
size = sys.getsizeof(lst)
if size != previous:
print(f"{i:>6} {size:>5} <- reallocated, with room to spare")
previous = size
# --- lists hold references, not copies ---------------------------------
print()
grid_wrong = [[0] * 3] * 3 # three references to ONE list
grid_right = [[0] * 3 for _ in range(3)]
grid_wrong[0][0] = 9
grid_right[0][0] = 9
print("[[0]*3]*3 ->", grid_wrong, " all three rows changed")
print("[[0]*3 for _ in ..] ->", grid_right, " only the first")
b = a # another name for the same list
c = a[:] # a copy
a.append(60)
print()
print("b is a:", b is a, "->", b)
print("c is a:", c is a, "->", c)
Output
How the code works
a[2]One multiplication and one memory read. The list stores references contiguously, so element i is at a computable address — this is the difference between a list and a linked list.
lst.insert(0, 1)Everything after the insertion point moves one slot right, so this is O(n). Doing it in a loop is O(n²), and it is the usual reason a “queue” written on a list is slow — see queues.
sys.getsizeof(lst)The size jumps in steps, not per item. CPython over-allocates on growth so that most appends need no reallocation, which is what “amortised O(1)” means concretely.
[[0] * 3] * 3Multiplying a list repeats the reference three times, so all three rows are one object. This is the single most common Python bug in grid and matrix code.
b = a versus c = a[:]Assignment binds another name to the same object; slicing builds a new one. is asks which object, == asks about contents, and confusing them is how mutation surprises happen.
Change one thing
Raise N to 60,000. The append timing doubles; the front-insert timing roughly quadruples.
Replace the front-insert loop with collections.deque and appendleft. Same result, back to linear.
Print sys.getsizeof for a list of 1,000 items and for 1,000 separate integers. The list stores references, so it is far smaller than the things in it.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Indexing a Python list is O(1) because the list stores:
One multiplication and one read. This is the whole difference between a list and a linked list.
What does [[0] * 3] * 3 build?
Multiplying repeats the reference, not the object. This is the most common Python bug in grid and matrix code.
sys.getsizeof shows a list's size jumping in steps rather than per item because:
That is what "amortised O(1) append" means concretely: most appends are free, and occasionally one pays for a copy.
Cheat sheet
Python List Lab
A Python list is a contiguous block of pointers to objects, with spare capacity at the end. That single implementation fact explains every performance characteristic it has.
TimeComplexityPython wiki - operation costs by container type
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.