Introduction to Data Structures
Welcome to one of the most exciting and fundamental topics in Software Systems Development! Whether you are building a simple mobile game, a school registration system, or a massive social media platform, your program needs a clean and organized way to hold information in memory. That is exactly what a data structure does.
Think of a data structure as a specialized storage container for your data. Just like you might use an egg carton for eggs, a bookshelf for books, or a filing cabinet for documents, computer programs use different data structures depending on what kind of information they are storing and how they need to access it.
Don't worry if this topic sounds abstract right now! We are going to break everything down step-by-step with real-world examples, visual analogies, and practical programming concepts.
1. The Big Picture: Static vs Dynamic Data Structures
Before diving into specific structures, it is essential to understand the two main categories of data structures: Static and Dynamic.
Static Data Structures
A static data structure has a fixed size that is decided when the structure is created in memory. Once it is set up, it cannot grow to hold more items or shrink when items are removed.
Everyday Analogy: Think of an egg carton with \(12\) slots. Even if you only put \(4\) eggs in it, the carton still takes up the space of \(12\) slots in your fridge. If you buy a \(13\text{th}\) egg, you cannot simply stretch the carton to fit it in!
Advantages:
• Memory allocation is fixed and predictable.
• Accessing elements is extremely fast because memory locations are laid out in a continuous block.
Disadvantages:
• Inflexible: If you underestimate the size, your program runs out of space.
• Memory wastage: If you allocate space for \(1000\) items but only store \(10\), the remaining memory is reserved and wasted.
Dynamic Data Structures
A dynamic data structure can expand and contract at runtime. Memory is allocated or released as items are added or removed.
Everyday Analogy: Think of a shopping trolley. When you start shopping, it holds nothing. As you walk through the aisles, you add items one by one. If you change your mind, you take an item out.
Advantages:
• Highly flexible: Adapts to the exact amount of data your program needs at any moment.
• Efficient use of memory: You only use space for the items currently stored.
Disadvantages:
• Slightly more memory overhead per item (needed to keep track of links or resizing).
• Can lead to memory fragmentation or slower performance during large resizing operations.
Key Takeaway: Static structures (like standard arrays) have a fixed size decided in advance. Dynamic structures (like Lists) can grow and shrink while the program is running.
2. One-Dimensional (1D) Arrays
A one-dimensional (1D) array is the most common static data structure. It is an ordered collection of elements that are all of the same data type, stored in consecutive memory locations.
Understanding Indexing: The "Zero is the Hero" Rule
In almost all modern programming languages (such as C# and Java), arrays use zero-based indexing. This means the very first element is stored at index \(0\), the second at index \(1\), and so on.
If an array has a size of \(n\):
• The first element is at index \(0\).
• The last element is at index \(n - 1\).
Example: If you create an array called scores with a size of \(5\):
• scores[0] is the \(1\text{st}\) score
• scores[1] is the \(2\text{nd}\) score
• scores[2] is the \(3\text{rd}\) score
• scores[3] is the \(4\text{th}\) score
• scores[4] is the \(5\text{th}\) (last) score
Memory Aid: The Street Address Analogy
Think of an array as a row of houses on a street called scores. The house numbers (indices) start at \(0\). If you want to deliver mail to the third house, you walk to house number \(2\).
Traversing a 1D Array
Traversing simply means visiting every single element in the array one by one (for example, to display them on the screen or calculate a total). We usually use a for loop to do this.
Step-by-Step Traversal Process:
1. Start the loop counter variable at \(i = 0\).
2. Set the condition so the loop runs while \(i < \text{Length}\).
3. In each iteration, access array[i].
4. Increment \(i\) by \(1\) after each step until the end of the array is reached.
Common Pitfall: The Off-By-One Error
A very common student mistake is trying to access an element at index \(n\) (where \(n\) is the array length). For an array of length \(5\), trying to access scores[5] will crash your program with an Index Out Of Bounds Exception because the highest index is \(4\)!
Key Takeaway: 1D arrays are fixed-size, homogeneous (all items have the same type) structures. Always remember that indices run from \(0\) to \(\text{Length} - 1\).
3. Two-Dimensional (2D) Arrays
Sometimes data naturally fits into a grid or table format with rows and columns. For this, we use a two-dimensional (2D) array.
Everyday Analogies
• A Cinema Seating Plan: Each seat is identified by a Row number and a Seat (Column) number.
• A Spreadsheet: A grid of cells organized by rows and columns.
• Tic-Tac-Toe / Noughts and Crosses: A \(3 \times 3\) grid.
Accessing Elements in a 2D Array
To pinpoint an item in a 2D array, you must provide two coordinates: the row index first, followed by the column index.
Format: grid[rowIndex, columnIndex] (or grid[rowIndex][columnIndex] depending on language syntax).
Example Grid: Suppose we have a grid with \(3\) rows and \(4\) columns (total of \(3 \times 4 = 12\) elements):
• grid[0, 0] = Top-left corner cell
• grid[0, 3] = Top-right corner cell
• grid[2, 0] = Bottom-left corner cell
• grid[2, 3] = Bottom-right corner cell
Memory Trick: RC Cars!
Struggling to remember whether Row or Column comes first? Remember RC (like a Remote-Controlled car): Row first, then Column!
Traversing a 2D Array using Nested Loops
To visit every cell in a 2D grid, we use nested loops (a loop inside another loop):
• The outer loop controls which row we are currently examining.
• The inner loop visits every column across that specific row.
How it works step-by-step:
1. Outer loop starts at Row \(0\).
2. Inner loop runs through Column \(0\), Column \(1\), Column \(2\)... until the row is finished.
3. Outer loop moves to Row \(1\).
4. Inner loop repeats from Column \(0\) to the end of Row \(1\).
5. This continues until all rows are processed.
Key Takeaway: 2D arrays organize data into rows and columns. Always access them using [row, column] order, and use nested loops to traverse the full grid.
4. Dynamic Lists and Collections
In many real-world applications, you do not know in advance how many items you will need to store. For example, a shopping cart website does not know whether a customer will buy \(1\) item or \(25\) items.
To solve this, object-oriented programming provides Dynamic Lists (such as List<T> in C# or ArrayList in Java).
Core Features of Lists
• Dynamic Resizing: You do not need to specify a size when creating a list. It expands automatically as you add items.
• Built-in Methods: Lists come with powerful pre-built commands for common operations.
• Sequential Storage: Like arrays, items maintain a specific order and can still be accessed using zero-based indices (e.g., myList[0]).
Common List Operations
• Add: Appends a new item to the end of the list.
• Insert: Places a new item at a specific index, shifting all following items one position to the right.
• Remove: Deletes a specific item (or removes an item at a specific index), automatically shifting remaining items left to close any gap.
• Count / Size: Returns the current number of elements actively stored in the list.
• Clear: Removes all items from the list at once.
Did You Know?
Behind the scenes, a dynamic list usually manages an internal array. When that array fills up, the list automatically creates a larger array behind the scenes, copies the items across, and discards the old one!
5. Comparing Arrays and Lists
Choosing the correct data structure is an essential skill for your AS examinations. Here is a direct comparison to help you choose between them:
Array:
• Size: Fixed at creation (Static).
• Memory: Highly efficient; memory is allocated in one single continuous block.
• Flexibility: Low; cannot add more items than the original capacity.
• Best used when: You know the exact number of elements in advance (e.g., \(7\) days of the week, \(12\) months of the year).
Dynamic List:
• Size: Variable; grows and shrinks automatically (Dynamic).
• Memory: Slightly higher overhead due to dynamic management.
• Flexibility: High; elements can be inserted, added, or removed effortlessly.
• Best used when: The total number of items changes frequently or is unknown beforehand (e.g., players joining an online lobby, items in a shopping basket).
Quick Review and Revision Summary
1. Data Structure: A specialized format for organizing, storing, and managing data efficiently.
2. Static vs Dynamic: Static structures have a fixed size (e.g., standard arrays); dynamic structures grow/shrink at runtime (e.g., Lists).
3. Zero-Based Indexing: Indices always start at \(0\) and end at \(\text{Length} - 1\).
4. 2D Arrays: Accessed using [row, column] indices; traversed using nested loops.
5. Dynamic Lists: Provide flexible sizing and built-in methods like Add, Insert, and Remove to manage variable amounts of data.