Data structures: practice questions with explanations

1What a data structure is

A data structure is a way to organise data in memory so that certain operations are fast: finding an item, adding one, removing one.

No structure is fast at everything. Choosing one means choosing which operations should be cheap. Their costs are written in Big O, with n the number of items.

The two basic building blocks are the array and the linked list.

An array stores its items in one block of memory, one after another. The computer can calculate where item i is, so reading a[i] takes O(1). Inserting at the front means shifting every item: O(n).

A linked list stores each item in a node with a pointer to the next node. The last pointer is null. Inserting at the head (h) only changes one pointer: O(1). But to reach item i you must follow i pointers: O(n).

A doubly linked list also has a pointer to the previous node, so you can walk both ways.

2Stacks and queues

A stack is like a pile of plates: you add and remove only at the top. The last item in is the first item out: LIFO.

• push puts an item on top, pop removes the top item, peek reads the top without removing it. All are O(1).
• Uses: the undo function of an editor, the call stack of a program, checking that brackets are balanced, depth-first search.

A queue is like a line at a till: you join at the back and leave at the front. The first item in is the first item out: FIFO.

• enqueue adds at the back, dequeue removes from the front. Both are O(1).
• Uses: print jobs, messages waiting to be handled, breadth-first search.

A deque (double-ended queue) allows adding and removing at both ends. A priority queue always removes the item with the highest priority first; it is usually built as a heap.

3Trees, heaps, hash tables and graphs

A tree has one top node, the root. Every other node has exactly one parent. Nodes without children are leaves. A tree with n nodes has n − 1 edges.

In a binary tree every node has at most two children. A binary search tree (BST) adds a rule: keys in the left subtree are smaller than the node, keys in the right subtree are larger.

Searching a BST follows one path down, so it costs O(height). A balanced tree (AVL, red-black) keeps the height near log₂ n. Keys inserted in sorted order make a chain of height n.

A heap is a binary tree where every parent is smaller than its children (min-heap) or larger (max-heap). The minimum or maximum is at the root, and insert and remove cost O(log n).

A hash table stores key–value pairs. A hash function turns the key into an index, so insert and lookup take O(1) on average. Two keys with the same index are a collision, solved by chaining (a list per slot) or open addressing (try another slot).

A graph has vertices joined by edges, which may have a direction or a weight. It is stored as an adjacency matrix, O(V²) memory, or as adjacency lists, O(V + E).

4The method step by step

Questions often describe a task and ask which structure fits, or ask what a structure looks like after some operations.

1. Find the operation that must be fast: access by position, by key, the newest item, the oldest item, the smallest item, or a range.
2. Match it to a structure: index → array, key → hash table, newest → stack, oldest → queue, smallest or largest → heap, sorted order or ranges → balanced search tree.
3. Check the cost of the other operations the task needs, in Big O.
4. For a trace question, carry out the operations one at a time and write down the state after each one.
5. Check the final state against the rule of the structure: LIFO, FIFO, the BST order or the heap order.

5A worked example

Follow every step. Try to predict the next one before you open it.

6Common mistakes

• Mixing up LIFO and FIFO. A stack returns the newest item, a queue the oldest.
• Thinking a linked list gives fast access by index. It must walk from the head.
• Assuming a BST is always O(log n). Only a balanced tree is; sorted inserts give O(n).
• Forgetting collisions in a hash table. O(1) is the average, not the worst case.
• Mixing up the traversals. Preorder: node first. In-order: node in the middle. Postorder: node last.
• Using an adjacency matrix for a large sparse graph. It wastes O(V²) memory.

7How exam questions look

• Easy: key terms and facts. LIFO and FIFO, what a node, root or leaf is, the BST rule, what a hash function does.
• Medium: applying the concepts. Which structure fits a task, the result of push and pop or of BST inserts, tree traversals, a hash table with linear probing, costs in Big O.
• Hard: cases and analysis. Balanced trees, heaps in arrays, B-trees, tries, union-find, Bloom filters and designs such as an LRU cache.

For a heap stored in an array from index 0, the children of index i are at 2i + 1 and 2i + 2, and its parent is at ⌊(i − 1) / 2⌋.