How programs organize information — lists, arrays, strings, records, dictionaries, stacks, and queues — and how to choose the right structure for the problem at hand
Every program works with data. A music app tracks thousands of songs. A school system stores tens of thousands of student records. A navigation app holds the coordinates of millions of roads. In each case, the program does not just store data — it organizes data so that the right piece can be found, updated, added, or removed quickly and reliably. The way a program organizes its data is called a data structure.
Part II of this textbook introduced you to variables that hold a single value — a number, a string, a Boolean. But most real programs deal with collections of values. A playlist is a collection of song titles. A gradebook is a collection of scores. A contact list is a collection of name-and-phone-number pairs. Each kind of collection calls for a different organizational strategy, and choosing the right strategy is one of the central skills of computer science.
This chapter introduces the most important data structures you will encounter as a beginning computer scientist: lists and arrays, strings as sequences, records, dictionaries and maps, stacks, and queues. The goal is not to make you an expert programmer of every structure — that depth belongs in Data Structures and Algorithms. The goal is to give you a clear mental model of each structure, a sense of what problems it solves, and enough familiarity to read, trace, and reason about code that uses them.
A teacher needs to store the names of every student in a class, then add a new student who enrolled late, then find and remove a student who transferred out. Which way of organizing the names would make each of these tasks easiest? A plain numbered list? A sorted alphabetical list? A special collection that supports fast search? By the end of this chapter you will know how to think through exactly these kinds of decisions — and why the structure you choose shapes every operation that follows.
Imagine you need to store the names of all 300 students at a school. You could create 300 separate variables — student1, student2, and so on all the way to student300. But this quickly becomes unmanageable. What if you need to find a student's name? You would have to check all 300 variables one by one. What if you need to add a student? You have to invent a new variable. What if you need to sort the names alphabetically? You would be facing hundreds of separate operations with no clear way to loop through them.
The problem is not the data itself — it is the organization. A data structure is a way of arranging and storing data in a computer's memory so that it can be used efficiently. The right data structure makes certain operations fast and easy; the wrong one makes the same operations slow and error-prone. Choosing a data structure is one of the most consequential decisions a programmer makes.
Data structures matter for several practical reasons. First, they determine which operations are natural. A list makes it easy to go through items one by one in order. A dictionary makes it easy to look up a value by name. A stack makes it easy to undo the last action. Second, data structures determine efficiency. Some structures find items quickly; others find them slowly. Some add items quickly; others require rearranging everything. As programs grow large — handling millions of records, responding in milliseconds — the choice of structure becomes critical. Third, data structures shape code. Programs built around well-chosen structures are readable, maintainable, and easier to debug. Programs built around poorly chosen structures become tangled.
A data structure is an organized way to store and access a collection of data. The right structure for a problem depends on what operations the program needs to perform on the data — not just how much data there is.
In Chapter 7 you learned about variables — containers that hold a single value. In Chapter 9 you used lists briefly to pass collections of items around in functions. This chapter gives those ideas a proper foundation. Every data structure is ultimately a way to extend the single-variable idea to collections of values.
The most fundamental data structure for an ordered collection is a list. A list is a sequence of items arranged in a specific order. The order matters: the first item is distinct from the second, which is distinct from the third, and so on. Items in a list are also called elements.
A list can hold any kind of item: numbers, strings, Boolean values, or even other lists. In Python, a list is written using square brackets, with items separated by commas.
scores = [88, 95, 71, 100, 83]
names = ["Alice", "Bob", "Carmen", "David"]
mixed = [42, "hello", True, 3.14]
empty = []
scores holds five integers. names holds four strings. mixed holds items of different types. empty is a valid list with no items.Once you have a list, there are several standard operations you need to perform on it. The table below shows the most common ones, using Python syntax as a concrete example. The key insight is that these operations — accessing an item, adding an item, removing an item, finding the length — are fundamental to what lists are for, regardless of the programming language.
| Operation | Python Example | What It Does |
|---|---|---|
| Access by position | names[0] | Returns the first element: "Alice" |
| Find the length | len(names) | Returns the number of elements: 4 |
| Add to the end | names.append("Eva") | Adds "Eva" as the last element |
| Insert at a position | names.insert(1, "Bea") | Inserts "Bea" at position 1, shifting others |
| Remove by value | names.remove("Bob") | Removes the first occurrence of "Bob" |
| Remove by position | names.pop(2) | Removes and returns the item at position 2 |
| Check membership | "Alice" in names | Returns True if "Alice" is in the list |
| Loop through items | for name in names: | Visits each element in order |
Python lists are mutable — you can change their contents after they are created. You can add items, remove items, and replace items. This is different from strings, which are immutable (you cannot change individual characters in place). Mutability matters because it affects what your program can do with data after creating it.
The list scores = [88, 95, 71, 100, 83] can be visualized as a row of slots. Each slot has an index number (its position) and a value (its content).
Highlighted: scores[3] → 100. Counting starts at 0, so position 3 is the fourth slot.
days that holds the names of the seven days of the week in order.temps = [72, 68, 75, 80, 77], what does len(temps) return?items holds ["pen", "paper", "stapler"]. Write the Python statement that adds "tape" to the end of the list.len(items) return?remove("Bob") and pop(2) on a list.The index of an element is its position within the list. Computer science counts positions starting at zero, not one. This is called zero-based indexing, and it is a convention used across virtually all modern programming languages. If a list has five elements, their indexes are 0, 1, 2, 3, and 4. There is no index 5.
Zero-based indexing exists for a mathematical reason rooted in how memory addresses are calculated, but for now the rule is simply: the first element is at index 0, the second at index 1, and so on. The last element is at index (length − 1).
colors = ["red", "green", "blue", "yellow"]colors[0] → "red"
colors[2] → "blue"
colors[3] → "yellow"
colors[1] = "lime"
# Now: ["red", "lime", "blue", "yellow"]
len(colors) → 4If you ask for an index that does not exist, the program raises an index error — a runtime error that stops execution. For a list of five elements (indexes 0–4), requesting index 5 or index -6 will cause an error. Always be aware of the valid range of indexes before accessing a list.
One of the most common mistakes with lists is the off-by-one error — accessing index (length) instead of (length − 1). If scores has 5 elements, valid indexes are 0–4. Writing scores[5] causes an IndexError at runtime. Always double-check that your index does not exceed (length − 1).
Python allows negative indexes as a shorthand for counting from the end. Index -1 refers to the last element, -2 to the second-to-last, and so on. This is a convenience feature: colors[-1] is the same as colors[len(colors) - 1].
Each element has two valid indexes: a positive one counting from the left, and a negative one counting from the right.
A slice extracts a contiguous portion of a list and returns it as a new list. In Python, the syntax is list[start:stop], where start is the index of the first element to include and stop is the index of the first element to exclude. Slicing never modifies the original list.
nums = [10, 20, 30, 40, 50, 60]nums[1:4] → [20, 30, 40] # indexes 1, 2, 3
nums[0:3] → [10, 20, 30] # indexes 0, 1, 2
nums[3:] → [40, 50, 60] # from index 3 to end
nums[:2] → [10, 20] # from start to index 1
animals = ["cat", "dog", "fish", "bird", "hamster"], what is the value of each of the following?
animals[0] b. animals[3] c. animals[-1] d. animals[-2]
nums = [5, 10, 15, 20, 25, 30], what does nums[2:5] return?animals[5] cause an error for a 5-element list? What index would you use to access the last element?In many textbooks and programming languages, the word array refers to a more specific kind of ordered collection than a general list. Understanding the distinction helps you read documentation, understand how computers actually store data, and prepare for Data Structures and Algorithms.
A traditional array has three characteristics that distinguish it from a Python list. First, an array has a fixed size: you specify how many elements it will hold when you create it, and that size cannot change. If you need more space, you must create a new, larger array. Second, every element in an array must be the same type: an array of integers holds only integers, an array of characters holds only characters. Third, elements are stored in contiguous memory locations — they sit right next to each other in the computer's memory, with no gaps.
This contiguous, fixed-size layout gives arrays a significant advantage: accessing any element by index is extremely fast, because the computer can calculate exactly where in memory to look. If the array starts at memory address A and each element takes B bytes, then the element at index i is at address A + (i × B). This is a simple arithmetic calculation that takes the same tiny amount of time regardless of which index you request or how large the array is.
Python's built-in list is more flexible than a traditional array: it can grow, shrink, and hold mixed types. But this flexibility has costs. The internal bookkeeping required to support dynamic resizing and mixed types makes Python lists somewhat slower than raw arrays for very large-scale numerical work. This is why Python's scientific computing library (NumPy) provides a true fixed-type array for applications such as data science and machine learning.
| Property | Traditional Array | Python List |
|---|---|---|
| Size | Fixed at creation | Dynamic — can grow or shrink |
| Element types | Same type only | Any mix of types |
| Memory layout | Contiguous (guaranteed) | Managed internally |
| Access by index | O(1) — constant time | O(1) — constant time |
| Adding elements | Not supported (fixed size) | append(), insert() |
| Typical use | Low-level, performance-critical code | General-purpose programming |
An integer array [10, 20, 30, 40] starting at memory address 1000, with each integer taking 4 bytes.
Element at index i is at address 1000 + (i × 4). This arithmetic is why array access is so fast.
You have been using strings since Chapter 7, but they are worth revisiting here because a string is not just a piece of text — it is a sequence of characters. Every character in a string has a position, just like every element in a list. You can access individual characters by index, slice substrings, find the length, and loop through characters one at a time. This means everything you learned about lists and indexes applies directly to strings.
The key difference between strings and lists is that strings are immutable: you cannot change an individual character in place. To create a modified version of a string, you must build an entirely new string. This immutability is by design — it makes strings safe to share between different parts of a program without worrying that one part will accidentally modify what another part is reading.
word = "computing"word[0] → "c"
word[3] → "p"
word[-1] → "g"
len(word) → 9
word[0:4] → "comp"
word[4:] → "uting"
word[:3] → "com"
for ch in word:
print(ch)
# prints: c o m p u t i n g (one per line)
Because strings are immutable, operations that seem to "change" a string actually produce a new string and leave the original unchanged. The original variable can then be assigned to the new string if you want the change to persist.
greeting = "hello world"greeting.upper() → "HELLO WORLD"
# greeting is still "hello world" — upper() returns a new string
greeting.replace("world", "Python") → "hello Python"
# original unchanged
greeting.split(" ") → ["hello", "world"]
# produces a list of substrings
| Method | What It Returns | Example |
|---|---|---|
.upper() | Uppercase version | "hello".upper() → "HELLO" |
.lower() | Lowercase version | "WORLD".lower() → "world" |
.strip() | Removes leading/trailing whitespace | " hi ".strip() → "hi" |
.replace(a, b) | Replaces all occurrences of a with b | "cat".replace("c","b") → "bat" |
.split(sep) | Splits into a list at each separator | "a,b,c".split(",") → ["a","b","c"] |
.startswith(s) | True if string begins with s | "Python".startswith("Py") → True |
in operator | True if substring is present | "py" in "python" → True |
s = "algorithm", evaluate: a. s[0] b. s[-1] c. s[2:5] d. len(s)"data" from the string "data science" using a slice.name = " Margaret ", write a chain of method calls that produces "margaret" (lowercase, no spaces).s[0] = "A" where s = "algorithm", expecting to change the first character. What will happen and why?A list stores many items of the same kind in order. But many real-world entities consist of several different pieces of information that belong together. A student is not just a name — a student record includes a name, a student ID number, a grade level, a list of courses, and a GPA. These different pieces of information about the same entity are called fields, and the entire grouped set of fields is called a record.
Records allow programs to represent real-world entities naturally. Instead of storing names in one list, IDs in another list, and GPAs in a third list (and trying to keep them synchronized), a record keeps all the information about one student bundled together.
In Python, records can be represented in several ways depending on the complexity of the program. At the introductory level, a common approach is to use a dictionary (covered in the next section) for each record, where the field names are keys and the field values are values. Another approach is to use a class, which is covered in later courses. What matters conceptually is the idea: a record groups named fields into a single structured unit that represents one thing in the world.
| name | "Carmen Reyes" |
| student_id | 10427 |
| grade_level | 11 |
| gpa | 3.7 |
| enrolled | True |
One record representing one student. Each row is a field: a name (key) paired with a value. All five fields together form a single coherent unit.
Records differ from lists in an important way. A list is accessed by position — you retrieve item number 0, item number 1, and so on. A record is accessed by name — you retrieve the value of the "name" field or the "gpa" field. Accessing by name is more readable and less error-prone, because field names carry meaning while position numbers do not.
In many systems, a large collection of records is organized as a table: each row is one record, and each column is one field. A school database might have a table of thousands of student records, each with the same set of fields but different values. This is exactly how relational databases (covered in Chapter 18) organize information.
| name | student_id | grade_level | gpa | enrolled |
|---|---|---|---|---|
| Carmen Reyes | 10427 | 11 | 3.7 | True |
| David Park | 10388 | 10 | 3.2 | True |
| Aisha Johnson | 10501 | 12 | 3.9 | False |
Suppose you want to look up a student's grade by their name. A list would require you to search through every element until you find the name you want — potentially checking thousands of entries. A dictionary solves this problem by organizing data as key-value pairs. Each key maps directly to one value, and looking up a value by key is extremely fast regardless of how many entries the dictionary contains.
The metaphor is exact: a physical dictionary maps each word (the key) to its definition (the value). A phone book maps each name (the key) to a phone number (the value). A dictionary data structure generalizes this pattern to any kind of key and any kind of value.
In Python, dictionaries are created using curly braces, with colons separating keys from values and commas separating pairs.
grades = {
"Alice": 92,
"Bob": 78,
"Carmen": 95,
"David": 85
}
grades["Alice"] → 92
grades["Carmen"] → 95
grades["Eva"] = 88
# grades now has 5 entries
grades["Bob"] = 82
# updates Bob's grade from 78 to 82
del grades["David"]
# removes David's entry entirely
"Alice" in grades → True
"Frank" in grades → False
| "Alice" | 92 |
| "Bob" | 78 |
| "Carmen" | 95 |
| "David" | 85 |
Keys (left column) must be unique. Values (right column) may repeat. Lookup goes in one direction: key → value.
| Rule | Explanation | Example |
|---|---|---|
| Keys must be unique | Each key appears at most once. Adding a key that already exists updates the value. | d["x"] = 1; d["x"] = 2 → value is 2 |
| Keys must be immutable | Strings, numbers, and tuples work as keys. Lists do not. | d[42] = "ok" works; d[[1,2]] = "no" fails |
| Values can be anything | Values can be numbers, strings, lists, other dicts, functions… | d["scores"] = [90, 85, 92] |
| Lookup by missing key raises an error | Requesting a key that does not exist raises KeyError | grades["Frank"] → KeyError |
Use a list when order matters and you access items by position. Use a dictionary when you need to access items by name or identifier. If you find yourself maintaining two parallel lists — one of names and one of matching values — that is a strong signal to use a dictionary instead.
grades dictionary from Example 11.7.1, write the statement that looks up Carmen's grade.names = ["apple","banana","cherry"] and prices = [0.99, 0.50, 2.49]. Rewrite this as a dictionary.Lists and dictionaries organize data for flexible access. But sometimes the structure of a problem calls for a stricter rule about how items enter and exit the collection. Two fundamental restricted-access structures are the stack and the queue. Both are used throughout computer science, from web browsers to operating systems, from compilers to network routers.
A stack is a collection in which items are added and removed from the same end, called the top. The rule is simple: the most recently added item is always the next item to be removed. This is called Last-In, First-Out, or LIFO.
The physical analogy is a stack of plates in a cafeteria. You place a clean plate on top of the stack. When someone takes a plate, they take it from the top. The plate added most recently is the one removed first. A plate deep in the stack cannot be reached until all the plates on top of it are removed.
The two fundamental stack operations are push (add an item to the top) and pop (remove the item from the top). In Python, a list can serve as a stack: append() acts as push, and pop() without an argument removes from the end (the top of the stack).
After push(10), push(20), push(30)
30 was pushed last. It will be popped first.
After pop() → returns 30
30 is gone. Now 20 is at the top.
stack = []
stack.append("page1") # push
stack.append("page2") # push
stack.append("page3") # push
# stack is ["page1", "page2", "page3"]
last = stack.pop() # pop → "page3"
# stack is now ["page1", "page2"]
A queue is a collection in which items are added at one end (the back or rear) and removed from the other end (the front). The rule is: the first item added is the first item removed. This is called First-In, First-Out, or FIFO.
The physical analogy is a line of people waiting at a ticket counter. The person who arrived first is served first. New arrivals join at the back of the line. Nobody cuts ahead. The two fundamental queue operations are enqueue (add to the back) and dequeue (remove from the front).
Queue after enqueue("A"), enqueue("B"), enqueue("C")
dequeue() removes "A" from the front. enqueue("D") adds "D" to the back. Order is preserved: first in, first out.
queue = []queue.append("job1") → ["job1"]
queue.append("job2") → ["job1", "job2"]
queue.append("job3") → ["job1", "job2", "job3"]
queue.pop(0) → "job1" # removes from front
# queue is now ["job2", "job3"]
| Property | Stack | Queue |
|---|---|---|
| Access rule | LIFO — Last In, First Out | FIFO — First In, First Out |
| Add operation | Push (to top) | Enqueue (to back) |
| Remove operation | Pop (from top) | Dequeue (from front) |
| Physical analogy | Stack of plates | Waiting line |
| Real-world use | Browser history, undo/redo, function calls | Print queues, task scheduling, message passing |
Understanding each data structure individually is the first step. The next step — and the one that actually matters in programming — is knowing which structure to choose when faced with a new problem. The key insight is this: the right data structure is the one whose natural operations match the operations your program needs to perform.
To choose wisely, ask yourself a series of questions about the problem. First, what kind of data are you storing, and how much? Second, how will you access the data? By position? By name? By order of arrival? Third, what operations will you perform most often? Adding items? Removing items? Searching? Iterating in order? Fourth, does order matter? Fifth, do you need fast lookup by a specific identifier?
Use a list when you need ordered items you access by position, and the order of items matters. Good for sequences, histories, and ordered sets.
Use an array when all items are the same type, the size is known and fixed, and you need maximum performance for numerical work.
Use a string when your data is text — a sequence of characters you will process, search, or split.
Use a record when you need to group multiple named fields describing a single real-world entity.
Use a dictionary when you need to look up values by a meaningful name or identifier — not by position. Good for any name-to-value mapping.
Use a stack when the most recent item added must be the first item removed (LIFO). Good for undo, back navigation, and tracking nested operations.
Use a queue when items must be processed in the order they arrived (FIFO). Good for scheduling, waiting lists, and ordered task processing.
| Structure | Ordered? | Access by | Add/Remove | Typical Use |
|---|---|---|---|---|
| List | Yes | Index (position) | Any end or middle | Playlists, to-do lists, grade rolls |
| Array | Yes | Index (position) | Not typically | Pixels, sensor readings, numerical data |
| String | Yes (chars) | Index (position) | Immutable — build new | Names, messages, file paths, URLs |
| Record | No ordering | Field name | Typically fixed fields | Student, product, employee, book |
| Dictionary | No ordering* | Key (name) | Any key | Word counts, lookup tables, settings |
| Stack | LIFO | Top only | Top only | Undo, browser Back, call stack |
| Queue | FIFO | Front only | Back only | Print jobs, task scheduling, messaging |
*Python dictionaries preserve insertion order as of Python 3.7, but lookup is still by key, not position.
Data structures are not abstract exercises — they are the working machinery of every piece of software you use. Understanding which structures appear in real systems helps you see why the concepts in this chapter are foundational rather than academic.
Web browsers use stacks to implement the Back button: each URL you visit is pushed onto a history stack; pressing Back pops the most recent URL. They also use queues to manage resources being downloaded in the background.
Search engines use sophisticated structures to index billions of web pages, but at their core they maintain enormous dictionaries: each word in their index maps to a list of pages where that word appears. Looking up a search term means looking up its key in this dictionary.
Social networks store user profiles as records — each user has an ID, a name, a list of posts, a list of friends, and other fields. Friend lists are themselves lists of user IDs. Finding a user's profile quickly requires dictionary-style lookup by user ID.
Video games store the positions, attributes, and states of every game object. An enemy might be a record containing location coordinates, health points, speed, and current action. Lists of enemies are processed every frame to update movement and check collisions.
Operating systems use queues to schedule processes. When several programs want to use the CPU at the same time, a scheduling queue determines whose turn it is. They also use stacks to manage function calls: each call pushes a frame onto the call stack, and returning from a function pops it off.
Databases organize data as large tables of records. Each row is one record; each column is a field. Lookup by primary key (like a student ID or product code) is implemented with structures designed for fast key-based search, building on the dictionary concept at a much larger scale.
Network routers maintain routing tables — dictionaries that map destination IP addresses to the next network hop. Incoming packets are often placed in queues while the router decides where to forward them.
| Real System | Data Structure Used | Purpose |
|---|---|---|
| Web browser | Stack | Back button history |
| Search engine | Dictionary | Word → page lookup (inverted index) |
| Social network | Records + lists | User profiles and friend connections |
| Video game | Records + lists | Game objects and their attributes |
| Operating system | Queue + stack | Process scheduling and function call management |
| Database | Tables (records) | Persistent structured data storage |
| Network router | Dictionary + queue | Routing table and packet buffer |
| Compiler | Stack | Parsing nested expressions and function calls |
( with a closing parenthesis ), including nested ones like ((a + b) * (c - d)). Explain why a stack is the natural structure for checking that parentheses are balanced.Each item describes a mistake. Identify the error and write a corrected version or explanation.
The list has 3 elements at indexes 0, 1, 2. Index 3 does not exist. What error will occur at runtime? Write the correct index to access the last element.
Strings are immutable. This raises a TypeError. How would you correctly create the string "Hello" from "hello"?
Keys must be unique. The second "a" overwrites the first. What value will print? Explain why.
pop() without an argument removes from the end, giving "C" — which is the most recently added item (LIFO). This is stack behavior, not queue behavior. Write the correct dequeue operation for the front.
Accessing a key that does not exist raises a KeyError. How could you safely check whether "Bob" is in the dictionary before accessing it?
cities = ["Cairo", "Paris", "Tokyo", "Lima", "Oslo"], answer each question.
cities[2]?cities[-1]?len(cities) return?cities[1:4] return?temps holds 7 daily temperature readings. Write the Python for loop that prints every element in the list on a separate line.s = "programming": What is s[0]?s[-3]?s[3:7]?len(s) return?"PROGRAMMING"."gram" appears in s.capitals that maps three countries to their capitals. Then write the lookup to get the capital of the second country you entered.inventory = {"pen": 40, "notebook": 15, "stapler": 7}, write statements to:
For each scenario, name the most appropriate data structure and write 1–2 sentences explaining your choice.
data = [4, 8, 15, 16, 23, 42]:
data[0]?
data[-1]?
data[2:5] return?
data[6] cause?
for loop that prints every element of a list called scores on a separate line.colors = {"sky": "blue", "grass": "green", "sun": "yellow"}:
push(5) · push(8) · push(2) · pop() · push(6) · pop()
enqueue("R") · enqueue("G") · enqueue("B") · dequeue() · enqueue("Y")
Chapter 11 gave you the containers — the data structures that hold information. Chapter 12 asks a new question: once information is stored in a structure, how do you find specific items, and how do you arrange them in order? You will learn linear search, binary search, and the basic principles of sorting algorithms. More importantly, you will learn to think about efficiency: why some approaches are dramatically faster than others as data grows larger, and how computer scientists describe and compare algorithmic performance. The intuition for Big-O that you will develop in Chapter 12 connects directly to the structures you learned here — the right structure makes the right search algorithm possible.