MARISSA MOLEJON | OCT2025-1 | Module-Complexity | Sprint 2 | feat/linked list - #4

Summary

Implements LinkedList from scratch in linked_list.py, supporting
push_head, pop_tail, and remove, each with O(1) worst-case time
complexity as required.

Changes made

• Added a Node class holding value, previous, and next.
• Added a LinkedList class holding head and tail.
• push_head(value) — inserts a new node at the front, updates head
  (and tail, if the list was empty), and returns the node itself as a
  handle for later removal.
• pop_tail() — reads the tail's value, removes the tail node via
  remove, and returns the value.
• remove(node) — reconnects node.previous and node.next around the
  removed node, updating head/tail when the removed node was at
  either end, and clears the removed node's own pointers.

Design notes

The list is doubly-linked (each node stores both previous and
next), which is what makes remove(node) O(1): given a direct
reference to a node, its neighbors can be reconnected without searching
the rest of the list. A singly-linked list would require an O(n) walk
from head to find the node's predecessor.

pop_tail is implemented in terms of remove, rather than duplicating
the pointer-reconnection logic, so there's a single source of truth for
"how to detach a node from the list."

Testing

All three provided tests pass:

• test_pushes_then_pops — confirms push_head/pop_tail order
• test_remove — confirms removing a middle node reconnects its neighbors
• test_remove_tail — confirms head/tail updates and pointer cleanup on
  the removed node

Ran locally via python3 -m pytest linked_list_test.py -v — all passing.

Learning points

• The key insight for O(1) remove given a node handle: the node itself
  must carry enough information (previous and next) to fix up its
  neighbors without any search. This is the core trade-off a
  doubly-linked list makes over a singly-linked one — a bit more memory
  per node, in exchange for O(1) removal from anywhere in the list.
• Reusing remove inside pop_tail avoids duplicating the
  neighbor-reconnection logic in two places.

Checklist

• All operations are O(1) worst-case
• All tests pass
• No test files modified
• Self-reviewed for readability, naming, and duplication