Data Structures with Python
Python provides four core built-in data structures, each with distinct properties that determine when to use them. GATE DA tests both the theoretical time ...
Python Data Structures: Lists, Tuples, Sets, and Dictionaries
Python provides four core built-in data structures, each with distinct properties that determine when to use them. GATE DA tests both the theoretical time complexities of operations and the practical Python syntax for working with these structures. Confusing them leads to incorrect answers on both fronts.
A list is an ordered, mutable sequence. Lists support indexing, slicing, appending, inserting, and deleting. Indexing and assignment are O(1). Appending to the end is amortized O(1) because Python over-allocates memory. Inserting or deleting at an arbitrary position is O(n) because elements must shift. Lists are implemented as dynamic arrays.
A tuple is an ordered, immutable sequence. Because tuples cannot be modified after creation, they are hashable if their elements are hashable, making them usable as dictionary keys or set members. Tuples use slightly less memory than lists. When the data represents a fixed collection such as a coordinate pair (x, y), a tuple is the semantically correct choice.
A set is an unordered collection of unique elements implemented as a hash table. Membership testing, insertion, and deletion are average O(1). Sets support union, intersection, difference, and symmetric difference operations. They are ideal when you need fast lookup and uniqueness is required.
A dictionary maps keys to values using a hash table. Key lookup, insertion, and deletion are average O(1). Since Python 3.7, dictionaries maintain insertion order. Common GATE question patterns include computing the frequency count of elements in a list using a dictionary, or checking whether two strings are anagrams by comparing character frequency dictionaries.
Worked example: given a list of n integers, find the two numbers that sum to a target value. A naive O(n^2) approach checks all pairs. An O(n) approach iterates through the list, storing each element in a set, and for each element x checks whether target - x is already in the set. This classic problem illustrates how choosing the right data structure transforms algorithmic complexity.
Stacks, Queues, Linked Lists, and Trees in Python
Stacks and queues implement restricted forms of sequence access. A stack follows last-in-first-out (LIFO) order. Push and pop operations occur at the same end. In Python, a list serves as a stack: append for push and pop() for pop, both O(1) amortized. A queue follows first-in-first-out (FIFO) order. In Python, collections.deque provides O(1) appendleft and pop operations, making it the correct implementation for queues. Using a plain list for a queue is inefficient because list.pop(0) is O(n).
Linked lists consist of nodes where each node stores a value and a reference to the next node. Python does not have a built-in linked list, but you can implement one with a Node class. Insertion and deletion at the head are O(1), but random access requires O(n) traversal. Doubly linked lists maintain both next and previous pointers, enabling O(1) deletion at any known node position.
Binary trees organize elements in a hierarchical structure. Each node has at most two children, called left and right. A binary search tree (BST) imposes the invariant that all values in the left subtree are smaller than the root, and all values in the right subtree are larger. Search, insertion, and deletion in a balanced BST are O(log n). In the worst case, an unbalanced BST degenerates to a linked list with O(n) operations.
Tree traversal orders are tested repeatedly in GATE. Inorder traversal (left, root, right) visits BST nodes in sorted ascending order. Preorder traversal (root, left, right) is used to copy or serialize a tree. Postorder traversal (left, right, root) is used to delete a tree or evaluate expression trees. Level-order traversal uses a queue to visit nodes level by level.
GATE question type: given a BST with values inserted in the order 5, 3, 7, 1, 4, write the inorder traversal sequence. The answer is 1, 3, 4, 5, 7. This tests whether you understand both insertion rules and inorder traversal in one concise question.
Graphs, Hashing, and Sorting in Python
Graphs generalize trees by allowing arbitrary connections between nodes. A graph G = (V, E) has vertices V and edges E. In Python, graphs are commonly represented as adjacency lists using dictionaries: each key is a node and its value is a list of neighbors. For dense graphs, an adjacency matrix (a 2D list or NumPy array) may be more appropriate. The choice affects both memory usage and the efficiency of graph algorithms.
Breadth-first search (BFS) explores all neighbors of a node before moving to deeper levels. It uses a queue and is implemented with collections.deque. BFS finds shortest paths in unweighted graphs. Depth-first search (DFS) explores as far as possible along one branch before backtracking. It can be implemented recursively using the call stack or iteratively using an explicit stack. DFS is used for cycle detection, topological sorting, and finding connected components.
Hashing is the mechanism behind Python's set and dict. A hash function maps a key to an integer index in an underlying array. Collisions occur when two keys map to the same index. Python uses open addressing with perturbation to resolve collisions. A well-designed hash function distributes keys uniformly. Custom objects can be made hashable by implementing __hash__ and __eq__ methods.
Sorting algorithms have well-known complexities. Bubble sort, insertion sort, and selection sort are O(n^2) in the worst case. Merge sort is O(n log n) with O(n) extra space. Quick sort is O(n log n) average and O(n^2) worst case but O(log n) space. Python's built-in sort uses Timsort, which is O(n log n) in the worst case and O(n) in the best case for nearly sorted data. Timsort is a hybrid of merge sort and insertion sort.
Worked tip: to sort a list of tuples by the second element in Python, use sorted(data, key=lambda x: x[1]). For GATE questions asking about stable sort behavior, recall that Python's sort is stable, meaning equal elements retain their original relative order, which matters when sorting by multiple keys sequentially.