Data-structure recap

ACompressed recap

🧾

Arrays: O(1) index, n − k shifts to insert at k. Singly linked lists: constant at the front, n at the back without a tail; doubly linked with tail: constant delete. Stacks and queues: constant operations (queue needs a tail pointer or circular array). Binary trees: ≤ 2ʰ⁺¹ − 1 nodes, height ≥ ⌊log n⌋; BST operations O(h), inorder sorted; max-heap: complete, parent ≥ children, 1-based children 2i, 2i+1, parent ⌊i/2⌋, insert/extract O(log n). Graphs: Σ deg = 2E; tree n − 1 edges; matrix Θ(V²) vs list Θ(V + E).

BMerged rule card

0.2.1 Arrays, linked lists, stacks and queues: what each operation costs

• Array: index O(1); insert/delete at k: n − k shifts; search unsorted n.
• Singly linked: front ops constant; delete needs predecessor; last node costs n.
• Doubly linked with tail: delete given node / last node constant.
• Stack push/pop and queue enqueue/dequeue (circular array or tail pointer): constant.

0.2.2 Trees, binary search trees and binary heaps: heights and operation costs

• Height h (edges): ≤ 2ⁱ nodes at level i; ≤ 2ʰ⁺¹ − 1 nodes; n nodes → h ≥ ⌊log n⌋.
• BST: left < node < right; operations O(h); inorder = sorted; sorted inserts make a chain.
• Max-heap: complete tree, parent ≥ children; 1-based children 2i, 2i+1, parent ⌊i/2⌋; leaves ⌊n/2⌋+1..n.
• Heap: max O(1); insert/extract O(log n); build O(n).

0.2.3 Graphs: vocabulary, adjacency matrix vs adjacency list

• Σ degrees = 2E (undirected); Σ in = Σ out = E (directed).
• Tree: connected, acyclic, n − 1 edges. Max edges: n(n−1)/2 undirected, n(n−1) directed.
• Matrix: Θ(V²) space, O(1) edge test. List: Θ(V + E) space, O(deg) neighbours, O(V + E) scan.

CInterleaved GATE-style questions

Q1NAT1 markArray

Deleting the first element of a 75-element array requires how many shifts?

Numerical answer: ________

Q2MCQ1 markQueue

A queue implemented with a singly linked list that keeps both head and tail pointers enqueues at the tail and dequeues at the head. Both operations take:

• (A) time proportional to n
• (B) log n time
• (C) constant time
• (D) n² time

Q3NAT2 marksHeap

Insert 5, 2, 9, 1, 7, 3 one by one into an empty max-heap. What is the element at index 2 (1-based) at the end?

Numerical answer: ________

Q4NAT1 markHeight

Minimum height (in edges) of a binary tree with 100 nodes?

Numerical answer: ________

Q5NAT2 marksBST

Keys 50, 30, 70, 20, 40, 60, 80, 10 are inserted in that order into an empty BST. Height (edges)?

Numerical answer: ________

Q6NAT1 markHandshake

An undirected graph has degrees 1, 2, 2, 3, 3, 3. How many edges?

Numerical answer: ________

Q7NAT2 marksMatrix size

How many entries of the adjacency matrix of an undirected simple graph with 8 vertices and 10 edges are 1?

Numerical answer: ________

Q8MSQ2 marksRepresentation costs

Which are true?

• (A) Checking whether (u, v) is an edge is O(1) with an adjacency matrix.
• (B) Listing the neighbours of u with an adjacency list costs O(degree of u).
• (C) Visiting every edge with an adjacency matrix costs Θ(V + E).
• (D) An adjacency list uses Θ(V + E) space.

DAnswer Vault