History is a movable timeline
A browser must remember visited pages and maintain a cursor called the current page. Back moves the cursor toward older pages; Forward moves toward newer pages. Visiting a new page after going Back creates a new timeline and permanently discards the old forward branch.
current. Deletion occurs when a new page is visited from the middle of history.State
Ordered pages plus one current position.
Navigation
Move one link without reallocating data.
Branch change
Free all nodes after current before appending.
Expected behaviour and boundaries
| Operation | Precondition | Postcondition |
|---|---|---|
| Visit | Non-empty title and URL | New page becomes current and last |
| Back | current.previous exists | current moves exactly one node left |
| Forward | current.next exists | current moves exactly one node right |
| Show current | None | State remains unchanged |
| Clear | None | All nodes freed; first/current become NULL |
Edge cases
- Back or Forward on an empty history
- Back at the first page and Forward at the last page
- Visiting the first page when both pointers are NULL
- Visiting from the middle of a multi-node history
- Clearing once and clearing an already empty history
Why a doubly linked list?
Page = { title, url, *previous, *next }
History state = { *first, *current }first
current
A singly linked list supports Forward but cannot move Back in O(1). Two stacks are another strong solution: Back stack + current + Forward stack. The doubly linked list is chosen here because it exposes the complete timeline and makes bidirectional relationships visible.
| Candidate | Back | Forward | Display timeline | Decision |
|---|---|---|---|---|
| Array + index | O(1) | O(1) | O(n) | Simple, but fixed/resized capacity |
| Two stacks | O(1) | O(1) | Less direct | Excellent production model |
| Doubly linked list | O(1) | O(1) | O(n) | Chosen for pointer learning |
What must always remain true?
- If
first != NULL, thenfirst->previous == NULL. - For every adjacent pair A and B:
A->next == BandB->previous == A. currentis NULL only when history is empty; otherwise it points to a reachable node.- The final node’s
nextis NULL. - After Visit,
current->next == NULLbecause the new page is last.
current->next = NULL leaves a dangling pointer. A later Forward dereferences released memory.Operations as pointer transformations
Visit from the middle
current
- Walk from
current->next, save each next pointer, then free the current forward node. - Set
current->next = NULL. - Allocate the new page N.
- Set
N->previous = currentandcurrent->next = N. - Move
current = N.
current
Clear safely
Never read node->next after free(node). Store it first, free the node, then advance to the saved address.
Compiler-ready C11 program
Loading source…Reading order
Movement
Read moveBack and moveForward first; they only change current.
Mutation
Then read visit and deleteForwardHistory.
Cleanup
Finally verify every allocation reaches clearHistory.
Trace the branch-deletion rule
- Visit page A.
- Visit page B.
- Visit page C.
- Press Back.
- Visit new page D from B.
- Delete abandoned C branch.
- Connect new page D.
- Try Forward.
Press Next to begin.
Test navigation and memory edges
Test 1 — Linear navigation
Test 2 — New branch
Test 3 — Boundary movement
Test 4 — Clear and reuse
Test 5 — Empty inputs
Time and space costs
| Operation | Time | Extra space | Reason |
|---|---|---|---|
| Back / Forward / Current | O(1) | O(1) | One pointer access |
| Visit at end | O(1) | O(1) | No forward branch |
| Visit from middle | O(k) | O(1) | Free k forward nodes |
| Show / Clear history | O(n) | O(1) | Traverse every node |
Total storage is O(n) for n retained pages.
Check and extend your understanding
What changes when Back succeeds?
Which condition must hold immediately after Visit?
Extension challenges
- Add timestamps and display most-recent visit time.
- Limit history to 10 pages and delete the oldest automatically.
- Implement the same behaviour using two stacks and compare code.
- Add tab objects, each with an independent history.
Defend your structure choice
Why are both previous and next required?
They provide O(1) movement in either direction. A singly linked list would need a scan from first to locate the predecessor.
When are two stacks preferable?
When only Back/Forward operations matter and displaying the entire ordered timeline is unnecessary. A new Visit simply clears the Forward stack.
What is a dangling pointer in this project?
A link that still holds the address of a freed Page. Setting current->next to NULL after branch deletion removes that dangerous reference.
How would you detect memory errors?
Test repeated branch changes and clears, then run with AddressSanitizer or Valgrind to detect leaks and invalid accesses.
A data structure is state plus invariants
The list alone is not browser history. Correct behaviour comes from interpreting current as a cursor, distinguishing movement from mutation and restoring every link invariant after deletion or insertion.