Skip to content
Tutorials Center
My learning

Topics

Lesson 144 of 147 ยท Practice and Review

Data Structures from Scratch in Go

Build four generic data structures in Go from scratch - a stack, a ring-buffer queue, a doubly linked list and a binary search tree - and check each with table-driven style tests.

Go ships with slices and maps, and between them they solve most problems. So why build your own stack or tree? Because writing them is the best exercise for pointers, generics and methods, because interviews ask for them, and because sometimes you need a structure the standard library lacks. The standard library does have container/list, container/heap and container/ring, but they store any and give you no compile-time type safety. With generics you can do better.

In this lesson you build four structures, all generic: a stack, a queue on a ring buffer, a doubly linked list and a binary search tree. Each one is followed by a small test written as a table. The site cannot run go test, so the checks are ordinary functions that report failures; in a real project you would move them into a _test.go file as shown in table-driven tests.

A generic stack

A stack is last in, first out. A slice is the perfect backing store, because append pushes and re-slicing pops.

Go Generic stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

The output is peek: c len: 3, then c b a, then pop from empty ok? false and balanced tests failed: 0. Two design choices are typical Go: Pop returns (T, bool) instead of panicking, so the caller decides how to handle emptiness, and the zero value of Stack[T] is ready to use because a nil slice works with append.

A queue on a ring buffer

A queue is first in, first out. A naive slice queue (q = q[1:]) leaks the space at the front and keeps growing. A ring buffer reuses a fixed array: two indexes chase each other around it, and the array doubles when it is full.

Go Generic queue backed by a ring buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

You get len: 5 cap: 8, dequeued: 1 2, rest: [3 4 5 6 7 8 9] and FIFO order kept: true. All three operations take constant time; Enqueue is amortized constant, because the occasional grow costs O(n) but happens less and less often.

A doubly linked list

A linked list stores each value in a node that points to its neighbors. Inserting or removing at a known node is O(1), but finding by index is O(n). In Go, with a garbage collector, you do not free nodes: you only update the pointers.

Go Generic doubly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

The output: [1 <-> 2 <-> 3 <-> 4] size 4, removed 3: true, removed 9: false, [1 <-> 2 <-> 4] size 3, reversed: [4 <-> 2 <-> 1], backward: [1 2 4]. The tricky part is always the edge cases: an empty list, the first node and the last node. That is why the test walks the list backward too; a wrong prev pointer would show up there. The All method returns an iterator function, so callers can write for v := range l.All().

A binary search tree

A binary search tree keeps smaller keys on the left and larger keys on the right, which makes lookup O(log n) when the tree is balanced. To compare generic keys we need an ordering constraint: cmp.Ordered accepts every type that supports <.

Go Generic binary search tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

You see size: 6 height: 4, then the keys in alphabetical order with the last value for mango replaced (apple=1 banana=5 fig=3 kiwi=4 mango=6 pear=2), kiwi: 4 true, plum found: false and skewed height: 8. The last line is the weakness of a plain BST: inserting sorted data makes a straight line with O(n) lookups. Production code uses a self-balancing tree such as a red-black or AVL tree, or a B-tree; the idea of this one stays the same.

Before building your own structure, check what is available. A slice with slices.BinarySearch gives you a sorted list; a map gives O(1) lookup; container/heap provides priority queues. Write your own when you need generic type safety, a special invariant or a learning exercise.

Testing data structures

Structures are easy to test because they have no I/O. A good test suite always covers the empty structure, one element, many elements, and the boundaries (first, last, wrap-around, duplicates). Comparing against a trusted model is powerful too: after a random series of operations on your tree, its in-order output must equal the sorted keys of an ordinary map. With fuzzing the compiler's tooling can generate those operation sequences for you.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does Stack[T].Pop return (T, bool) instead of just T?

    When the stack is empty there is no value to return. The bool says whether the T is real, so a legitimate 0 or empty string is not confused with 'nothing'.
  2. 2. What problem does a ring buffer solve for a queue built on a slice?

    Two indexes wrap around a fixed array, so dequeued slots are reused and memory stays bounded.
  3. 3. Which constraint lets a generic tree compare keys with < and >?

    comparable only allows == and !=. cmp.Ordered covers the types that support ordering operators, so cmp.Compare works on them.
  4. 4. What happens to a plain binary search tree when you insert already sorted keys?

    Every new key goes to the right of the previous one, so the tree degenerates into a linked list. Self-balancing trees fix this.

Summary

  • Generic types such as Stack[T any] and Tree[K cmp.Ordered, V any] give you type-safe containers without any casts.
  • A slice is the natural backing store for a stack; a ring buffer gives a queue with reused space and amortized O(1) operations.
  • Linked lists make local edits cheap but need careful handling of the empty, first and last node; test the prev links by walking backward.
  • A binary search tree gives O(log n) operations only while it stays balanced.
  • Return (T, bool) for "maybe nothing", make zero values usable, and write table-style tests that include empty, single, many and boundary cases.

Next: Go Interview Questions puts these ideas to work in typical interview problems.