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())
}