Introduction
Nothing fancy here, just wanted a quick reference for several common data structures written in my current favorite language. I tried to keep it idiomatic and as flexible as possible through the use of generics.
None of the text or code was generated by AI. Only a complete loser would do something like that.
Stack
A stack is a LIFO data structure.
package main
import (
"errors"
)
type Stack[T any] []T
func (s *Stack[T]) Empty() bool {
return len(*s) == 0
}
func (s *Stack[T]) Length() int {
return len(*s)
}
func (s *Stack[T]) Peek() (T, error) {
if s.Empty() {
var zero T
return zero, errors.New("StackEmpty")
}
return (*s)[len(*s)-1], nil
}
func (s *Stack[T]) Pop() (T, error) {
if s.Empty() {
var zero T
return zero, errors.New("StackEmpty")
}
v := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return v, nil
}
func (s *Stack[T]) Push(v T) {
*s = append(*s, v)
}
See the Singly Linked List implementation for using a linked list as a stack.
Queue
A queue is a FIFO data structure.
Here is a straightforward and functional (although naive) implementation of a queue, although it has significant performance issues when dequeuing (i.e., dequeuing here is an O(n) operation rather than constant time O(1)):
package main
import "errors"
type Queue[T any] []T
func (q *Queue[T]) Enqueue(v T) {
*q = append(*q, v)
}
func (q *Queue[T]) Dequeue() (T, error) {
if len(*q) == 0 {
var zero T
return zero, errors.New("QueueEmpty")
}
v := (*q)[0]
*q = (*q)[1:]
return v, nil
}
func (q *Queue[T]) Empty() bool {
return len(*q) == 0
}
See the Singly Linked List implementation for using a linked list as a queue.
Ring Buffer
All operations are constant time (O(1)).
Here is a better implementation of a queue data structure that uses a ring buffer:
package main
import (
"errors"
"fmt"
)
var (
ErrRingBufferEmpty = errors.New("RingBufferEmpty")
ErrRingBufferFull = errors.New("RingBufferFull")
)
type RingBuffer[T any] struct {
len int
buffer []T
readIndex int
writeIndex int
}
func NewRingBuffer[T any](size int) *RingBuffer[T] {
return &RingBuffer[T]{
len: size,
buffer: make([]T, size),
}
}
func (r *RingBuffer[T]) Cap() int {
return r.len
}
func (r *RingBuffer[T]) Dequeue() (T, error) {
if r.readIndex == r.writeIndex {
var zero T
return zero, fmt.Errorf("dequeue failed: %w", ErrRingBufferEmpty)
}
v := r.buffer[r.readIndex]
r.readIndex = (r.readIndex + 1) % r.len
return v, nil
}
func (r *RingBuffer[T]) Empty() bool {
return r.readIndex == r.writeIndex
}
func (r *RingBuffer[T]) Enqueue(v T) error {
if (r.writeIndex+1)%r.len == r.readIndex {
return fmt.Errorf("enqueue failed: %w", ErrRingBufferFull)
}
r.buffer[r.writeIndex] = v
r.writeIndex = (r.writeIndex + 1) % r.len
return nil
}
func (r *RingBuffer[T]) Full() bool {
return (r.writeIndex+1)%r.len == r.readIndex
}
func (r *RingBuffer[T]) Len() int {
if r.writeIndex >= r.readIndex {
return r.writeIndex - r.readIndex
}
return r.len - r.readIndex + r.writeIndex
}
It can be called like this:
b := NewRingBuffer[int](5)
n, err := b.Dequeue()
if err != nil && errors.Is(err, ErrRingBufferEmpty) {
fmt.Println(err)
}
Note that the writeIndex is where the next enqueue operation should place the element, and the rightIndex is where the next dequeue should happen.
A drawback of the ring buffer is that it has a set length. If this constraint doesn’t work for your implementation, try a Singly Linked List.
Singly Linked List
This singly linked list is intentionally flexible to include implementations for both stack (push, pop) and queue (enqueue, dequeue) data structures.
package main
import (
"errors"
"fmt"
)
type LinkedList[T comparable] struct {
Head *Node[T]
}
type Node[T comparable] struct {
Value T
Next *Node[T]
}
func NewEmptyLinkedList[T comparable]() *LinkedList[T] {
return &LinkedList[T]{nil}
}
func NewLinkedList[T comparable](v T) *LinkedList[T] {
return &LinkedList[T]{
Head: &Node[T]{v, nil},
}
}
func (l *LinkedList[T]) Append(v T) {
if l.Head == nil {
l.Head = &Node[T]{v, nil}
return
}
node := l.Head
for node.Next != nil {
node = node.Next
}
node.Next = &Node[T]{v, nil}
}
func (l *LinkedList[T]) Clear() {
l.Head = nil
}
func (l *LinkedList[T]) Dequeue() (T, error) {
if l.Head == nil {
var zero T
return zero, errors.New("ListEmpty")
}
v := l.Head.Value
l.Head = l.Head.Next
return v, nil
}
func (l *LinkedList[T]) Empty() bool {
return l.Head == nil
}
func (l *LinkedList[T]) Enqueue(v T) {
l.Append(v)
}
func (l *LinkedList[T]) Has(v T) bool {
return l.Search(v)
}
func (l *LinkedList[T]) Insert(v T, position int) error {
if position == 0 {
if l.Head == nil {
l.Head = &Node[T]{v, nil}
} else {
node := &Node[T]{v, l.Head}
l.Head = node
}
} else {
var i int
node := l.Head
var before *Node[T]
for i < position && node != nil {
before = node
node = node.Next
i += 1
}
if i < position || node == nil {
return errors.New("ListOverflow")
} else {
before.Next = &Node[T]{v, node}
}
}
return nil
}
func (l *LinkedList[T]) Len() int {
var n int
node := l.Head
for node != nil {
node = node.Next
n += 1
}
return n
}
func (l *LinkedList[T]) List() {
l.Traverse()
}
func (l *LinkedList[T]) Pop() (T, error) {
if l.Head == nil {
var zero T
return zero, errors.New("ListEmpty")
}
if l.Head.Next == nil {
v := l.Head.Value
l.Head = nil
return v, nil
}
var before *Node[T]
node := l.Head
for node.Next != nil {
before = node
node = node.Next
}
v := node.Value
before.Next = nil
return v, nil
}
func (l *LinkedList[T]) Push(v T) {
l.Append(v)
}
func (l *LinkedList[T]) Remove(position int) (T, error) {
if position == 0 {
return l.Dequeue()
}
var before *Node[T]
node := l.Head
var i int
for i < position && node != nil {
before = node
node = node.Next
i += 1
}
if i < position || node == nil {
var zero T
return zero, errors.New("ListOverflow")
}
v := node.Value
before.Next = node.Next
return v, nil
}
func (l *LinkedList[T]) Search(v T) bool {
if l.Head == nil {
return false
}
node := l.Head
for node != nil {
if v == node.Value {
return true
}
node = node.Next
}
return false
}
func (l *LinkedList[T]) Size() int {
return l.Len()
}
func (l *LinkedList[T]) Traverse() {
node := l.Head
for node != nil {
fmt.Println(node.Value)
node = node.Next
}
}
Hash Table
package main
const (
HASH_TABLE_LEN = 30
)
type HashTable[T comparable] [HASH_TABLE_LEN]*LinkedList[T]
type Member struct {
Name string
Age uint64
}
func hash(name string) rune {
var ru rune
for _, char := range name {
ru += char
ru = (ru * char) % HASH_TABLE_LEN
}
return ru
}
This implementation uses the Singly Linked List defined above to handle hash collisions.
Yes, the hashing function isn’t production worthy. For one, it doesn’t randomize as much as it should, meaning that it’s not equally distributing the hashed names among all of the possible keys for the hash table.
To use something worthy of production, check out the hash/fnv package in the Go standard library.
package main
func main() {
family := []*Member{
{"Jimmy", 54},
{"Lena", 51},
{"Robert", 78},
{"Gretchen", 26},
{"John", 72},
{"Susan", 73},
{"Kilgore", 101},
{"William", 35},
{"Billie", 22},
{"Maggie", 52},
{"Ari", 57},
{"Noam", 44},
{"Charles", 39},
}
var hashTable HashTable[*Member]
for _, member := range family {
h := hash(member.Name)
if hashTable[h] == nil {
hashTable[h] = NewEmptyLinkedList[*Member]()
}
hashTable[h].Append(member)
}
hashTable[16].Traverse()
hashTable[20].Traverse()
}
Bit Array
The bit array is my favorite data structure, and luckily, there is an excellent article on the Internet entitled On Ints as Bit Vectors about this very topic. Check it out.
That article goes into detail about solving an algorithm with the assistance of a bit array, and here is another: Tic Tac Toe! Everyone’s favorite pastime (well, not counting bingo), and now we have an efficient implementation of it starring your new friend the bit array.
All we need to store the game board are nine bits! Pretty sweet. Each player gets a uint16 game board that stores the state of their selections. Have fun, bozo.
package main
import (
"fmt"
)
var board = [2]uint16{}
func checkBoard(moves uint16) bool {
return checkDiagonally(moves) ||
winsHorizontally(moves) ||
winsVertically(moves)
}
func checkDiagonally(moves uint16) bool {
// 100010001
// 1 0 0
// 0 1 0
// 0 0 1
if (moves & 1) == 1 {
var i uint8
for i < 9 {
if !isOccupied(moves, i) {
return false
}
i += 4
}
return true
}
// 001010100
// 0 0 1
// 0 1 0
// 1 0 0
var i uint8 = 2
// Note that we don't want to go until the end of
// the board here (9) because it will loop 4 times
// and go out of bounds!
for i < 7 {
if !isOccupied(moves, i) {
return false
}
i += 2
}
return true
}
func checkHorizontal(moves uint16, i uint8) bool {
n := i
for i < n+3 {
if !isOccupied(moves, i) {
return false
}
i++
}
return true
}
func checkVertical(moves uint16, i uint8) bool {
for i < 9 {
if !isOccupied(moves, i) {
return false
}
i += 3
}
return true
}
func isOccupied(moves uint16, i uint8) bool {
return (moves >> i & 1) == 1
}
// We need 9 bits total for each player.
// Each move needs to get a 1 bit b/c 0 is ambiguous:
// Is it 0 because there was no move there?
// Or, is it 0 b/c there was a move to (0,0)?
//
// Because of this ambiguity, the best solution is to
// use a uint16 so each place on the board can be
// marked with its own bit.
func move(player, r, c uint8) {
var bitPosition uint8 = r*3 + c
for _, playerBoard := range board {
if isOccupied(playerBoard, bitPosition) {
fmt.Println("Position is occupied, make another!")
return
}
}
board[player] |= 1 << bitPosition
if checkBoard(board[player]) {
fmt.Println("You won!")
}
}
func winsHorizontally(moves uint16) bool {
return checkHorizontal(moves, 0) ||
checkHorizontal(moves, 3) ||
checkHorizontal(moves, 6)
}
func winsVertically(moves uint16) bool {
return checkVertical(moves, 0) ||
checkVertical(moves, 1) ||
checkVertical(moves, 2)
}
func main() {
// Horizontal
// 000000111
// -----
// 1 1 1
// 0 0 0
// 0 0 0
// -----
// move(1, 0, 0)
// move(1, 0, 1)
// move(1, 0, 2)
// Horizontal
// 000111000
// -----
// 0 0 0
// 1 1 1
// 0 0 0
// -----
// move(1, 1, 0)
// move(1, 1, 1)
// move(1, 1, 2)
// Horizontal
// 111000000
// -----
// 0 0 0
// 0 0 0
// 1 1 1
// -----
move(1, 2, 0)
move(0, 2, 0)
move(1, 2, 1)
move(1, 2, 2)
// Vertical
// 001001001
// -----
// 1 0 0
// 1 0 0
// 1 0 0
// -----
// move(1, 0, 0)
// move(1, 1, 0)
// move(1, 2, 0)
// Vertical
// -----
// 0 1 0
// 0 1 0
// 0 1 0
// -----
// 010010010
// move(1, 0, 1)
// move(1, 1, 1)
// move(1, 2, 1)
// Vertical
// 100100100
// -----
// 0 0 1
// 0 0 1
// 0 0 1
// -----
// move(1, 0, 2)
// move(1, 1, 2)
// move(1, 2, 2)
// Diagonal
// 100010001
// -----
// 1 0 0
// 0 1 0
// 0 0 1
// -----
// move(1, 0, 0)
// move(1, 1, 1)
// move(1, 2, 2)
// Diagonal
// 001010100
// -----
// 0 0 1
// 0 1 0
// 1 0 0
// -----
// move(1, 0, 2)
// move(1, 1, 1)
// move(1, 2, 0)
// fmt.Printf("board=%d,%b\n", board, board)
}
Summary
This summary has been approved by your mom.