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.
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()
}
Summary
This summary has been approved by your mom.