What is a data structure?
A data structure is a way to store and organise data so that we can use it well: find it, add to it, remove from it, sort it.
- Primitive data types hold one value: integer, float, character, Boolean.
- Non-primitive data structures hold many values: arrays, lists, stacks, queues, trees, graphs.
- Linear structures keep items in a sequence (array, list, stack, queue). Non-linear structures branch (tree, graph).
- Static structures have a fixed size (a classic array). Dynamic structures grow and shrink while the program runs (linked list, Python list).
An abstract data type (ADT) describes what a structure does (its operations) without saying how it is built. A stack ADT promises push, pop, peek and isEmpty; it could be built from an array or a linked list.
Arrays, records, tuples and lists
An array stores items of the same type in neighbouring memory boxes. Each box has an index, usually starting at 0. Because the boxes are side by side, the computer can jump to A[i] in one step. But inserting in the middle means sliding every later item along.
A 2D array is a grid, like a table or a chessboard: M[row][col]. A string is an array of characters.
A record groups different kinds of data about one thing, such as a student: name (text), roll number (integer), marks (float). Each part is a field. A file stores many records permanently on disk.
In Python, a list [3, 8, 5] is a dynamic array that can grow; a tuple (3, 8, 5) cannot be changed after it is made.
A linked list is a chain of nodes. Each node stores a value and a pointer to the next node; the last points to null. The first node is the head. Inserting or deleting only changes pointers, so nothing slides; but to reach the 100th item you must walk through 99 nodes.
Stacks and queues
A stack is LIFO: last in, first out. You only touch the top.
push(x)adds x on top;pop()removes and returns the top;peek()looks at the top without removing it.- Popping an empty stack is underflow; pushing onto a full fixed-size stack is overflow.
- Uses: undo, the back button, checking brackets, and the call stack that remembers which function to return to.
Reverse Polish notation (RPN) writes the operator after its numbers: 3 4 + means 3 + 4. A stack evaluates it: push numbers; on an operator, pop two, calculate, push the result. RPN needs no brackets.
A queue is FIFO: first in, first out. Items join at the rear (enqueue) and leave from the front (dequeue). Uses: printer jobs, keyboard buffers, customer service lines, tasks waiting for the CPU. A circular queue reuses empty spaces at the start of a fixed array, and a priority queue lets urgent items go first.
Dictionaries, trees and graphs
A dictionary (map, hash table) stores key → value pairs, like {"Asha": 9876, "Ravi": 9123}. You find a value by its key, not by position. A hash function turns the key into a box number, so look-up is very fast.
A tree stores data in levels. The top node is the root; nodes below are children; nodes with no children are leaves. In a binary tree each node has at most two children.
In a binary search tree (BST), every value in the left subtree is smaller than the node and every value in the right subtree is bigger. To search, compare and go left or right; each step throws away about half of what is left, so even a million well-balanced items need only about 20 comparisons.
A graph is a set of vertices joined by edges, with no fixed top. Maps, social networks and the internet are graphs.
Choosing a structure: need instant access by position → array; lots of inserting in the middle → linked list; undo or reverse → stack; fair waiting line → queue; look-up by name → dictionary; fast sorted search → BST.
Key formulas and definitions
- Array: A[i] reached directly; first index = 0, last index = n − 1
- Address of A[i] = base address + i × (size of one item)
- Stack (LIFO): push, pop, peek, isEmpty; underflow = pop when empty
- Queue (FIFO): enqueue at rear, dequeue at front
- BST rule: left < node < right
- RPN: on a number push; on an operator pop two, compute, push the answer
Worked examples
1. A = [12, 7, 30, 45, 9, 18]. What is A[3], and what is the last index?
Indexes start at 0, so A[3] = 45. There are 6 items, so the last index is 6 − 1 = 5.
2. Start with an empty stack. push(4), push(9), push(2), pop(), push(7), pop(), pop(). What is left, and what was popped in order?
After pushes: [4, 9, 2]. pop → 2. push 7 → [4, 9, 7]. pop → 7. pop → 9. Left: [4]. Popped in order: 2, 7, 9.
3. Empty queue. enqueue(4), enqueue(9), enqueue(2), dequeue(), enqueue(7), dequeue(). What is left?
[4, 9, 2] → dequeue removes 4 → [9, 2] → enqueue 7 → [9, 2, 7] → dequeue removes 9 → [2, 7].
4. Evaluate the RPN expression 5 3 + 2 × using a stack.
push 5, push 3 → '+' pops 3 and 5, pushes 8 → push 2 → '×' pops 2 and 8, pushes 16. Answer: 16 (same as (5 + 3) × 2).
5. Insert 35 into the BST with root 50, left child 30 (children 20, 40) and right child 70. Where does it go?
35 < 50 → go left to 30. 35 > 30 → go right to 40. 35 < 40 → it becomes the left child of 40.
6. An integer array starts at memory address 1000 and each integer takes 4 bytes. Where is A[5]?
Address = 1000 + 5 × 4 = 1020.
Common mistakes
- Starting array indexes at 1. In most languages the first index is 0, so the last is n − 1.
- Mixing up LIFO and FIFO. Stack = last in first out; queue = first in first out.
- Thinking a linked list gives instant access like an array. You must walk node by node from the head.
- In RPN, popping the numbers in the wrong order for − and ÷. The first number popped is the right-hand operand: '8 2 −' is 8 − 2 = 6.