Data Structures
Arrays, stacks, queues, trees, graphs
Data structures organise data so that the operations a program needs can be performed clearly and efficiently. The right choice depends on access pattern, ordering, updates, memory and whether relationships are linear or hierarchical. Technical aptitude questions usually test the structure's invariant and the cost of its common operations, not memorisation in isolation.
Key formulas and rules
Key concepts
Arrays and dynamic arrays
An array stores elements in indexed positions, often in contiguous memory. Direct access by index is fast because the address can be calculated from the base address and element size. Inserting or deleting near the beginning usually shifts later elements. A dynamic array grows by allocating a larger block and copying elements, so append is often amortized O(1) even though a resize itself costs O(n).
Linked lists
A linked list stores nodes connected by links rather than requiring adjacent memory. Inserting at a known head or after a known node can be constant time, but finding a position or accessing the kth item requires traversal. A doubly linked list stores both next and previous links, using more memory to support backward traversal and easier deletion when the node is known.
Stacks, queues and deques
A stack follows LIFO: the last item pushed is the first item popped. It suits undo history and function-call management. A queue follows FIFO: the first item enqueued is the first item dequeued. It suits scheduling and breadth-first search. A deque supports insertion and removal at both ends. Circular queues reuse freed positions instead of shifting every remaining item.
Trees and binary search trees
A tree represents hierarchical relationships with a root and child nodes. A binary tree has at most two children per node. In a binary search tree, values in the left subtree are smaller and values in the right subtree are larger according to the chosen ordering. Inorder traversal of a valid BST visits keys in sorted order, but a badly skewed BST loses the expected logarithmic performance.
Heaps and priority queues
A heap is a complete tree commonly stored in an array. In a min-heap, each parent is no greater than its children, so the minimum is at the root. Insertion and removal of the root are O(log n), while reading the root is O(1). A priority queue uses this ordering to repeatedly process the most or least important item.
Hash tables and collision handling
A hash table maps a key to a bucket using a hash function. Equal keys must be treated consistently, and a collision occurs when different keys select the same bucket. Chaining stores several entries in a bucket structure such as a linked list; open addressing searches for another slot. Load factor and hash distribution affect performance, so O(1) is an average-case expectation, not a universal guarantee.
Graphs and representations
A graph contains vertices connected by edges, which may be directed, undirected, weighted or unweighted. An adjacency matrix gives O(1) edge-existence checks but uses O(V²) space. An adjacency list uses space proportional to vertices and edges and is efficient for sparse graphs. BFS uses a queue, while DFS uses a stack or recursion.
Worked examples
Example 1
You need to read the 500th item repeatedly by position, but insertions at the front are rare. Which structure is usually the better fit: an array or a singly linked list?
Step 1: Repeated indexed reads favour direct address calculation.
Step 2: An array commonly accesses an item by index in O(1).
Step 3: A singly linked list must follow links from the head, making indexed access O(n).
Step 4: Rare front insertions do not outweigh the dominant access pattern.
Answer: An array is usually the better fit.
Example 2
A text editor must undo the most recent action first. Which data structure matches this requirement, and why?
Step 1: The most recent action must be removed before older actions.
Step 2: This is a last-in, first-out requirement.
Step 3: A stack provides LIFO behavior through push and pop.
Answer: Use a stack; push each action and pop the latest action when undo is requested.
Example 3
A circular queue has capacity 5, front at index 3 and rear at index 4. The rear slot is occupied, but indices 0 and 1 have been freed by earlier dequeues. What should enqueue do?
Step 1: A circular queue treats the array as wrapping from the last index back to index 0.
Step 2: The next rear position is (4 + 1) mod 5 = 0.
Step 3: Because index 0 is free, the new item is placed there instead of shifting existing items.
Answer: Enqueue at index 0 and update the rear position.
Example 4
Insert 40, 20, 60, 10 and 30 into a binary search tree. Where is the smallest key, and what does inorder traversal produce?
Step 1: 20 becomes the left child of 40; 60 becomes the right child.
Step 2: 10 is placed left of 20, and 30 is placed right of 20.
Step 3: The leftmost node is 10, so it is the smallest key.
Step 4: Inorder traversal visits left subtree, root and right subtree, producing 10, 20, 30, 40, 60.
Answer: Smallest key = 10; inorder traversal = 10, 20, 30, 40, 60.
Example 5
A min-heap contains [3, 7, 9, 12, 15]. Which item is removed by extract-min, and what is the usual time complexity of the removal?
Step 1: The min-heap property keeps the smallest key at the root, index 0.
Step 2: Extract-min removes 3.
Step 3: The last element is moved to the root and the heap is restored by moving it downward.
Step 4: The height of a complete heap is O(log n), so restoration takes O(log n).
Answer: Remove 3; extract-min is O(log n).
Example 6
A hash table has 10 buckets and stores 7 keys. What is its load factor, and what happens if two different keys hash to the same bucket when chaining is used?
Representative solved questions
See the kind of question in this topic before opening the full practice set.
Question 1
What is the time complexity of accessing an element in an array by index?
O(1)
O(n)
O(log n)
O(n^2)
Answer: A. O(1)
ExplanationStep 1: Arrays provide random access to elements.
Step 2: The memory address of any element can be calculated directly using: base_address + (index x element_size).
Step 3: This calculation takes constant time regardless of array size.
Answer: O(1)
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Question 2
Which data structure follows the LIFO (Last In, First Out) principle?
Queue
Stack
Linked List
Array
Answer: B. Stack
ExplanationStep 1: LIFO means the last element added is the first one removed.
Step 2: Stack operations: push adds to top, pop removes from top.
Step 3: Queue is FIFO, Linked List and Array are general structures without enforced access patterns.
Answer: Stack
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Question 3
What is the time complexity of inserting at the beginning of a singly linked list?
O(1)
O(n)
O(log n)
O(n^2)
Answer: A. O(1)
ExplanationStep 1: To insert at the beginning, we only need to modify the head pointer.
Step 2: Create new node, set its next to current head, update head to new node.
Step 3: These are 3 pointer operations independent of list size.
Answer: O(1)
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Common mistakes and useful habits
- Start with the required operation: indexed access, insertion, deletion, ordering, membership or priority retrieval.
- Remember the invariants: stack is LIFO, queue is FIFO, BST left is smaller and a min-heap keeps the minimum at the root.
- Do not quote O(1) without its condition. Hash tables are average-case, dynamic-array append is amortized, and linked-list insertion is constant only when the position is known.
- For trees, distinguish height measured in edges from the number of levels and check whether the tree is balanced.
- For graph questions, identify directedness, weights and density before choosing a representation or traversal.
- Draw a small structure for pointer and tree questions. A diagram often reveals the operation more reliably than mental tracing.
- Compare time and space together. A faster lookup may require extra memory, while a compact representation may require more traversal.
Sources and review notes
Reviewed by AISEA Editorial Desk on 1 Sep 2026.
- Array, linked-list, stack, queue, tree, heap, hash-table and graph definitions were checked for operation-specific conditions.
- Worked examples were recalculated for index access, circular-queue wraparound, BST traversal, heap removal, load factor and sparse graphs.
- Complexity claims are qualified by assumptions such as balance, known position, amortization, density and hash distribution.
- Data StructuresPython Documentation · Checked 1 Sep 2026Supports: list, set, dictionary and collection behavior as concrete data-structure examples
- Introduction to CollectionsOracle Java Tutorials · Checked 1 Sep 2026Supports: collection interfaces, implementations, reusable data structures and algorithms
- Open Data StructuresPat Morin · Checked 1 Sep 2026Supports: array-based lists, linked lists, hash tables, trees and graph data structures
Ready to test your understanding?
Work through 186 questions with explanations after each answer.