Master Python Data Structures One by One: Lists, Stacks, Queues, Linked Lists, Trees, Heaps, and Graphs

List (Array)

A Python list is an ordered, mutable collection that can store elements of different types. Common operations include creation, append(), insert(), remove(), pop(), assignment, and indexing.

my_list = [1, 6, 3]
my_list.append(4)
print("my_list.append(4):", my_list)
my_list.insert(0, 5)
print("my_list.insert(0,5):", my_list)
my_list.pop(2)
print("my_list.pop(2):", my_list)
my_list.sort()
print("my_list.sort():", my_list)

Exercise – rotate an array nums = [1,2,3,4,5,6,7] by k = 3 positions using slicing:

def rotate(nums, k):
    k = k % len(nums)
    nums[:] = nums[-k:] + nums[:-k]

nums = [1,2,3,4,5,6,7]
rotate(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

The modulo operation prevents unnecessary rotations when k exceeds the list length, and the slice assignment modifies the list in‑place.

Stack

A stack follows LIFO order. In Python a list can be used as a stack with append() for push and pop() for pop.

stack = []
stack.append(1)
print(stack)          # [1]
stack.append(2)
print(stack)          # [1, 2]
stack.pop()
print(stack)          # [1]

Exercise – validate parentheses using a stack:

def is_valid(s):
    stack = []
    mapping = {')':'(','}':'{',']':'['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

print(is_valid("()[]{}"))  # True
print(is_valid("()[]}"))   # False

The algorithm pushes opening brackets, pops and checks matching for closing brackets, and finally ensures the stack is empty.

Queue

A queue follows FIFO order. The collections.deque class provides efficient enqueue ( append()) and dequeue ( popleft()) operations.

from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("Queue content:", list(queue))   # [1, 2, 3]
first = queue.popleft()
print("Dequeued element:", first)      # 1
print("Queue after dequeue:", list(queue))
print("Front element:", queue[0])
print("Rear element:", queue[-1])
print("Is empty?", not queue)
print("Length:", len(queue))
queue.clear()
print("After clearing:", list(queue))

Linked List

Python does not have a built‑in linked list, so a custom Node and LinkedList class are defined.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
    def display(self):
        cur = self.head
        while cur:
            print(cur.value, end=" -> ")
            cur = cur.next
        print("None")
    def delete(self, value):
        cur = self.head
        if cur and cur.value == value:
            self.head = cur.next
            return
        prev = None
        while cur and cur.value != value:
            prev = cur
            cur = cur.next
        if cur:
            prev.next = cur.next
    def find(self, value):
        cur = self.head
        while cur:
            if cur.value == value:
                return True
            cur = cur.next
        return False
    def length(self):
        cur = self.head
        cnt = 0
        while cur:
            cnt += 1
            cur = cur.next
        return cnt

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()          # 1 -> 2 -> 3 -> None
ll.delete(2)
ll.display()          # 1 -> 3 -> None
print("Found 3?", ll.find(3))
print("Length:", ll.length())

The methods illustrate pointer manipulation for insertion, deletion, search, and size calculation.

Binary Tree Traversal

A binary tree node stores a value and references to left and right children. Recursive traversals are demonstrated.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
preorder(root)   # 1 2 4 5 3
print()
inorder(root)    # 4 2 5 1 3
print()
postorder(root)  # 4 5 2 3 1
print()

Preorder visits root → left → right, inorder visits left → root → right, and postorder visits left → right → root.

Recursion and Call Stack

The classic factorial example shows the base case ( n == 0) and the recursive step ( n * factorial(n-1)). Each call pushes a new frame onto the call stack; returning unwinds the stack.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

print(factorial(4))  # 24

Graph Representation

Graphs are represented as adjacency lists (a dictionary where each key is a vertex and the value is a list of neighbours).

# Undirected graph example
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

Depth‑First Search (DFS) uses recursion and a visited set to explore as deep as possible before backtracking.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Example call
dfs(graph, 'A')  # Possible order: A B D C

Breadth‑First Search (BFS) uses a queue to explore vertices level by level.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D']

Cycle Detection in Directed Graphs

DFS with an additional recursion stack ( rec_stack) detects back‑edges that form cycles.

def has_cycle(graph):
    visited = set()
    rec_stack = set()
    def dfs(v):
        if v in rec_stack:
            return True
        if v in visited:
            return False
        visited.add(v)
        rec_stack.add(v)
        for nbr in graph[v]:
            if dfs(nbr):
                return True
        rec_stack.remove(v)
        return False
    for node in graph:
        if node not in visited and dfs(node):
            return True
    return False

graph_cycle = {
    'A': ['B'],
    'B': ['D'],
    'C': ['A'],
    'D': ['A']
}
print(has_cycle(graph_cycle))  # True

Weighted Graph and Dijkstra’s Shortest‑Path Algorithm

Weighted graphs store edge costs in the adjacency list.

graph = {
    'A': {'B': 5, 'D': 2},
    'B': {'A': 5, 'C': 1, 'D': 4},
    'C': {'B': 1, 'D': 3},
    'D': {'A': 2, 'B': 4, 'C': 3},
    'E': {}
}

Dijkstra uses a min‑heap ( heapq) to always expand the vertex with the smallest tentative distance.

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]
    visited = set()
    while pq:
        cur_dist, cur = heapq.heappop(pq)
        if cur in visited:
            continue
        visited.add(cur)
        for nbr, w in graph[cur].items():
            nd = cur_dist + w
            if nd < dist[nbr]:
                dist[nbr] = nd
                heapq.heappush(pq, (nd, nbr))
    return dist

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 5, 'C': 6, 'D': 2, 'E': inf}

