Implementing Stacks, Queues, Lists, Trees & Hash Tables in Python
GATE 2027 DA core: stacks, queues, linked lists, trees, hash tables
“Connect abstract data-structure operations to Python representations and their costs.”
1.Prerequisites and abstract operations
§ 1.1.Prerequisites: Python lists, dictionaries, loops, and functions. For the abstract definitions and structural proofs, see [Data Structures](/notes/data-structures/linear-data-structures) and [Trees](/notes/data-structures/trees-and-bst).
An abstract data type specifies behavior; an implementation chooses a representation. A Python list behaves well as a stack when both push and pop use its end. A deque behaves as a queue. A linked list uses nodes that point to their successors. A binary tree node stores a value and up to two child references. Python dictionaries implement hash-based mappings; they are the natural built-in hash table for many programming tasks.
The operation requested determines the cost. A list's random indexing is O(1), but insertion at its front shifts elements. A linked list can prepend in O(1) but requires O(n) traversal to find a target. A tree traversal touches each node once; balanced search-tree guarantees do not automatically apply to an arbitrary Python object graph.
Worked example: queue semantics
The queue order is [A, B, C].
A leaves; the remaining order is [B, C].
Append D at the rear: [B, C, D].
Representation checks
Which operation is O(n) on a Python list of n elements?
A binary tree traversal visits every node once. What is its time complexity for n nodes?
One-minute revision
“State the representation and supported operations before giving a data-structure complexity.”
- •Array/list indexing O(1); front insertion/deletion O(n)
- •Linked-list search O(n), head insertion O(1)
- •Tree traversal O(n)
- •Hash lookup expected O(1), worst case can differ
- •List versus linked list
- •Stack versus queue order
- •Unbalanced tree guarantees
- •Expected versus worst-case hash cost
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Visual thinkers who want to see each algorithm step animated clearly.
GATE-targeted coverage with step-by-step GATE PYQ walkthroughs.