Data Structures Explained: Arrays, Lists, and More for H2 Computing

Data structures are fundamental to H2 Computing (Syllabus 9569). This comprehensive guide explains key data structures including arrays, lists, stacks, queues, and trees for A-Level students in Singapore.

What are Data Structures?

Data structures are ways of organizing and storing data in a computer so that it can be accessed and used efficiently.

Key Concepts:

Organization of data
Efficient access and modification
Relationship between data items
Storage and retrieval methods
Performance characteristics

Why They Matter:

Essential for programming
Enable efficient algorithms
Important for H2 Computing exams
Used in real-world applications

Arrays

What is an Array?

An array is a collection of elements stored in contiguous memory locations, accessed by index.

Characteristics:

Fixed size (usually)
Indexed access (0-based or 1-based)
Contiguous memory
Fast access by index
Simple structure

Operations:

Access by index: O(1)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

Use Cases:

Storing lists of items
When size is known
When random access is needed
Simple data storage

Example:

Array: [10, 20, 30, 40, 50]
Index:  0   1   2   3   4
Access: array[2] = 30

Linked Lists

What is a Linked List?

A linked list is a collection of nodes where each node contains data and a reference to the next node.

Characteristics:

Dynamic size
Non-contiguous memory
Sequential access
Flexible structure
Memory efficient

Types:

Singly linked list
Doubly linked list
Circular linked list

Operations:

Access: O(n)
Search: O(n)
Insertion: O(1) at beginning, O(n) elsewhere
Deletion: O(1) at beginning, O(n) elsewhere

Use Cases:

When size is unknown
Frequent insertions/deletions
Dynamic data storage
Memory efficiency needed

Example:

Singly Linked List:
[Data: 10] -> [Data: 20] -> [Data: 30] -> NULL

Stacks

What is a Stack?

A stack is a linear data structure that follows Last-In-First-Out (LIFO) principle.

Characteristics:

LIFO principle
Two main operations: push and pop
Top element access
Simple structure
Efficient operations

Operations:

Push (add): O(1)
Pop (remove): O(1)
Peek (view top): O(1)
Search: O(n)

Use Cases:

Function call management
Expression evaluation
Undo operations
Backtracking algorithms

Example:

Stack Operations:
Push 10 -> [10]
Push 20 -> [20, 10]
Push 30 -> [30, 20, 10]
Pop -> [20, 10] (returns 30)

Queues

What is a Queue?

A queue is a linear data structure that follows First-In-First-Out (FIFO) principle.

Characteristics:

FIFO principle
Two main operations: enqueue and dequeue
Front and rear pointers
Simple structure
Efficient operations

Operations:

Enqueue (add): O(1)
Dequeue (remove): O(1)
Front (view): O(1)
Search: O(n)

Use Cases:

Task scheduling
Print queue management
Breadth-first search
Request processing

Example:

Queue Operations:
Enqueue 10 -> [10]
Enqueue 20 -> [10, 20]
Enqueue 30 -> [10, 20, 30]
Dequeue -> [20, 30] (returns 10)

Trees

What is a Tree?

A tree is a hierarchical data structure with nodes connected by edges, with one root node.

Characteristics:

Hierarchical structure
Root node
Parent-child relationships
Leaf nodes
Efficient search

Types:

Binary tree
Binary search tree (BST)
AVL tree
General tree

Operations:

Search: O(log n) for BST, O(n) for general
Insertion: O(log n) for BST, O(n) for general
Deletion: O(log n) for BST, O(n) for general
Traversal: O(n)

Use Cases:

Hierarchical data representation
Efficient searching
Expression trees
Decision trees

Example:

Binary Search Tree:
        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

Choosing the Right Data Structure

Factors to Consider

Access Pattern:

Random access: Arrays
Sequential access: Linked lists
LIFO: Stacks
FIFO: Queues

Size Requirements:

Fixed size: Arrays
Dynamic size: Linked lists, trees

Operation Frequency:

Frequent insertions/deletions: Linked lists
Frequent searches: Trees (BST)
Simple operations: Stacks, queues

Memory Constraints:

Limited memory: Arrays
Flexible memory: Linked lists

Complexity Analysis

Time Complexity Comparison

Access:

Array: O(1)
Linked list: O(n)
Stack/Queue: O(1) for top/front
Tree: O(log n) for BST, O(n) for general

Search:

Array: O(n)
Linked list: O(n)
Stack/Queue: O(n)
Tree: O(log n) for BST, O(n) for general

Insertion:

Array: O(n)
Linked list: O(1) at beginning, O(n) elsewhere
Stack/Queue: O(1)
Tree: O(log n) for BST, O(n) for general

Common Operations

Array Operations

Access:

array[index] = value
value = array[index]

Traversal:

FOR i = 0 TO length(array) - 1
    PROCESS array[i]
END FOR

Linked List Operations

Insertion at Beginning:

newNode.next = head
head = newNode

Traversal:

current = head
WHILE current != NULL
    PROCESS current.data
    current = current.next
END WHILE

Stack Operations

Push:

top = top + 1
stack[top] = value

Pop:

value = stack[top]
top = top - 1
RETURN value

Queue Operations

Enqueue:

queue[rear] = value
rear = rear + 1

Dequeue:

value = queue[front]
front = front + 1
RETURN value

Practice Exercises

Exercise 1: Array Operations

Implement basic array operations: access, search, insertion, deletion.

Exercise 2: Linked List Implementation

Implement a singly linked list with insertion, deletion, and traversal.

Exercise 3: Stack Application

Use a stack to check if parentheses are balanced in an expression.

Exercise 4: Queue Application

Implement a queue for task scheduling.

How We Help at Atlas Academy

At Atlas Academy in Bukit Timah, Singapore, we teach data structures effectively:

Our Approach:

Clear Explanations - Step-by-step data structure teaching
Practical Examples - Real-world data structure applications
Implementation Practice - Hands-on data structure coding
Exam Focus - Data structure questions for H2 Computing

Benefits:

Strong data structure foundation
Improved programming skills
Better exam performance
Enhanced computing abilities

Frequently Asked Questions

What's the difference between an array and a linked list?

Arrays use contiguous memory and fixed size, while linked lists use non-contiguous memory and dynamic size.

When should I use a stack vs a queue?

Use a stack for LIFO operations (like undo), and a queue for FIFO operations (like task scheduling).

How do I choose the right data structure?

Consider access patterns, size requirements, operation frequency, and memory constraints.

Are data structures only for H2 Computing?

Data structures are important for H2 Computing, but understanding them helps in all programming.

How important are data structures for H2 Computing exams?

Very important. Data structures are fundamental to H2 Computing and appear in both papers.

Conclusion

Data structures are essential for H2 Computing and programming in general. Understanding different data structures, their characteristics, and when to use them will help you excel in H2 Computing exams and programming.

Remember, data structure knowledge improves with practice. Study each structure, implement them, and practice using them in various scenarios to build strong data structure skills.

For expert data structure instruction and practice, consider joining our classes at Atlas Academy in Bukit Timah, Singapore.

Need help with data structures? Contact us to learn more about our H2 Computing classes and data structure instruction.

Concept Guides