The algorithm maintains the invariant that the distance for any vertex extracted from the heap is final.

Heap (Priority Queue)

A binary heap is a complete tree stored in a list. For index i, left child is 2*i+1, right child 2*i+2, parent (i-1)//2. Python’s heapq implements a min‑heap.

import heapq
heap = [1, 3, 6, 5, 9, 8]
heapq.heapify(heap)          # [1, 3, 6, 5, 9, 8]
print(heap)
min_elem = heapq.heappop(heap)  # 1
print(min_elem)
print(heap)                     # [3, 5, 6, 8, 9]
heapq.heappush(heap, 2)
print(heap)                     # [2, 3, 6, 5, 9, 8]
print(heapq.nlargest(2, heap)) # [9, 8]
print(heapq.nsmallest(2, heap))# [2, 3]

Deletion of the minimum element removes the root, replaces it with the last element, and performs a “sift‑down” to restore the heap property. This operation runs in O(log n) time.

Heap Applications

Priority Queue : always retrieve the smallest (or largest) element efficiently.

Heap Sort : repeatedly extract the root to obtain a sorted sequence in O(n log n) time.

Top‑K Problems : heapq.nlargest(k, iterable) and heapq.nsmallest(k, iterable) return the k extreme elements without full sorting.

Graph Algorithms : Dijkstra’s algorithm relies on a min‑heap to select the next vertex with the smallest tentative distance.

Additional Exercises

Find the first duplicate number in a list using a dictionary for O(n) detection.

Implement BFS that returns the visitation order of a graph.

Use heapq.nlargest to obtain the k largest elements of a list.

# First duplicate example
def find_first_duplicate(nums):
    seen = {}
    for num in nums:
        if num in seen:
            return num
        seen[num] = True
    return -1

print(find_first_duplicate([1,2,3,4,2,5]))  # 2

# BFS order example
from collections import deque

def bfs_order(graph, start):
    visited, q, order = set([start]), deque([start]), []
    while q:
        v = q.popleft()
        order.append(v)
        for n in graph[v]:
            if n not in visited:
                visited.add(n)
                q.append(n)
    return order

print(bfs_order({'A':['B','C'],'B':['A','D'],'C':['A'],'D':['B']}, 'A'))
# ['A', 'B', 'C', 'D']

# Top‑K using heapq
import heapq

def top_k(nums, k):
    return heapq.nlargest(k, nums)

print(top_k([3,2,1,5,6,4], 2))  # [6, 5]

These exercises reinforce the core concepts of list manipulation, graph traversal, and heap‑based selection.