DSA — Lists, Stacks, Queues & Linked Lists

Python lists are dynamic arrays — O(1) index access, O(n) insert in middle.

Python Lists and Arrays

Python lists are dynamic arrays — O(1) index access, O(n) insert in middle.

Many DSA tutorials use lists before custom structures.

Real-life example: A list is a numbered locker row — open locker 5 instantly, but shifting lockers takes work.

Find minimum

arr = [7, 12, 9, 4, 11]
print(min(arr))

Stacks

Stack: Last In, First Out (LIFO). Push adds top; pop removes top.

Use for undo history, browser back stack, expression parsing.

Real-life example: A stack of plates — you add and remove from the top only.

Stack with list

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

Queues

Queue: First In, First Out (FIFO). enqueue back, dequeue front.

collections.deque is efficient for queue operations.

Real-life example: A ticket queue — first person in line gets served first.

Queue with deque

from collections import deque

q = deque()
q.append("A")
q.append("B")
print(q.popleft())  # A

Linked Lists

Linked lists chain nodes with data + next pointer. Insert/delete at head is O(1).

Python has no built-in linked list — implement with classes for learning.

Real-life example: A treasure hunt — each clue points to the next location, no numbered index.

Simple linked list node

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

head = Node(1, Node(2, Node(3)))
print(head.next.data)  # 2

Hash Tables

Hash tables (dict in Python) map keys to values in average O(1) lookup.

Collisions handled internally — you use dict and set daily.

Real-life example: A hash table is a coat check — ticket number maps to your jacket instantly.

Dict as hash map

cache = {"user:1": "Aarav", "user:2": "Meera"}
print(cache["user:1"])