Welcome to Fundamental Data Structures!

In your journey through Computer Science, you've already used variables to store single pieces of information, like a name or a score. But what happens if you need to store the names of 100 students or every move in a game of Chess? Creating 100 different variables would be a nightmare! This is where data structures come to the rescue. They allow us to organize and store data so we can use it efficiently. In this chapter, we are going to master Arrays and Lists.


1. What is a Data Structure?

At its simplest, a data structure is a specialized format for organizing, processing, retrieving, and storing data. Think of it like the difference between throwing all your clothes in a pile on the floor versus using a chest of drawers. The drawers (the data structure) make it much easier to find exactly what you need!

Static vs. Dynamic Data Structures

This is a big concept in the Oxford AQA syllabus, so let's break it down. Data structures generally fall into two categories:

Static Data Structures: These have a fixed size that is determined at the beginning (when the program is compiled). You cannot change the size while the program is running.

  • Analogy: A row of 10 lockers in a school. You can't suddenly add an 11th locker to the middle of the wall!
  • Advantage: They are very fast to access because the computer knows exactly how much memory they take up.
  • Disadvantage: You might waste space if you don't fill all the slots, or run out of space if you have too much data.

Dynamic Data Structures: These can grow and shrink in size while the program is running.

  • Analogy: A digital photo album on your phone. You can keep adding photos as long as you have storage space.
  • Advantage: They only use the memory they need at that specific moment.
  • Disadvantage: They are slightly more complex for the computer to manage, which can make them a bit slower than static structures.

Quick Review: If you know exactly how many items you will store, use a static structure. If the number of items changes, dynamic is your friend!


2. Arrays and Lists

In many programming languages, arrays are the classic example of a static data structure, while lists are often dynamic.

Understanding Arrays

An array is a collection of items of the same data type stored under a single identifier (name). Each item in the array is called an element.

To find a specific element, we use an index. Crucial Point: In Computer Science, we almost always start counting from 0, not 1!

Example: If we have an array called Scores: [10, 25, 30, 45]

  • Scores[0] is 10
  • Scores[1] is 25
  • Scores[3] is 45

How Python Handles This

Did you know? Python doesn't actually have a built-in "static array" like C# or Java. Python uses lists, which are dynamic. However, for your exam, you should know that you can use lists to solve problems that require arrays. If you specifically need an array in Python, you would have to import a module like numpy or array.

Common Mistake: Trying to access an index that doesn't exist. If an array has 5 items, the last index is 4. Trying to access index 5 will cause an "Index Out of Range" error!


3. Two-Dimensional (2D) Arrays

Don't worry if this seems tricky at first! A 1D array is like a single row of lockers. A 2D array is like a whole wall of lockers with rows and columns. It is essentially an array of arrays.

Analogy: Think of a 2D array like a Cinema Seating Plan or a Spreadsheet.

To find a piece of data in a 2D array, you need two coordinates: [row][column].

Example: A 2D array called Grid

[ "A", "B", "C" ]
[ "D", "E", "F" ]
[ "G", "H", "I" ]

  • To get "A", we use Grid[0][0]
  • To get "F", we use Grid[1][2] (Row 1, Column 2)
  • To get "G", we use Grid[2][0] (Row 2, Column 0)

Memory Aid: Always remember RC (like an RC car or RC Cola) — Row first, then Column!


4. Working with Arrays and Lists

In your exams, you might be asked to use iteration (loops) to process data in these structures.

Step-by-Step: Printing a 1D Array

  1. Start a loop from 0 to the length of the array minus 1.
  2. Inside the loop, use the loop counter as the index.
  3. Print the element at that index.

Step-by-Step: Searching a 2D Array

  1. Use a nested loop (a loop inside a loop).
  2. The outer loop goes through each row.
  3. The inner loop goes through each column in that row.
  4. Check the value at [row][column] to see if it matches what you are looking for.

Key Takeaways for the Exam

  • Data Structures are ways to organize data to make it useful.
  • Static structures (like traditional arrays) have a fixed size.
  • Dynamic structures (like lists) can grow or shrink.
  • Indexing starts at 0.
  • 2D Arrays use two indices: \( array[row][column] \).
  • In Python, lists are the most common way to store these collections, but you should understand the theory of arrays for the syllabus.

Quick Review Box:
Q: What is the main advantage of a static data structure?
A: It is memory efficient and fast to access because its size and location in memory are fixed.

Q: If an array has 10 elements, what is the index of the final element?
A: 9 (because we start at 0!).