What I Learned in Week 8 of Python — Stacks, Queues & Linked Lists

Week 7 was hash maps and two pointers — patterns that lean on Python's built-in dict, set, and list.

Week 8 was different. This week I built the data structures themselves. Stacks, queues, linked lists — implementing them from scratch before using them to solve real problems. By the end of the week I had a browser history tracker with working back and forward buttons, built on the same logic LeetCode problems made me practice all week.

Month 2 is done. Here's how it closed out.

Day 50 — Stacks: LIFO, From Scratch

A stack is the simplest data structure with a personality: last in, first out. Whatever you added most recently is the first thing you remove. Think of a stack of plates — you take from the top.

Implementing one from scratch made that personality concrete:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.items:
            return None
        return self.items.pop()

    def peek(self):
        if not self.items:
            return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

Python's list.append() and list.pop() already behave exactly like a stack at the end — that's not a coincidence, it's the same underlying behaviour. Wrapping them in a class just gives the operations names that match the concept: push, pop, peek.

Then came the problem that made stacks click for real: Valid Parentheses. Given a string of brackets, determine if every opening bracket has a matching closing bracket in the right order.

class Solution:
    def isValid(self, s: str) -> bool:
        mp = {']': '[', ')': '(', '}': '{'}
        stack = []
        if len(s)%2 != 0:
            return False
        for c in s:
            if stack and c in mp and mp[c] == stack[-1]:
                stack.pop()
            else:
                stack.append(c)
        return len(stack) == 0

The logic: scan left to right. Every opening bracket gets pushed onto the stack. Every closing bracket checks if it matches whatever's currently on top of the stack — if it does, pop it off. If the string is valid, the stack empties out completely by the end.

The odd-length check (len(s)%2 != 0) is a quick rejection before doing any real work — an unbalanced string can never have matching pairs if its length is odd. Small optimisation, but it's the kind of thing that starts feeling natural once you've internalised what the problem actually requires.

What clicked: a stack is the exact right structure here because "most recently opened bracket needs to close first" is last-in-first-out, word for word.

Day 51 — Queues: FIFO, and Stack-via-Queue

A queue is a stack's opposite: first in, first out. Whoever's been waiting longest gets served first — like an actual queue of people.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return None
        return self.items.popleft()

    def peek(self):
        if not self.items:
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

Using deque instead of a plain list here was deliberate — list.pop(0) is O(n) because every remaining element has to shift left. deque.popleft() is O(1). For a data structure whose entire purpose is fast operations at both ends, that difference matters.

The real exercise of the day was implementing a stack using only queue operations — no direct stack access allowed:

class MyStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> int:
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def empty(self) -> bool:
        return len(self.stack) == 0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

This problem is really an exercise in thinking about how stacks and queues relate, more than the code itself — the underlying question is whether you understand that a stack can be simulated with queue primitives by rotating elements until the most recently added one is at the front. Whether implemented directly or via rotation, the goal is the same: prove you understand both structures well enough to build one from the other's tools.

Day 52 — Linked Lists: My First Pointer-Based Structure

Every data structure so far has been built on Python lists or dictionaries underneath. A linked list is different — it's nodes connected by pointers, with no built-in Python type backing it.

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
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

The mental model that finally made this click: each Node only knows about one thing — the node directly after it. There's no array, no index. To get anywhere in the list, you have to start at head and walk forward one .next at a time. That's slower than list indexing for random access, but it makes inserting and removing nodes mid-list genuinely cheap — no shifting every other element.

Then came Reverse Linked List, the problem that's basically a rite of passage for this topic:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Three pointers doing a careful dance: prev trails behind, curr is the node being processed, nxt temporarily holds onto what curr.next used to point to before it gets overwritten. Each loop iteration flips one arrow: curr.next = prev reverses the direction, then everything shifts one step forward.

The verification task for the day — "can you draw the memory layout?" — turned out to be the real test. Sketching boxes and arrows on paper before writing this function made the pointer manipulation obvious in a way that just reading the code never would have.

Day 53 — More Linked Lists: Merging and Removing

Merge Two Sorted Lists

Given two already-sorted linked lists, merge them into one sorted list:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        p1, p2 = list1, list2
        dum = ListNode()
        curr = dum
        while p1 and p2:
            if p1.val < p2.val:
                curr.next = p1
                p1 = p1.next
            else:
                curr.next = p2
                p2 = p2.next
            curr = curr.next
        if not p1:
            curr.next = p2
        else:
            curr.next = p1
        return dum.next

The dum (dummy) node was the trick that unlocked this problem. Instead of special-casing "what's the very first node of the merged list," create a throwaway placeholder node, build the real list as dum.next, and return dum.next at the end — skipping the dummy entirely. No special case for the first node needed anywhere in the loop.

Remove Nth Node From End of List

Remove the nth node counting from the end of a linked list — without knowing the list's length in advance:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dum = ListNode()
        dum.next = head
        slow = dum
        fast = dum
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dum.next

This is the fast and slow pointer trick. Move fast ahead by n + 1 steps first, creating a fixed gap between fast and slow. Then move both forward together until fast runs off the end — at that exact moment, slow is sitting right before the node that needs removing, because the gap between them was always n + 1. One pass, no length-counting needed up front.

Both problems use the same dummy-node pattern from above, and by the second problem I reached for it automatically rather than rediscovering it — a small but real sign that something from earlier in the week had actually stuck.

Day 54 — The Week 8 Project: A Browser History Tracker

The end-of-week project: build something that works like a real browser's back and forward buttons. Stack-based logic applied to something tangible.

