linkedlist

README

LinkedList

LinkedList is a simple doubly linked-list implementation which offers:

• Append
• Prepend
• Remove
• ForEach
• ForEachRev
• Map
• Filter
• Reduce

Aren't linked lists bad?

It is true that in many situations, there is a better data structure to use than a linked list. While this is the case for many scenarios, it is not the case for ALL scenarios. Over the years, I've found situations where linked lists have proven extremely useful:

I need to store data, and I'm not sure if the size beforehand

When you are unsure of your slice size, you have two options:

• Pre-allocate: Which often leads to over-allocating
• Start with empty slice: Causes lots of memcpy and allocations

With a linked list, you can grow your data structure as needed. As soon as the size has stabilized, the linked list can efficiently be converted to a slice.

I need to prepend a lot

When you need to deal with lots of prepends, the common approach is to append your slice and reverse at the end. There are some caveats with this approach:

• You must wait to access your data until the appending is complete (so reverse can be called)
• You will encounter lots of memcpy during the reverse process, especially if your list is quite large

Benchmarks

# go test --bench=.

# Generic LinkedList
BenchmarkListAppend-4          10000000         120 ns/op          40 B/op      2 allocs/op
BenchmarkListPrepend-4         10000000         118 ns/op          40 B/op      2 allocs/op
BenchmarkListFilter-4          50000000        28.3 ns/op          24 B/op      0 allocs/op

# Typed (int) LinkedList
BenchmarkIntListAppend-4       20000000         100 ns/op          32 B/op      1 allocs/op
BenchmarkIntListPrepend-4      20000000        93.2 ns/op          32 B/op      1 allocs/op

# Standard library
BenchmarkStdListAppend-4       10000000         238 ns/op          56 B/op      2 allocs/op
BenchmarkStdListPrepend-4      10000000         238 ns/op          56 B/op      2 allocs/op

# Slice
BenchmarkSliceAppend-4          3000000         430 ns/op          98 B/op      1 allocs/op
BenchmarkSlicePrepend-4           30000      369399 ns/op      243917 B/op      2 allocs/op
BenchmarkSliceFilter-4         20000000        74.2 ns/op          41 B/op      0 allocs/op

# Map
BenchmarkMapAppend-4            5000000         346 ns/op         106 B/op      1 allocs/op
BenchmarkMapPrepend-4           5000000         358 ns/op         106 B/op      1 allocs/op

Usage

package main

import (
	"fmt"

	"github.com/itsmontoya/linkedlist/typed/int"
)

func main() {
	var l linkedlist.LinkedList
	// Populate list values
	l.Append(0, 1, 2, 3, 4, 5, 6)

	// Create new list with map applied
	nl := l.Map(addOne)
	// Set mapped value
	mapped := nl.Slice()

	// Filter new list
	nl.Filter(isEven)

	// Set filtered and reduced values
	filtered := nl.Slice()
	reduced := nl.Reduce(addInts)

	// Note - This can also be done shorthand as such:
	// val := l.Map(addOne).Filter(isEven).Reduce(addInts)

	fmt.Printf("Original list: %v\n", l.Slice())
	fmt.Printf("Slice with map applied: %v\n", mapped)
	fmt.Printf("Slice with map and filter applied: %v\n", filtered)
	fmt.Printf("Result of reduction: %v\n", reduced)
}

func addOne(val int) (nval int) {
	return val + 1
}

func isEven(val int) (ok bool) {
	return val%2 == 0
}

func addInts(acc, val int) (sum int) {
	return acc + val
}

Documentation

Index

• type FilterFn
• type ForEachFn
• type GenericSum
• type GenericVal
• type LinkedList
  • func (l *LinkedList) Append(vals ...GenericVal)
  • func (l *LinkedList) Filter(fn FilterFn) (nl *LinkedList)
  • func (l *LinkedList) ForEach(n *Node, fn ForEachFn) (ended bool)
  • func (l *LinkedList) ForEachRev(n *Node, fn ForEachFn) (ended bool)
  • func (l *LinkedList) Len() (n int32)
  • func (l *LinkedList) Map(fn MapFn) (nl *LinkedList)
  • func (l *LinkedList) Prepend(vals ...GenericVal)
  • func (l *LinkedList) Reduce(fn ReduceFn) (sum GenericSum)
  • func (l *LinkedList) Remove(n *Node)
  • func (l *LinkedList) Slice() (s []GenericVal)
  • func (l *LinkedList) Update(n *Node, val GenericVal)
  • func (l *LinkedList) Val(n *Node) (val GenericVal)
• type MapFn
• type Node
• type ReduceFn

Types

type FilterFn

type FilterFn func(val GenericVal) (ok bool)

FilterFn is the format of the function used to call Filter

type ForEachFn

type ForEachFn func(n *Node, val GenericVal) (end bool)

ForEachFn is the format of the function used to call ForEach

type GenericSum

type GenericSum generic.Type

GenericSum is a generic sum type used for reducing

type GenericVal

type GenericVal generic.Type

GenericVal is a generic value type

type LinkedList

type LinkedList struct {
	// contains filtered or unexported fields
}

LinkedList is a simple doubly-linked list

func (*LinkedList) Append

func (l *LinkedList) Append(vals ...GenericVal)

Append will append the list with a value, the reference Node is Returned

func (*LinkedList) Filter

func (l *LinkedList) Filter(fn FilterFn) (nl *LinkedList)

Filter will return a filtered list

func (*LinkedList) ForEach

func (l *LinkedList) ForEach(n *Node, fn ForEachFn) (ended bool)

ForEach will iterate through each node within the linked list

func (*LinkedList) ForEachRev

func (l *LinkedList) ForEachRev(n *Node, fn ForEachFn) (ended bool)

ForEachRev will iterate through each node within the linked list in reverse

func (*LinkedList) Len

func (l *LinkedList) Len() (n int32)

Len will return the current length of the linked list

func (*LinkedList) Map

func (l *LinkedList) Map(fn MapFn) (nl *LinkedList)

Map will return a mapped list

func (*LinkedList) Prepend

func (l *LinkedList) Prepend(vals ...GenericVal)

Prepend will prepend the list with a value, the reference Node is Returned

func (*LinkedList) Reduce

func (l *LinkedList) Reduce(fn ReduceFn) (sum GenericSum)

Reduce will return a reduced value

func (*LinkedList) Remove

func (l *LinkedList) Remove(n *Node)

Remove will remove a node from a list

func (*LinkedList) Slice

func (l *LinkedList) Slice() (s []GenericVal)

Slice will return a slice of the current linked list

func (*LinkedList) Update

func (l *LinkedList) Update(n *Node, val GenericVal)

Update will update the value for a given node

func (*LinkedList) Val

func (l *LinkedList) Val(n *Node) (val GenericVal)

Val will return the value for a given node

type MapFn

type MapFn func(val GenericVal) (nval GenericVal)

MapFn is the format of the function used to call Map

type Node

type Node struct {
	// contains filtered or unexported fields
}

Node is a value container

type ReduceFn

type ReduceFn func(acc, val GenericVal) (sum GenericSum)

ReduceFn is the format of the function used to call Reduce