Skip to content

Big O Visualizer

Added previous page / next page navigation on all pages

Change1 min read

With this change you'll see two arrows at the top right of the screen, whenever you're on a page. These arrows are hyperlinks that allow you to navigate to the next or previous page. I've added these because they're handy for visitors who just want to browse the site's content without having to figure out the navigation structure.

Curious about the implementation? Then read on!

CSS-only

No images or inline vector data is used to render the arrows. In fact, it only took a few lines of (pseudo) CSS to create these:

src/gatsby-plugin-theme-ui/index.ts
1arrow: {
2 width: 4,
3 height: 4,
4 marginTop: "0.25rem",
5 borderRightWidth: "0.25rem",
6 borderRightStyle: "solid",
7 borderTopWidth: "0.25rem",
8 borderTopStyle: "solid",
9 borderColor: "secondary",
10 "&:hover": {
11 borderColor: "heading",
12 },
13},

Basically the above styling creates a square element where the top and right edge have a thick border. In the TSX component template I add a rotate(45deg) or rotate(225deg) to rotate the whole thing so the arrow points in the right direction. The relevant snippet looks like this:

/src/@lekoarts/gatsby-theme-minimal-blog/components/page.tsx
1const PrevNextNav = (section: DoublyLinkedLoop<string>, slug: string) =>
2 section.contains(slug) && (
3 <Flex pt={[1, 2, 3]}>
4 <TLink as={Link} sx={{ variant: `links.secondary` }} to={section.prev(slug)!} alt="Previous page">
5 <div sx={{ variant: `icons.arrow`, transform: `rotate(225deg)` }} />
6 </TLink>
7 <div sx={{ variant: `icons.dot` }} />
8 <TLink as={Link} sx={{ variant: `links.secondary` }} to={section.next(slug)!} alt="Next page">
9 <div sx={{ variant: `icons.arrow`, transform: `rotate(45deg)` }} />
10 </TLink>
11 </Flex>
12 )

Doubly Linked Loop

In order for this feature to work, there needs to be some kind of data structure that helps me to figure out the next (or previous) page, given the current page the user is on. I choose a Doubly Linked Loop, which is a new structure I made up. It's essentially a regular Doubly Linked List but where the tail is always connected to the head. This property ensures I can blindly call next or previous on the structure, without having to worry that I'm going over some kind of edge. It also means the structure no longer has a clear beginning (headless) or end (tailless), which is why I choose to call it a Loop rather than a List. Internally, there's still a root, which is always the first element that was added.

The final implementation looks like this:

src/util/doubly-linked-loop.ts
1interface Node<T> {
2 value: T
3 prev: Node<T>
4 next: Node<T>
5}
6
7export default class DoublyLinkedLoop<T> {
8 root!: Node<T>
9 length: number
10
11 constructor(array: T[]) {
12 this.length = 0
13 array.forEach(this.add.bind(this))
14 }
15
16 add(item: T) {
17 const node = {
18 value: item,
19 } as Node<T>
20 if (this.length === 0) {
21 // eslint-disable-next-line no-multi-assign
22 node.prev = node.next = this.root = node
23 } else {
24 const last = this.root.prev
25 this.root.prev = node
26 last.next = node
27 node.prev = last
28 node.next = this.root
29 }
30 this.length++
31 }
32
33 find(item: T): Node<T> | undefined {
34 let node = this.root
35 for (let i = 0; i < this.length; i++) {
36 if (node.value === item) {
37 return node
38 }
39 node = node.next
40 }
41 return undefined
42 }
43
44 contains(item: T): boolean {
45 return this.find(item) !== undefined
46 }
47
48 next(item: T): T | undefined {
49 const node = this.find(item)
50 return node?.next?.value
51 }
52
53 prev(item: T): T | undefined {
54 const node = this.find(item)
55 return node?.prev?.value
56 }
57}

And the usage of this data structure looks like this:

/src/@lekoarts/gatsby-theme-minimal-blog/components/page.tsx
1const pages = new DoublyLinkedLoop([
2 "/docs",
3 "/demo",
4 "/sorting/bubble-sort",
5 "/sorting/selection-sort",
6 "/sorting/insertion-sort",
7 "/sorting/counting-sort",
8 "/sorting/quick-sort",
9 "/sorting/merge-sort",
10 "/sorting/heap-sort",
11 "/sorting/tim-sort",
12 "/live",
13 "/about",
14])

This wouldn't be the Big O Visualizer without me explaining the time complexity of the Doubly Linked Loop. The add method, which is the only mutation method available, has a constant time complexity: O(1). All the query operations (contains, prev and next) use the find method internally, which has a worst-case linear time complexity: O(n), where n represents the amount of elements in the loop. Since I'm not building Wikipedia the amount of elements (read: pages) will always be insignificant and thus I'm happy with a linear time complexity.