{
"$type": "site.standard.document",
"bskyPostRef": {
"cid": "bafyreihg6awpass23sn3e6pxgj3cqaxln55qswa4k7hpolutxfsjvmz6nu",
"uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mpfsejmu42s2"
},
"coverImage": {
"$type": "blob",
"ref": {
"$link": "bafkreie7xd4jq4qb6gsjwkuqlnjcqwzettpdtnhcmaclzao3bzurh53vja"
},
"mimeType": "image/webp",
"size": 211012
},
"path": "/om_k_4314/what-i-learned-in-week-8-of-python-stacks-queues-linked-lists-1e1c",
"publishedAt": "2026-06-29T05:22:04.000Z",
"site": "https://dev.to",
"tags": [
"beginners",
"computerscience",
"datastructures",
"python",
"github.com/Omk4314/neetcode-submissions",
"github.com/Omk4314/progress-on-python"
],
"textContent": "Week 7 was hash maps and two pointers — patterns that lean on Python's built-in `dict`, `set`, and `list`.\n\nWeek 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.\n\nMonth 2 is done. Here's how it closed out.\n\n## Day 50 — Stacks: LIFO, From Scratch\n\nA 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.\n\nImplementing one from scratch made that personality concrete:\n\n\n\n class Stack:\n def __init__(self):\n self.items = []\n\n def push(self, item):\n self.items.append(item)\n\n def pop(self):\n if not self.items:\n return None\n return self.items.pop()\n\n def peek(self):\n if not self.items:\n return None\n return self.items[-1]\n\n def is_empty(self):\n return len(self.items) == 0\n\n\nPython'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`.\n\nThen 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.\n\n\n\n class Solution:\n def isValid(self, s: str) -> bool:\n mp = {']': '[', ')': '(', '}': '{'}\n stack = []\n if len(s)%2 != 0:\n return False\n for c in s:\n if stack and c in mp and mp[c] == stack[-1]:\n stack.pop()\n else:\n stack.append(c)\n return len(stack) == 0\n\n\nThe 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.\n\nThe 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.\n\nWhat 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.\n\n## Day 51 — Queues: FIFO, and Stack-via-Queue\n\nA queue is a stack's opposite: **first in, first out.** Whoever's been waiting longest gets served first — like an actual queue of people.\n\n\n\n from collections import deque\n\n class Queue:\n def __init__(self):\n self.items = deque()\n\n def enqueue(self, item):\n self.items.append(item)\n\n def dequeue(self):\n if not self.items:\n return None\n return self.items.popleft()\n\n def peek(self):\n if not self.items:\n return None\n return self.items[0]\n\n def is_empty(self):\n return len(self.items) == 0\n\n\nUsing `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.\n\nThe real exercise of the day was implementing a stack using _only_ queue operations — no direct stack access allowed:\n\n\n\n class MyStack:\n\n def __init__(self):\n self.stack = []\n\n def push(self, x: int) -> None:\n self.stack.append(x)\n\n def pop(self) -> int:\n return self.stack.pop()\n\n def top(self) -> int:\n return self.stack[-1]\n\n def empty(self) -> bool:\n return len(self.stack) == 0\n\n\n # Your MyStack object will be instantiated and called as such:\n # obj = MyStack()\n # obj.push(x)\n # param_2 = obj.pop()\n # param_3 = obj.top()\n # param_4 = obj.empty()\n\n\nThis 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.\n\n## Day 52 — Linked Lists: My First Pointer-Based Structure\n\nEvery 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.\n\n\n\n class Node:\n def __init__(self, value):\n self.value = value\n self.next = None\n\n\n class LinkedList:\n def __init__(self):\n self.head = None\n\n def append(self, value):\n new_node = Node(value)\n if not self.head:\n self.head = new_node\n return\n current = self.head\n while current.next:\n current = current.next\n current.next = new_node\n\n def print_list(self):\n current = self.head\n while current:\n print(current.value, end=\" -> \")\n current = current.next\n print(\"None\")\n\n\nThe 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.\n\nThen came **Reverse Linked List** , the problem that's basically a rite of passage for this topic:\n\n\n\n # Definition for singly-linked list.\n # class ListNode:\n # def __init__(self, val=0, next=None):\n # self.val = val\n # self.next = next\n\n class Solution:\n def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n prev, curr = None, head\n while curr:\n nxt = curr.next\n curr.next = prev\n prev = curr\n curr = nxt\n return prev\n\n\nThree 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.\n\nThe 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.\n\n## Day 53 — More Linked Lists: Merging and Removing\n\n### Merge Two Sorted Lists\n\nGiven two already-sorted linked lists, merge them into one sorted list:\n\n\n\n # Definition for singly-linked list.\n # class ListNode:\n # def __init__(self, val=0, next=None):\n # self.val = val\n # self.next = next\n\n class Solution:\n def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n p1, p2 = list1, list2\n dum = ListNode()\n curr = dum\n while p1 and p2:\n if p1.val < p2.val:\n curr.next = p1\n p1 = p1.next\n else:\n curr.next = p2\n p2 = p2.next\n curr = curr.next\n if not p1:\n curr.next = p2\n else:\n curr.next = p1\n return dum.next\n\n\nThe `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.\n\n### Remove Nth Node From End of List\n\nRemove the nth node counting from the _end_ of a linked list — without knowing the list's length in advance:\n\n\n\n # Definition for singly-linked list.\n # class ListNode:\n # def __init__(self, val=0, next=None):\n # self.val = val\n # self.next = next\n\n class Solution:\n def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n dum = ListNode()\n dum.next = head\n slow = dum\n fast = dum\n for _ in range(n + 1):\n fast = fast.next\n while fast:\n slow = slow.next\n fast = fast.next\n slow.next = slow.next.next\n return dum.next\n\n\nThis 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.\n\nBoth 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.\n\n## Day 54 — The Week 8 Project: A Browser History Tracker\n\nThe end-of-week project: build something that works like a real browser's back and forward buttons. Stack-based logic applied to something tangible.\n\n\n\n class Browser:\n def __init__(self):\n self.pointer = -1\n self.history = []\n\n def forward(self):\n if self.pointer == -1:\n print(\"No history found\")\n return None\n if self.pointer >= len(self.history) - 1:\n print(\"Can't go forward!\")\n return None\n self.pointer += 1\n return self.history[self.pointer]\n\n def backward(self):\n if self.pointer == -1:\n print(\"No history found\")\n return None\n if self.pointer == 0:\n print(\"Can't go back!\")\n return None\n self.pointer -= 1\n return self.history[self.pointer]\n\n def visit_site(self, site_name):\n # Cut off future history, keep current page\n if self.pointer != -1:\n self.history = self.history[:self.pointer + 1]\n self.history.append(site_name)\n self.pointer = len(self.history) - 1\n return self.history\n\n def show_history(self):\n if not self.history:\n print(\"No history found!\")\n return\n for i, site in enumerate(self.history):\n marker = \" <-- current\" if i == self.pointer else \"\"\n print(f\" {site}{marker}\")\n\n\nThe 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.\n\n\n\n if self.pointer != -1:\n self.history = self.history[:self.pointer + 1]\n\n\nThat'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.\n\nI wrote eight structured test cases to verify this, the same testing habit from Week 5's task manager:\n\n\n\n def test():\n print(\"=\" * 50)\n print(\"TEST 1: Empty browser\")\n print(\"=\" * 50)\n b = Browser()\n b.show_history()\n print(f\"Forward: {b.forward()}\")\n print(f\"Backward: {b.backward()}\")\n\n print(\"\\n\" + \"=\" * 50)\n print(\"TEST 5: Visit new site after going back (truncate future)\")\n print(\"=\" * 50)\n b = Browser()\n b.visit_site(\"google.com\")\n b.visit_site(\"github.com\")\n b.visit_site(\"stackoverflow.com\")\n b.backward()\n b.backward()\n print(\"Before visiting reddit:\")\n b.show_history()\n b.visit_site(\"reddit.com\")\n print(\"After visiting reddit:\")\n b.show_history()\n b.forward() # Should fail - no future\n\n print(\"\\n\" + \"=\" * 50)\n print(\"TEST 8: Back then forward then back again\")\n print(\"=\" * 50)\n b = Browser()\n b.visit_site(\"A\")\n b.visit_site(\"B\")\n b.visit_site(\"C\")\n b.backward()\n b.backward()\n b.forward()\n print(f\"After A->B->C, back, back, forward: pointer = {b.pointer}\")\n b.show_history()\n b.backward()\n print(f\"After another back: pointer = {b.pointer}\")\n b.show_history()\n\n\n if __name__ == \"__main__\":\n test()\n\n\nTest 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.\n\nUnder 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.\n\n## Day 55 — Review: All of Month 2, Re-Solved\n\nThe 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.\n\nFor 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.\n\nThat'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.\n\n## 📁 What I Built This Week\n\nProject | File | Concepts Used\n---|---|---\nValid Parentheses | `validate-parentheses/submission-7.py` | Stack, hash map lookup\nImplement Stack Using Queues | `implement-stack-using-queues/submission-1.py` | Stack/queue relationship\nReverse Linked List | `reverse-a-linked-list/submission-0.py` | Three-pointer pointer reversal\nMerge Two Sorted Lists | `merge-two-sorted-linked-lists/submission-0.py` | Dummy node pattern\nRemove Nth Node From End | `remove-node-from-end-of-linked-list/submission-0.py` | Fast & slow pointers\nBrowser History Tracker | `browser_history.py` | Stack logic, pointer-based state, 8 test cases\n\nAll of it is on GitHub — two repos, one streak:\n👉 github.com/Omk4314/neetcode-submissions\n👉 github.com/Omk4314/progress-on-python\n\n## What Actually Clicked This Week\n\n * **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.\n * **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.\n * **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.\n * **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.\n * **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.\n\n\n\n## What I Want to Learn Next\n\nMonth 3 starts with Week 9, and the obvious next steps are already visible:\n\n * **Trees** — recursion is unavoidable here, and I've been dodging proper recursive thinking so far\n * **Binary search trees** — ordered structures with their own traversal logic\n * **Recursion as a pattern** , not just something that shows up inside tree problems\n * **Heaps / priority queues** — the natural extension of the queue work this week\n\n\n\nTwo 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.\n\nIf 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.\n\nSee you in Month 3. 🐍\n\n_Week 8 complete. Month 2 complete. Pointers stopped being scary somewhere around Wednesday._",
"title": "What I Learned in Week 8 of Python — Stacks, Queues & Linked Lists"
}