class Browser:
    def __init__(self):
        self.pointer = -1
        self.history = []

    def forward(self):
        if self.pointer == -1:
            print("No history found")
            return None
        if self.pointer >= len(self.history) - 1:
            print("Can't go forward!")
            return None
        self.pointer += 1
        return self.history[self.pointer]

    def backward(self):
        if self.pointer == -1:
            print("No history found")
            return None
        if self.pointer == 0:
            print("Can't go back!")
            return None
        self.pointer -= 1
        return self.history[self.pointer]

    def visit_site(self, site_name):
        # Cut off future history, keep current page
        if self.pointer != -1:
            self.history = self.history[:self.pointer + 1]
        self.history.append(site_name)
        self.pointer = len(self.history) - 1
        return self.history

    def show_history(self):
        if not self.history:
            print("No history found!")
            return
        for i, site in enumerate(self.history):
            marker = "  <-- current" if i == self.pointer else ""
            print(f"  {site}{marker}")

The detail that makes this feel like a real browser rather than just a list: visit_site() truncates everything ahead of the current pointer before adding the new site.

if self.pointer != -1:
    self.history = self.history[:self.pointer + 1]

That's the exact behaviour real browsers have — if you go back two pages and then visit somewhere new, the "forward" history you had is gone. You can't go forward into a future that no longer exists once you've branched off into a new page.

I wrote eight structured test cases to verify this, the same testing habit from Week 5's task manager:

def test():
    print("=" * 50)
    print("TEST 1: Empty browser")
    print("=" * 50)
    b = Browser()
    b.show_history()
    print(f"Forward: {b.forward()}")
    print(f"Backward: {b.backward()}")

    print("\n" + "=" * 50)
    print("TEST 5: Visit new site after going back (truncate future)")
    print("=" * 50)
    b = Browser()
    b.visit_site("google.com")
    b.visit_site("github.com")
    b.visit_site("stackoverflow.com")
    b.backward()
    b.backward()
    print("Before visiting reddit:")
    b.show_history()
    b.visit_site("reddit.com")
    print("After visiting reddit:")
    b.show_history()
    b.forward()  # Should fail - no future

    print("\n" + "=" * 50)
    print("TEST 8: Back then forward then back again")
    print("=" * 50)
    b = Browser()
    b.visit_site("A")
    b.visit_site("B")
    b.visit_site("C")
    b.backward()
    b.backward()
    b.forward()
    print(f"After A->B->C, back, back, forward: pointer = {b.pointer}")
    b.show_history()
    b.backward()
    print(f"After another back: pointer = {b.pointer}")
    b.show_history()


if __name__ == "__main__":
    test()

Test 5 was the one that mattered most — it's the exact truncate-on-new-visit behaviour described above, verified explicitly rather than just assumed. Watching b.forward() correctly print "Can't go forward!" after visiting Reddit was the moment the whole design proved itself.

Under the hood, self.pointer is doing the conceptual work of two stacks glued together — everything before the pointer is "back" history, everything after is "forward" history, and a single integer plus a single list tracks both. That's a nice example of how the stack thinking from Day 50 quietly reappears in a problem that doesn't mention stacks at all.

Day 55 — Review: All of Month 2, Re-Solved

The final day of Week 8 — and of Month 2 — had two parts: re-solve five problems from earlier in the month without help, and build one new small project.

For the re-solves, the difference from Week 7's mock day was immediately obvious. Solving Two Sum II again wasn't a memory exercise — recognising "sorted input, need a pair" triggered two pointers instantly. Re-deriving Valid Parentheses meant reaching for a stack and a bracket-matching dictionary without hesitation. The patterns from Week 7 and Week 8 are now reflexes rather than lessons.

That's the real verification criterion for Day 55: not whether the code compiles, but whether it comes out faster than the first time — and it did.

📁 What I Built This Week

All of it is on GitHub — two repos, one streak:
👉 github.com/Omk4314/neetcode-submissions
👉 github.com/Omk4314/progress-on-python

What Actually Clicked This Week

• Stacks and queues are personalities, not just structures. LIFO and FIFO aren't abstract rules — they're "which one comes off first," and once that question feels intuitive, choosing between them stops requiring thought.
• The dummy node pattern removes special cases. Both linked list merge problems got simpler the moment I stopped trying to handle "the first node" as a unique case and just gave myself a throwaway node to build from.
• Fast and slow pointers solve "from the end" problems elegantly. Not knowing a list's length in advance stops being a blocker once you know to create a fixed gap between two pointers instead.
• A pointer-based browser history is secretly two stacks. The truncate-on-new-visit behaviour is exactly what makes visit_site() feel like a real browser, and it falls directly out of stack thinking from Day 50.
• Drawing pointer diagrams on paper before coding is worth the extra two minutes. Reverse Linked List went from confusing to obvious the moment I sketched it instead of just reading it.

What I Want to Learn Next

Month 3 starts with Week 9, and the obvious next steps are already visible:

• Trees — recursion is unavoidable here, and I've been dodging proper recursive thinking so far
• Binary search trees — ordered structures with their own traversal logic
• Recursion as a pattern, not just something that shows up inside tree problems
• Heaps / priority queues — the natural extension of the queue work this week

Two months of daily Python. Stacks, queues, and linked lists feel like real tools now, not topics I read about once. The browser history tracker is proof that the structures aren't just LeetCode trivia — they show up in things people actually use every day.

If you've built your own version of a back/forward history tracker, or solved any of this week's problems differently, I'd love to compare notes in the comments.

See you in Month 3. 🐍

Week 8 complete. Month 2 complete. Pointers stopped being scary somewhere around Wednesday.