Skip to content

Instantly share code, notes, and snippets.

@husobee
Created April 27, 2017 18:59
Show Gist options
  • Save husobee/69068c1a17068c42d603e6fd119f6dc3 to your computer and use it in GitHub Desktop.
Save husobee/69068c1a17068c42d603e6fd119f6dc3 to your computer and use it in GitHub Desktop.
simple linked list implementation
package main
import "fmt"
func main() {
// create list
l := new(List)
// append to list
for i := 0; i < 100; i++ {
l.Append(i)
}
// print everything in the list
for node := l.GetRoot(); node != nil; node = node.Next() {
fmt.Println(node.Value())
}
fmt.Println(">>>>>>>>>>>>>>")
// reverse the list
l2 := l.Reverse()
// print everything in the list
for node := l2.GetRoot(); node != nil; node = node.Next() {
fmt.Println(node.Value())
}
}
// Node - node structure in linked list
type Node struct {
next *Node
value interface{}
}
// Next - helper to get the next value
func (n *Node) Next() *Node {
return n.next
}
// Value - helper to get the node value
func (n *Node) Value() interface{} {
return n.value
}
// List - linked list implementation
type List struct {
root *Node
}
// Append - append a value to the list
func (l *List) Append(v interface{}) {
// if the root is nil, make the root of the list contain this value
if l.root == nil {
l.root = &Node{
value: v,
}
return
} else {
// otherwise keep recursing
listAppend(l.GetRoot(), v)
}
}
// listAppend - recursively append a node to a list
func listAppend(node *Node, v interface{}) {
// if we are at the end of the list, make the next
// node a new one containing value v as value
if node.Next() == nil {
node.next = &Node{
value: v,
}
} else {
// we are not at the end yet, keep recursing.
listAppend(node.Next(), v)
}
}
// GetRoot - helper to get the root node of a list
func (l *List) GetRoot() *Node {
return l.root
}
// Reverse - List reversal produces a list in the reverse
func (l *List) Reverse() *List {
newList := new(List)
// call recursive reversal
listReverse(l.root, newList)
return newList
}
// listReverse - recursive list reversal
func listReverse(node *Node, newList *List) {
// if we are not at the end of the list, keep recursing
if node.Next() != nil {
listReverse(node.Next(), newList)
}
// append a node to the new list
newList.Append(node.Value())
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment