Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 225 ยท Arrays and Lists

Arrays and Python Lists

Learn how arrays store data in a row, why indexing is O(1) while insert and delete cost O(n), and how Python lists, the array module and 2D lists behave.

The array is the oldest and most important data structure. Almost every other structure in this tutorial is either built on top of an array or exists to fix one of its weaknesses. If you understand what an array is good at and where it hurts, you will pick the right tool far more often.

An array is a collection of items stored one after another in a single block of memory. Because the items sit side by side, the computer can jump straight to any item if it knows its position. That one property explains almost everything in this lesson: why reading is instant, why inserting in the middle is slow, and why Python's list is built the way it is.

The picture: a row of numbered boxes

Imagine a street with identical houses. House 0 is at the start, house 1 is next door, and so on. If you know where the street starts and how wide each house is, you can compute the address of house 5 without walking past houses 1 to 4.

TEXT
index:      0     1     2     3     4
          +-----+-----+-----+-----+-----+
values:   | 12  |  7  | 30  |  4  | 19  |
          +-----+-----+-----+-----+-----+
address:   base  base+s  base+2s  ...

The address of item i is base + i * s, where s is the size of one item. One multiplication and one addition, no matter how long the array is. That is why reading or writing a[i] is O(1): constant time.

An array has a length (how many items it holds). Valid indexes run from 0 to length - 1. Starting at 0 feels odd at first, but it falls out of the formula: the first item is base + 0 * s, zero steps from the start.

Python lists are arrays of references

Python's built-in list is the array you will use 95% of the time. There is one detail you need to know: a list does not store the values themselves. It stores references (pointers) to objects. All references have the same size, so the address formula still works and indexing is still O(1). If you want the memory story, see Memory and Data Layout.

Python Indexing a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Negative indexes are pure convenience: a[-1] is a[len(a) - 1]. They are great for "the last item" but easy to misuse in loops, as you will see under common mistakes.

Bounds

Asking for an index outside 0 .. len - 1 raises IndexError. Python checks every access; languages like C do not, which is how many security bugs happen.

Python Out of bounds (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first access works and prints 30. The second raises IndexError, which we catch and print. Notice the contrast with slicing: a[1:100] quietly stops at the end of the list. That convenience can hide bugs, so be sure you want it.

What is cheap and what is expensive

Because items are packed together, anything that keeps the layout unchanged is cheap. Anything that must shift items to make room or close a gap is expensive.

Operation Time Why
Read or write a[i] O(1) Address arithmetic
Append at the end O(1) amortized Usually free space at the end (see Dynamic Arrays)
Remove from the end (pop()) O(1) Nothing to shift
Insert at index i O(n) Every item from i onward moves one step right
Delete at index i O(n) Every item after i moves one step left
Search for a value (x in a) O(n) Must look at items one by one (unless sorted, see Searching)
Length len(a) O(1) The list stores its size

Let's see the shifting for real by writing our own insert and counting the moves.

Python Insert by shifting, counting the moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Inserting at the end costs no moves. Inserting at the front moves every existing item. With n items, the average position forces about n / 2 moves, and the worst case forces n. Dropping constants, that is O(n). Python's built-in a.insert(i, x) and del a[i] do exactly this shifting for you, just in fast C code.

Fast C code does not change the Big O. A list of a million items still shifts a million references to insert at the front. If you do that in a loop, your program crawls. Remember this when we reach Queues.

Deleting

Deleting works the mirror way: close the gap by shifting items left. Removing the last item is free; removing the first shifts everything.

Python Delete by shifting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The array module: real, typed arrays

A Python list can mix types ([1, "two", 3.0]) and stores references, so each number is a full Python object. When all items have the same numeric type, the standard array module stores raw machine values packed together, using far less memory.

Python array.array stores raw numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In interviews and day-to-day Python you will almost always use a plain list. Reach for array (or NumPy) when you hold millions of numbers and memory matters. The indexing rules are the same.

Lists of lists: 2D arrays

A grid is an array whose items are arrays. grid[r][c] means "row r, column c". Each row is its own list object, which is where the classic trap lives.

Python The shared-rows trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

[[0] * cols] * rows repeats the same row object rows times, so changing one row appears to change all of them. [[0] * cols for _ in range(rows)] builds a new row each time. Note that [0] * cols is fine for the inner list because integers are immutable. The problem only appears when the repeated item is itself mutable. We use grids a lot in Matrices and 2D Arrays.

Time and space complexity

  • Space: an array of n items takes O(n) memory. A Python list also keeps a few spare slots at the end for cheap appends.
  • Access by index: O(1). This is the array's superpower.
  • Search, insert and delete in the middle: O(n).
  • Building a list of n items by appending: O(n) total.

When to use an array: you need fast access by position, you mostly add and remove at the end, or you want data packed for iteration speed. When to avoid it: you must insert or delete at the front or middle constantly (consider a linked list or deque), or you need lookups by key (use a hash table).

Common mistakes

  • Off-by-one: the last valid index is len(a) - 1, not len(a).
  • Modifying a list while looping over it. Removing items shifts the rest and the loop skips elements. Loop over a copy or build a new list.
  • Shallow copies: b = a makes b another name for the same list. b = a[:] or a.copy() makes a new list, but nested lists inside are still shared.
  • a[-0]: it is just a[0], not the last item.
  • Using pop(0) or insert(0, x) in a loop, quietly turning an O(n) algorithm into O(nยฒ).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is reading a[i] an O(1) operation in an array?

    Items are stored contiguously with equal-sized slots, so the address is base + i * size. No searching or walking is needed.
  2. 2. A list has n items. What is the worst-case cost of inserting a new item at index 0?

    Every existing item must shift one step to the right to make room, which is n moves.
  3. 3. What does grid = [[0] * 3] * 2; grid[0][0] = 5; print(grid) show?

    The outer multiplication repeats a reference to the same inner list, so both rows are the same object.
  4. 4. What does a[1:100] do when a has only 3 items?

    Slices clip to the valid range instead of raising errors. Only a single out-of-range index raises IndexError.
  5. 5. Which operation on a Python list is O(1) (amortized or exact)?

    Removing the last item needs no shifting. insert(0, x) and pop(0) shift everything, and x in a scans the list.

Summary

  • An array stores items in one contiguous block, so index i is found by arithmetic: reads and writes are O(1).
  • Inserting or deleting anywhere except the end shifts items and costs O(n).
  • A Python list is a dynamic array of references; array.array stores packed raw numbers.
  • [[0] * c] * r shares rows. Use [[0] * c for _ in range(r)] for a real grid.
  • Out-of-range single indexes raise IndexError; out-of-range slices are clipped.

Next: Array Operations