Data Structures
Arrays, linked lists, stacks, queues, and trees
A data structure organises data in memory for efficient use.
Arrays: Fixed-size, ordered, same data type, **contiguous** memory. Access any element by **index** — O(1) **random access**. Downside: fixed size, slow insert/delete.
Linked Lists: Each **node** stores data + a **pointer** to the next node. Dynamic size, easy insert/delete. But finding element 50 requires following 49 pointers — **sequential access**, O(n).
Stacks: **LIFO** (Last In, First Out). **Push** (add to top), **Pop** (remove from top). Used in undo features and function calls.
Queues: **FIFO** (First In, First Out). **Enqueue** (add to rear), **Dequeue** (remove from front). Used in print queues, scheduling.
Binary Search Trees: Each node has max 2 children. Left child smaller, right child larger. Traversals: **Pre-order** (Root→Left→Right), **In-order** (Left→Root→Right — gives sorted output), **Post-order** (Left→Right→Root).
Key Points to Remember
- 1Arrays: fixed size, random access
- 2Linked lists: dynamic size, sequential access
- 3Stacks: LIFO, Queues: FIFO
- 4Binary trees and traversal
Pakistan Example
Queue at Saddar Bus Stop vs Stack of Bun Kebabs
A queue at Karachi's Saddar bus stop is FIFO — first passenger boards first. A cook stacking bun kebabs on a plate is LIFO — last kebab placed is first taken. Bykea uses queues internally to assign drivers to the longest-waiting passenger.