Introduction: Organising Our Data
Welcome to your study notes on data structures! In computer programming, we constantly work with information—like high scores in a game, names in a class register, or items in a shopping basket. If you had to create a brand new variable for every single item, your code would quickly become messy and hard to manage.
That is where data structures come in. In this chapter, you will learn how to group lots of items together under a single name using lists, arrays, and tables. Don't worry if this seems new or tricky at first—we will break down every concept step by step!
Key Takeaway: A data structure is a specialised container used in programming to store, organise, and manage multiple pieces of data under one single identifier (variable name).
1. What Are Lists and Arrays?
Imagine a row of numbered lockers at school. Each locker can hold an item, and the entire row shares one common name, such as Year7Lockers. This is exactly how lists and arrays work in programming!
Arrays
• In computer science theory, an array is a linear collection of items stored right next to each other in memory.
• Same Data Type: Traditionally, an array holds items that are all of the exact same type (for example, only integers or only text strings).
• Fixed Size: A classic static array has a fixed size defined when it is created.
Lists
• A list is an ordered sequence of data items.
• Dynamic Size: Unlike static arrays, lists in textual languages like Python can grow and shrink whenever you add or remove items while the program is running.
• Mixed Data Types: Lists can store items of different data types together (such as numbers, words, and decimals).
Analogy: Think of a static array like an egg carton (it has a fixed number of slots for eggs only), while a list is like a shopping bag (you can add or remove different items at any time!).
Key Takeaway: In Python (the main textual language used at KS3), we use lists to store ordered sequences of data using square brackets [].
2. Understanding Indexing (The Zero-Based Rule!)
To pick out a specific item from a list or array, computers use a number called an index (plural: indices).
The Golden Rule of Indexing: Start at Zero!
In most programming languages, counting does not start at \(1\). It starts at \(0\)! This is known as zero-based indexing.
Let's look at an example list of fruits:
fruits = ["apple", "banana", "cherry", "date"]
• First item ("apple") is at index \(0\): fruits[0]
• Second item ("banana") is at index \(1\): fruits[1]
• Third item ("cherry") is at index \(2\): fruits[2]
• Fourth item ("date") is at index \(3\): fruits[3]
Did You Know? If a list contains \(n\) items, the index of the very last item is always \(n - 1\). For example, in our list of \(4\) fruits, the last item is at index \(4 - 1 = 3\).
Key Takeaway: Always remember that the first item in any list or array is at index \(0\), not \(1\).
3. Essential List Operations
Once you have created a list, you can perform several basic operations to view, change, add, or delete items.
1. Creating a List
We create a list by placing items inside square brackets [] separated by commas:
shopping_list = ["bread", "milk", "cheese"]
2. Accessing and Updating Items
• Accessing: To view an item, use the list name followed by the index in square brackets.
print(shopping_list[1]) → displays "milk"
• Updating / Overwriting: You can replace an existing item by assigning a new value to its index.
shopping_list[0] = "bagel" → changes "bread" to "bagel"
3. Adding Items (Append and Insert)
• Append: Adds an item to the very end of the list.
shopping_list.append("eggs") → ["bagel", "milk", "cheese", "eggs"]
• Insert: Adds an item at a specific index and shifts everything else to the right.
shopping_list.insert(1, "butter") → places "butter" at index \(1\)
4. Removing Items
• Remove by Value: Finds and removes the first occurrence of a specific value.
shopping_list.remove("milk") → searches for "milk" and deletes it.
• Delete by Index: Removes an item at a specific position using del or .pop().
del shopping_list[0] or shopping_list.pop(0) → removes whatever item is at index \(0\).
5. Finding the Length
Use the function len() to find out how many items are currently in your list.
len(shopping_list) → returns the total count as an integer.
6. Traversal (Looping Through a List)
Traversal means visiting every item in a list one by one using a loop.
• Looping by Item:
for item in shopping_list:
print(item)
• Looping by Index:
for i in range(len(shopping_list)):
print(shopping_list[i])
Key Takeaway: Use .append() to add to the end, .insert() to add at a specific index, .remove() to delete by value, and len() to check the size.
4. Tables: 2D Lists and 2D Arrays
Sometimes data needs to be organised in a grid of rows and columns, just like a spreadsheet, a cinema seating plan, or a tic-tac-toe board. This is called a table, a 2D array, or a 2D list (a list of lists!).
How a 2D List Looks in Code
Let's look at a \(3 \times 3\) grid representing a game board:
board = [
["X", "O", "X"], # Row 0
["O", "X", "O"], # Row 1
["O", "O", "X"] # Row 2
]
Accessing Elements in a 2D Table
To pinpoint an item in a 2D data structure, you must give two index numbers inside square brackets: [row_index][column_index].
• board[0][0] refers to Row \(0\), Column \(0\) → "X"
• board[0][1] refers to Row \(0\), Column \(1\) → "O"
• board[2][1] refers to Row \(2\), Column \(1\) → "O"
Memory Trick: Always remember RC (like a Remote Control car or a Row then Column). Row comes first, Column comes second!
Key Takeaway: A table or 2D array is a "list of lists" accessed using the coordinate format table[row][column] starting from index \(0\).
5. Common Pitfalls and Mistakes to Avoid
Here are the top mistakes students make when working with data structures—and how you can avoid them!
• The "Off-by-One" Error: Trying to access index \(3\) in a list of \(3\) items. Since indices run from \(0\) to \(2\), asking for index \(3\) will cause an IndexError: list index out of range.
• Overwriting the Entire List: If you write my_list = "apple", you replace your entire list with a single word! To add an item, use my_list.append("apple"), or to replace a specific item, use my_list[0] = "apple".
• Row-Column Confusion: Writing grid[column][row] instead of grid[row][column]. Remember your Remote Control rule: Row first, then Column!
• Value vs. Index Deletion: Using list.remove(0) when you want to delete the first item. .remove(0) searches for the number \(0\) inside the list. To delete by position, use del list[0] or list.pop(0).
6. Quick Review Checklist
Check your understanding with this quick review:
• Data Structure: A container for storing and organising multiple data values.
• Array: A fixed-size, linear structure traditionally holding items of the same data type.
• List: A dynamic, ordered sequence of items enclosed in square brackets [].
• Zero-Based Indexing: The first item is at index \(0\), and the last item is at index \(n - 1\).
• Table (2D Array/List): A grid of rows and columns accessed as [row][column].
• Key Methods: .append() adds to the end; .insert() adds at an index; .remove() deletes by value; len() gives the total count.