Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 225 ยท Getting Started

Memory and Data Layout

See how memory is organized, why arrays sit side by side while linked nodes are scattered, how Python references work, and what is vs == really compares.

Before you can choose between an array and a linked list, you need a mental picture of where data actually lives. Every structure in this tutorial is, underneath, just a way of arranging values in the computer's memory and finding them again. Two arrangements matter most: items stored side by side, and items scattered and connected by references. Almost every trade-off you will meet later grows out of that single difference.

This lesson builds the picture in three steps: how memory looks to a program, how the two layouts differ, and how Python's own objects fit in, including the surprising fact that every Python variable is a reference.

Memory as a long row of numbered boxes

Think of memory as an enormous street of mailboxes, each with a number called its address and room for one byte. A program asks the system for a stretch of mailboxes, stores values in them, and later reads them back by address. An integer in a low-level language like C takes four bytes, which is four mailboxes in a row.

TEXT
address:   1000  1001  1002  1003  1004  1005  1006  1007
         +-----+-----+-----+-----+-----+-----+-----+-----+
bytes:   |  .  |  .  |  .  |  .  |  .  |  .  |  .  |  .  |
         +-----+-----+-----+-----+-----+-----+-----+-----+
          \_____ one int ____/    \_____ next int ____/

You almost never see addresses in Python, and we will not print them here since they change from run to run. But the idea is essential: a data structure is a plan for where to put values and how to get from one to the next.

Contiguous layout: the array

An array reserves one unbroken block of memory and puts its items one after another, each the same size. Because every item has the same size and the block starts at a known address, the address of item i is just arithmetic:

TEXT
address of item i = start + i * item_size
TEXT
index:      0      1      2      3      4
          +------+------+------+------+------+
values:   |  7   |  3   |  9   |  4   |  1   |
          +------+------+------+------+------+
address:  1000   1004   1008   1012   1016        (4 bytes each)

item 3 lives at 1000 + 3 * 4 = 1012

That one multiplication and addition is why reading a[i] takes the same time for i = 3 and i = 3,000,000: no searching, no following links. This is called constant time or O(1), and the next chapter, Big O, gives it a precise name. The price: the block has a fixed size. To insert in the middle you must shift every later item over, and to grow beyond the block you must allocate a bigger one and copy. Details in Arrays and Dynamic Arrays.

Linked layout: nodes and references

A linked structure takes the opposite approach. Each item lives in its own small box called a node, placed anywhere in memory. Each node stores its value and a reference (a "pointer") to the next node.

TEXT
   head
    |
    v
 +-----+------+     +-----+------+     +-----+------+
 |  7  |  --------> |  3  |  --------> |  9  | None |
 +-----+------+     +-----+------+     +-----+------+
  node at 5200        node at 1720        node at 9040

Nodes can be anywhere, so adding one means creating a node and rewiring a reference or two; nothing shifts. But you can no longer jump to item 3 by arithmetic. To reach it you must start at head and follow references one by one, which takes time proportional to the position. See Linked Lists.

Array (contiguous) Linked nodes
Read item i direct, O(1) follow i links, O(n)
Insert/delete in the middle shift items, O(n) rewire references, O(1) once you hold the spot
Extra memory per item none one reference per node
Growth copy to a bigger block allocate one node
Neighbours in memory yes no

Neither layout is "better". They answer different questions, which is the theme of Abstract Data Types.

Cache locality: why neighbours are fast

Modern processors are far faster than main memory. To hide the delay, the CPU fetches memory in chunks called cache lines (commonly 64 bytes) and keeps recently used chunks in a small, very fast cache. Reading one item pulls its neighbours in for free.

With a contiguous array, a scan reads item 0 and the neighbouring items arrive in the same chunk, so the next several reads are served from cache. With linked nodes scattered across memory, nearly every step lands in a different chunk, and each step may be a slow trip to main memory. This is locality of reference.

You cannot measure this reliably in the browser, so here is a simplified simulation. We model memory as a map from address to value, pretend a cache line holds 4 neighbouring addresses, and count how many different lines a traversal touches.

Python Counting cache lines touched

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 contiguous array needs 4 line loads for 16 items; the scattered list needs one load per node. Both scans do 16 steps, so Big O treats them as equal, but real arrays win on speed. That is why dynamic arrays beat linked lists in practice so often, and why Python's list is the default choice.

Python's list does not hold the objects themselves in its block. It holds a contiguous block of references to objects, which can live anywhere. The references are packed together, so scanning them is quick, but reading the objects they point to may still jump around memory.

Everything in Python is a reference

In Python, a variable is a name attached to an object. Assignment never copies the object; it attaches another name.

