Computer Science · Topic 05

Data Structures

Discover how computers organize information so programs can store, retrieve, update, and process data efficiently.

1. What Is a Data Structure?

A data structure is a way of organizing and storing data so that operations on it can be performed effectively.

Imagine a library. Books could be stored randomly, or they could be arranged by category, author, and title. A good arrangement makes finding a particular book easier.

Programs face a similar problem: choosing an appropriate way to organize information.

Common operations

Access: Read a particular item.
Search: Find an item with a given value.
Insertion: Add a new item.
Deletion: Remove an item.
Update: Change an existing value.
Traversal: Visit items systematically.

No single data structure is best for every task. The right choice depends on how the data will be used.

2. Linear and Non-Linear Structures

Data structures are often grouped by how their elements relate to one another.

Linear structures Elements are arranged in a sequence. Examples include arrays, linked lists, stacks, and queues.

Non-linear structures Elements can form hierarchical or network-like relationships. Examples include trees and graphs.

3. Arrays

An array stores elements in an ordered collection. In many programming languages, array elements are accessed using an index.

scores = [72, 85, 91, 68]

scores[0] = 72
scores[1] = 85
scores[2] = 91
scores[3] = 68

This example uses zero-based indexing, meaning the first element has index 0. Some languages and data structures use different indexing rules.

Advantages

Direct access by index is typically fast.
Elements are easy to process using loops.
Arrays are useful for storing collections such as marks or temperatures.

Limitations

In a conventional fixed-size array, capacity is determined when it is created.
Inserting or removing an element in the middle may require shifting other elements.

Many languages also provide dynamic arrays or lists that can grow as needed, though resizing may occasionally require extra work.

4. Linked Lists

A linked list consists of nodes. Each node stores data and a link to another node. In a singly linked list, each node points to the next node.

[10 | next] → [20 | next] → [30 | null]

The last node points to null, indicating that there is no next node in this simple example.

Advantages

Nodes can be added or removed without shifting an entire sequence.
The structure can grow or shrink as nodes are allocated and released.

Limitations

Accessing a particular position generally requires following links from the beginning.
Links require additional memory.

5. Stacks

A stack follows the LIFO rule: Last In, First Out. The most recently added element is the first one removed.

A stack of plates is a familiar analogy: the plate placed on top is usually removed first.

Push(10)
Push(20)
Push(30)

Pop() → 30
Pop() → 20

Core operations

Push: Add an item to the top.
Pop: Remove and return the top item.
Peek / Top: Inspect the top item without removing it.

Applications

Undo and redo features.
Tracking function calls.
Checking balanced brackets in expressions.
Backtracking algorithms.

6. Queues

A queue usually follows the FIFO rule: First In, First Out. The earliest item added is the earliest one removed.

A queue at a ticket counter illustrates this principle.

Enqueue(10)
Enqueue(20)
Enqueue(30)

Dequeue() → 10
Dequeue() → 20

Core operations

Enqueue: Add an item at the rear.
Dequeue: Remove an item from the front.
Front / Peek: Inspect the next item to be removed.

Applications

Managing print jobs.
Scheduling tasks.
Processing requests in arrival order.
Breadth-first search in graphs.

7. Trees

A tree is a hierarchical data structure made of nodes connected by edges. A rooted tree has a designated root node.

Root: The starting node of a rooted tree.
Parent: A node directly above another node.
Child: A node directly below another node.
Leaf: A node with no children.
Subtree: A node together with its descendants.

Binary trees

A binary tree is a tree in which each node has at most two children. A binary search tree is a particular kind of binary tree organized to support searching.

Applications

Representing folders and directories.
Organizing searchable data.
Representing expressions and decision processes.

8. Graphs

A graph consists of vertices (also called nodes) and edges that connect them. Graphs can represent relationships between objects.

A ─── B
|   / |
|  /  |
C ─── D

This is a conceptual illustration of a network, not a specific graph layout.

Types of graphs

Undirected graph: Edges have no direction.
Directed graph: Edges have a direction.
Weighted graph: Edges carry values such as distance or cost.

Applications

Road and navigation networks.
Social networks.
Connections between web pages.
Communication and computer networks.

9. Hash Tables

A hash table stores key-value pairs. A hash function helps determine where a key's data should be stored.

"name"  → "Asha"
"score" → 95
"city"  → "Delhi"

A program can use a key such as "score" to retrieve its associated value, 95.

Important concepts

Key: Identifies the item to look up.
Hash function: Maps a key to a hash value used to locate storage.
Collision: Occurs when different keys map to the same location.

Hash tables are often very fast for lookups on average, but their performance depends on the hash function, collision handling, and table design.

10. Choosing the Right Data Structure

Structure	Useful when
Array	You need an ordered collection with quick indexed access.
Linked list	You need linked nodes and frequent insertions or removals at known positions.
Stack	The most recently added item should be handled first.
Queue	Items should generally be handled in arrival order.
Tree	You need hierarchical relationships or structured searching.
Graph	You need to represent general relationships or networks.
Hash table	You need efficient average-case lookup by key.

These are general guidelines, not absolute rules. Real performance depends on the specific implementation and operations your program needs.

11. Knowledge Check

Try to answer each question before revealing the answer.

1. Which data structure follows LIFO?

A stack: Last In, First Out.

2. Which data structure normally follows FIFO?

A queue: First In, First Out.

3. What is a leaf node in a tree?

A node that has no children.

4. What are the two main components of a graph?

Vertices (nodes) and edges (connections).

5. What does a hash table store?

Data organized around keys, commonly as key-value pairs.

6. Which structure is commonly used for undo operations?

A stack is a common choice because the most recent action is usually undone first.

Key Takeaways

Data structures organize information for efficient use.
Arrays and linked lists organize elements in sequences.
Stacks use LIFO, while queues typically use FIFO.
Trees represent hierarchies; graphs represent general networks.
Hash tables support lookup using keys.
The best structure depends on the task and required operations.