Data Structures: Definitions, Types, Operations & Real-World Use

What is a Data Structure?

A data structure is a way of organizing, storing, and accessing data efficiently in a computer program. It defines how data is laid out in memory and how operations (like searching or sorting) are performed on it.

Why Do We Need Data Structures?

• Efficiency: Different structures optimize for time/space (e.g., arrays for fast access, trees for hierarchical data).
• Abstraction: Hide implementation details (e.g., a queue abstracts FIFO order).
• Problem-Solving: Match the structure to the problem (e.g., graphs for routes, stacks for undo operations).

---

Types of Data Structures

Data structures are classified into two broad categories:

1. Primitive (Basic) Data Structures

Stores single values (no sub-structures). Examples:

• Integer: Stores whole numbers (e.g., int age = 25;).
• Float/Double: Stores decimals (e.g., float price = 12.99;).
• Character: Stores single letters/symbols (e.g., char grade = 'A';).

2. Non-Primitive (Compound) Data Structures

Combine multiple data items. Divided into:

A. Linear Data Structures

Elements are arranged sequentially. Examples:

• Array: Fixed-size, contiguous memory.
• Linked List: Dynamic-size, nodes with pointers.
• Stack: LIFO (Last-In-First-Out) order.
• Queue: FIFO (First-In-First-Out) order.

B. Non-Linear Data Structures

Elements are not sequential. Examples:

• Tree: Hierarchical (e.g., file systems, organization charts).
• Graph: Nodes connected by edges (e.g., social networks, maps).
• Hash Table: Key-value pairs for O(1) access.

---

Key Operations on Data Structures

All data structures support these core operations (time complexity varies by structure):

---

Visualizing Data Structures

1. Array

An array is a contiguous block of memory storing elements of the same type.

Index: 0   1   2   3   4
Value: 10  20  30  40  50

Operations:

• Insertion at end: Append to arr[n] (O(1) if space exists).
• Deletion from start: Shift all elements left (O(n)).

Example: Storing Daraz order IDs in a fixed-size array:

Index: 0   1   2   3
OrderID: 1001 1002 1003 1004

---

2. Linked List

A dynamic structure where each node points to the next.

Node 1 (Data: 10) → Node 2 (Data: 20) → Node 3 (Data: 30) → NULL

Operations:

• Insertion at head: Update head pointer (O(1)).
• Deletion at tail: Traverse to last node (O(n)).

Example: Khalti transaction history (newest first):

Node 1 (Txn: 5000) → Node 2 (Txn: 3000) → Node 3 (Txn: 2000) → NULL

---

Comparison Table: Array vs. Linked List

---

In the Real World

1. eSewa (Nepal)

   • Data Structure Used: Queue
   • How? When you book an appointment, your request is added to a FIFO queue. The system processes older requests first (e.g., first-come-first-served for bill payments).
   • Visual:

     [Request 1 (User A)] → [Request 2 (User B)] → [Request 3 (User C)] → NULL
     

2. Daraz (Nepal)

   • Data Structure Used: Array + Hash Table
   • How? Product IDs are stored in an array for quick access, while user reviews use a hash table (key = product ID, value = list of reviews) for O(1) lookup.
   • Example: Searching for a product by ID (productID = 1005) uses the hash table to fetch details instantly.

3. NTC Traffic Routes (Nepal)

   • Data Structure Used: Graph
   • How? Roads are nodes, and connections are edges. The NTC uses Dijkstra’s algorithm (a graph algorithm) to find the fastest route between two cities, avoiding traffic jams.
   • Visual:

 ```
 Kathmandu --(60km)--> Bhaktapur --(40km)--> Dhulikhel
                 |                     |
                30km                 50km
                 |                     |
                Dharan --(120km)--> Pokhara
 ```

---

Worked Example: Storing NEPSE Stock Prices

Problem: Store daily closing prices of NEPSE shares for the last 7 days. Which data structure is better: array or linked list?

Solution:

1. Array Choice:

   • Fixed size (7 days), random access needed (e.g., "What was the price on Day 3?").
   • Implementation:

     float prices[7] = {1200.5, 1202.3, 1198.7, 1210.1, 1205.0, 1199.8, 1203.2};
     

   • Access Day 3:

     printf("Day 3 price: %.2f", prices[2]); // Output: 1198.70
     

2. Linked List Choice:

   • If prices arrive dynamically (e.g., real-time updates), a linked list allows easy insertion at the end (newest price).
   • Implementation:

     struct Node {
         float price;
         struct Node* next;
     };
     

   • Insertion:

 ```
 Before: NULL ← [1200.5] ← [1202.3] ← NULL
 After:  NULL ← [1200.5] ← [1202.3] ← [1198.7] ← NULL
 ```

Trace for Array Insertion (Day 8):

---

Advantages and Disadvantages

---

Exam Tip

1. Definitions Matter: Always define data structures clearly (e.g., "A stack is a LIFO structure with push/pop operations").
2. Visuals = Marks: Draw diagrams for:
   • Array/linked list operations (insertion/deletion).
   • Stack/queue states after each operation.
   • Graphs for real-world examples (e.g., NTC routes).
3. Time Complexity: Memorize O(1), O(n), O(n²) for operations (e.g., array access is O(1), linked list search is O(n)).
4. Real-World Links: Examiners love connections to apps (e.g., "How would you implement a browser’s back button using a stack?").
5. Pseudocode: Write short traces (like the NEPSE example) to show understanding of step-by-step execution.

---

Key Formula to Remember: For an array of size n:

• Access time: $O(1)$
• Insertion at end: $O(1)$ (if space exists), else $O(n)$ (for resizing).
• Deletion at start: $O(n)$ (shifting elements).