TEXT
a = [1, 2, 3]       a ----+
b = a                      +---->  [1, 2, 3]
                    b ----+

So changing the list through b also changes it through a, because there is only one list. Compare with a copy, where there are two:

Python Names, references and copies

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.

is versus ==

  • a == b asks: do these objects have equal values?
  • a is b asks: are these the very same object?

Use == to compare values. Use is almost only for None (if node is None:), because there is exactly one None object. Two equal lists can be different objects, so [1, 2] is [1, 2] is False even though [1, 2] == [1, 2] is True.

Do not use is to compare numbers or strings. Python sometimes reuses small integers and short strings behind the scenes, so is may appear to work and then fail on other values. The result is an implementation detail, not something to rely on.

Passing to functions

Arguments are passed the same way: the function gets a new name for the same object. Mutating it inside the function changes it for the caller; re-assigning the parameter name does not.

Python Mutating vs rebinding in a function

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.

Immutable objects (numbers, strings, tuples) cannot be changed in place, so every "change" produces a new object. Mutable ones (lists, dicts, sets, your own class instances) can. This is the root of the shared-row and mutable-default traps from Python You Need for DSA.

How big are Python objects?

sys.getsizeof reports the size of one object in bytes, not counting the objects it refers to. It is enough to see the main pattern: a list stores a reference per item, so its size grows with its length.

Python Sizes with sys.getsizeof

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.

Python objects carry overhead (a reference count and a type pointer), so a Python int is much bigger than a C int. When you need compact numeric arrays, the standard library offers array.array and, outside the standard library, NumPy. For learning algorithms, the overhead does not change the Big O.

Stack versus heap

Programs use two main regions of memory.

  • The call stack holds one frame per active function call: its parameters, local names and where to return. Frames are pushed on call and popped on return, strictly last in, first out. Allocation is automatic and very fast, but the stack is small.
  • The heap is a large pool for objects whose lifetime isn't tied to one call. In Python, all objects live on the heap; stack frames only hold references to them.
TEXT
   call stack (small, LIFO)                heap (large)
  +--------------------------+         +---------------------+
  | frame: helper(x)         |         |  [1, 2, 3]          |
  |   x  ------------------------------>                      |
  +--------------------------+         |  "hello"            |
  | frame: main()            |         |                     |
  |   data --------------------------->|  Node(7) -> Node(4) |
  +--------------------------+         +---------------------+

The stack's small size explains the recursion limit. Every recursive call adds a frame, so recursing too deep exhausts the stack. Python guards against this by raising RecursionError after about a thousand nested calls, as the next demo shows (the error is caught, so the program continues).

Python Stack overflow caught on purpose (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.

Lessons on recursion cover how to avoid this with base cases and iteration. The size of that stack is also part of an algorithm's space complexity.

Common mistakes

  • Assuming b = a copies a list. It adds a name. Use a.copy(), a[:] or list(a); for nested data use copy.deepcopy.
  • Comparing with is instead of == for values.
  • Thinking array indexing and list insert(0, x) cost the same. Reading is direct; inserting at the front shifts everything.
  • Ignoring layout in Big O discussions. Two O(n) scans can differ a lot in practice if one is contiguous and one is not.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can an array read item i in constant time?

    Items are contiguous and equal-sized, so the address of any item is a single multiplication and addition.
  2. 2. Which is true of a singly linked list compared with an array?

    Nodes are scattered and linked by references, so you reach a position by walking the chain. Each node also stores a reference, which costs memory.
  3. 3. After a = [1, 2] and b = a, then b.append(3), what is a?

    b is another name for the same list object, so changes through b are visible through a.
  4. 4. What does x is y test?

    is compares identity. Use == to compare values, and reserve is mainly for comparisons with None.
  5. 5. Why is scanning a contiguous array usually faster in practice than scanning linked nodes, even though both are O(n)?

    Big O counts steps, not memory behaviour. Contiguous items arrive together in cache lines, while scattered nodes cause many more cache misses.

Summary

  • Memory is a row of addressed bytes; a data structure is a plan for arranging values in it.
  • Contiguous layouts (arrays) give O(1) indexing by address arithmetic and good cache locality, but inserting in the middle shifts items.
  • Linked layouts store nodes anywhere, joined by references: cheap rewiring, slow indexing, and an extra reference per item.
  • In Python every variable is a reference to an object; assignment adds a name, it never copies.
  • == compares values; is compares identity and is mainly used with None.
  • Mutable objects can be changed through any name, which is the source of shared-list bugs.
  • The call stack is small and holds frames, the heap holds objects, and deep recursion raises RecursionError.

Next: Abstract Data Types and Data Structures, where you will separate what a structure promises from how it is built.