Chapter 6: Contiguous Memory (Arrays & Lists)

Learning Objectives

• Understand why declaring hundreds of individual variables is impossible.
• Learn how data is grouped together sequentially in RAM.
• Master zero-based indexing and pointer arithmetic.
• Iterate through collections of data dynamically.

Prerequisites

Chapter 4: The Engine of Software (Loops).

Why Does This Exist?

Imagine you are building a system to store the high scores of a video game.

You could create variables: score1 = 500, score2 = 450, score3 = 300.

What happens when you have a million players? Are you going to manually type out a million variable names in your code? And how would you loop over them? You can't write a for loop that magically increments the name of a variable.

We needed a way to store many pieces of data under a single name, organized sequentially.

History

Early computing heavily relied on matrices for scientific math calculations. Engineers needed a way to tell the memory controller: "I don't just want one box. I want 1,000 boxes, all right next to each other in a straight line."

Thus, the Array was born. It is the oldest, most fundamental Data Structure in computer science.

Mental Model

Think of variables from Chapter 1 as individual, detached houses scattered randomly around a city.

An Array is an Apartment Building.

The building has one master address (the variable name). Inside, there are sequentially numbered mailboxes (the indexes).

If you want to find an apartment, you don't need a map of the whole city. You just go to the building, and count up from the ground floor.

Internal Working

Why are arrays so incredibly fast?

Because they rely on basic math instead of searching.

When you create an array of 5 integers, the OS finds a contiguous block of empty memory. Let's say it starts at memory address 0x100.

Since an integer takes 4 bytes, the OS knows the layout:

• Item 0 is at 0x100
• Item 1 is at 0x104
• Item 2 is at 0x108

If you ask the CPU for "Item 100", it doesn't search. It just calculates: Base Address + (100 * Size). It teleports directly to that exact memory address instantly. This is why arrays have O(1) read time.

Syntax

In Python, dynamic arrays are called "Lists", and they are defined using square brackets [].

1scores = [90, 85, 100]
2print(scores[0])  # Output: 90
3scores.append(75)

Token breakdown:

• [90, 85, 100]: Creates the array in memory.
• scores[0]: Index access. This tells the computer: "Go to the `scores` building, and open mailbox number 0."
• Zero-Based Indexing: In computer science, we always start counting at 0. The first item is 0, the second is 1. Why? Because the index represents the "offset" from the base memory address. The first item has an offset of 0 bytes!
• .append(75): A built-in function that tacks a new box onto the end of the building.

Visual Explanation

Tiny Example

Combining Arrays with Loops is the most powerful combo in programming.

1names = ["Alice", "Bob", "Charlie"]
2
3for name in names:
4    print("Welcome, " + name)

Walkthrough

• Line 1: Creates an array of three strings.
• Line 3: The for loop asks the array: "Give me your first item." It puts "Alice" into the name variable.
• Line 4: Prints "Welcome, Alice".
• The loop repeats automatically, grabbing "Bob", then "Charlie", and stopping perfectly when the array ends.

Common Mistakes

1colors = ["Red", "Blue"]
2print(colors[2])

Debugging

When working with arrays, the number one rule of debugging is checking its length.

If your loop isn't running, or it's crashing, use the len() function.

print(len(my_list))

If it prints 0, your array is empty, and that's why your code is failing.

Mini Project

Time: 15 minutes.

Goal: The Averager.

Create a list of 5 numbers. Write a for loop that adds them all together into a total variable. Outside the loop, divide the total by the length of the list to find the average. Print it.

Bigger Project

Time: 1 hour.

Goal: The To-Do List App (Console).

Create an empty list called tasks. Use a while True: loop to repeatedly ask the user for a command: "add", "view", or "quit".

If "add", ask for a task string and .append() it.

If "view", loop through the list and print each task with a number (e.g., "1. Buy milk").

If "quit", break the loop.

Production Usage

Twitter timelines are arrays of Tweet objects.

When you scroll, Twitter fetches the next chunk of the array. When you post, they .insert() your Tweet at index 0 (the top of the list).

However, inserting at index 0 of a massive array is very slow, because the CPU has to manually shift every single other tweet down by one memory slot to make room!

Best Practices

• Keep Arrays Homogeneous: While languages like Python let you mix types (e.g., ["Text", 42, True]), you should avoid it. Arrays should represent a collection of the same kind of data.
• Avoid inserts in the middle: Adding to the end of an array is fast. Inserting into the middle requires shifting everything after it. For massive data, this kills performance.

Interview Questions

Easy: Why do array indexes start at 0?

Answer: Because the index represents the memory offset from the start of the array. The first element is exactly 0 bytes away from the start.

Medium: What is the difference between a static array and a dynamic array (List)?

Answer: A static array (in C/Java) has a fixed size determined at creation. A dynamic array (like Python Lists) automatically requests more memory from the OS and copies itself if you add too many items.

Hard: What is the time complexity of looking up an item in an array by its index, versus looking up an item by its value?

Answer: Index lookup is O(1) (instant), because of pointer arithmetic. Value lookup (e.g., finding where "Bob" is) is O(N) (linear), because the CPU must check every single index one by one until it finds a match.

Revision Sheet

Connections

• Previous Chapter: Functions and Loops are the primary tools used to manipulate Arrays.
• Future Chapters: Arrays are terrible at finding data by a keyword (like looking up a definition in a dictionary). For that, we need Hash Maps (Chapter 7).