Doubly Linked List

Description

This example demonstrates how you could implement a doubly linked list in go.

An embedded struct is used to store the Value for each Node in the list.

type Value struct {
    Name string
    MilesAway int
}
type Node struct {
    Value               // Embedded struct
    next, prev  *Node
}

A map is used to track which nodes have been processed:

processed := make(map[*Node]bool)

Be sure to read the Notes section for a short discussion on the practical implications of using a linked list.

Golang Features

This golang code sample demonstrates the following go language features:

home grown doubly linked list
basic error handling
iterating linked list
map indexed by Node to track
embedded struct
pointers
functions
string package

Code Example

package main
import (
    "fmt"
    "errors"
    "strings"
)
type Value struct {
    Name string
    MilesAway int
}
type Node struct {
    Value               // Embedded struct
    next, prev  *Node
}
type List struct {
    head, tail *Node
}
func (l *List) First() *Node {
    return l.head
}
func (n *Node) Next() *Node {
    return n.next
}
func (n *Node) Prev() *Node {
    return n.prev
}
// Create new node with value
func (l *List) Push(v Value) *List {
    n := &Node{Value: v}
    if l.head == nil {
        l.head = n      // First node
    } else {
        l.tail.next = n // Add after prev last node
        n.prev = l.tail // Link back to prev last node
    }
    l.tail = n          // reset tail to newly added node
    return l
}
func (l *List) Find(name string) *Node {
    found := false
    var ret *Node = nil
    for n := l.First(); n != nil && !found; n = n.Next() {
        if n.Value.Name == name {
            found = true
            ret = n
        }
    }
    return ret
}
func (l *List) Delete(name string) bool {
    success := false
    node2del := l.Find(name)
    if node2del != nil {
        fmt.Println("Delete - FOUND: ", name)
        prev_node := node2del.prev
        next_node := node2del.next
        // Remove this node
        prev_node.next = node2del.next
        next_node.prev = node2del.prev
        success = true
    }
    return success
}
var errEmpty = errors.New("ERROR - List is empty")
// Pop last item from list
func (l *List) Pop() (v Value, err error) {
    if l.tail == nil {
        err = errEmpty
    } else {
        v = l.tail.Value
        l.tail = l.tail.prev
        if l.tail == nil {
            l.head = nil
        }
    }
    return v, err
}

func main() {
    dashes := strings.Repeat("-", 50)
    l := new(List)  // Create Doubly Linked List

    l.Push(Value{Name: "Atlanta", MilesAway: 0})
    l.Push(Value{Name: "Las Vegas", MilesAway: 1961})
    l.Push(Value{Name: "New York", MilesAway: 881})

    processed := make(map[*Node]bool)

    fmt.Println("First time through list...")
    for n := l.First(); n != nil; n = n.Next() {
        fmt.Printf("%v\n", n.Value)
        if processed[n] {
            fmt.Printf("%s as been processed\n", n.Value)
        }
        processed[n] = true
    }
    fmt.Println(dashes)
    fmt.Println("Second time through list...")
    for n := l.First(); n != nil; n = n.Next() {
        fmt.Printf("%v", n.Value)
        if processed[n] {
            fmt.Println(" has been processed")
        } else { fmt.Println() }
        processed[n] = true
    }

    fmt.Println(dashes)
    var found_node *Node
    city_to_find := "New York"
    found_node = l.Find(city_to_find)
    if found_node == nil {
        fmt.Printf("NOT FOUND: %v\n", city_to_find)
    } else {
        fmt.Printf("FOUND: %v\n", city_to_find)
    }

    city_to_find = "Chicago"
    found_node = l.Find(city_to_find)
    if found_node == nil {
        fmt.Printf("NOT FOUND: %v\n", city_to_find)
    } else {
        fmt.Printf("FOUND: %v\n", city_to_find)
    }

    fmt.Println(dashes)
    city_to_remove := "Las Vegas"
    successfully_removed_city := l.Delete(city_to_remove)
    if successfully_removed_city {
        fmt.Printf("REMOVED: %v\n", city_to_remove)
    } else {
        fmt.Printf("DID NOT REMOVE: %v\n", city_to_remove)
    }

    city_to_remove = "Chicago"
    successfully_removed_city = l.Delete(city_to_remove)
    if successfully_removed_city {
        fmt.Printf("REMOVED: %v\n", city_to_remove)
    } else {
        fmt.Printf("DID NOT REMOVE: %v\n", city_to_remove)
    }

    fmt.Println(dashes)
    fmt.Println("* Pop each value off list...")
    for v, err := l.Pop(); err == nil; v, err = l.Pop() {
        fmt.Printf("%v\n", v)
    }
    fmt.Println(l.Pop())  // Generate error - attempt to pop from empty list
}

Notes

A map of boolean values can be used as a set-like data structure to detect cycles in the list as follows:

processed := make(map[*Node]bool)

for n := l.First(); n != nil; n = n.Next() {
   if processed[n] {
       fmt.Printf("%s as been processed\n", n.Value)
   }
   processed[n] = true
}

The expression processed[n] is true if n has been visited, or false if n is not present. There's no need to use the two-value form to test for the presence of n in the map; the zero value default does it for us.

You might notice that that iterations are performed using the for clause, rather than range; That is mainly because the range clause provides a way to iterate over a array, slice, string, map, or channel -- not for iterating over a home-grown doubly linked list.

Here's how we iterated using the for clause:

found := false
    var ret *Node = nil
    for n := l.First(); n != nil && !found; n = n.Next() {
        if n.Value.Name == name {
            found = true
            ret = n
        }
    }

Here's how to iterate using the range clause:

 for k, v := range myMap {
     log.Printf("key=%v, value=%v", k, v)
 }

 for v := range myChannel {
     log.Printf("value=%v", v)
 }

Note that slices can be utilized, rather than linked lists, to achieve similar goals in go.

There are valid reasons to use slices (rather than linked lists):

Slices are faster than linked lists
Linked lists can't be serialized via gob encoding due to its use private variables

Golang's container/list Package

This article shows how you might implement a home grown version of what comes out of the box with Go's container/list Package.

Here's what you get in the container/list Package:

type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) PushBack(v interface{}) *Element
func (l *List) PushBackList(other *List)
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushFrontList(other *List)
func (l *List) Remove(e *Element) interface{}

Output

First time through list...
{Atlanta 0}
{Las Vegas 1961}
{New York 881}
--------------------------------------------------
%sSecond time through list...
{Atlanta 0} has been processed
{Las Vegas 1961} has been processed
{New York 881} has been processed
--------------------------------------------------
FOUND: New York
NOT FOUND: Chicago
--------------------------------------------------
Delete - FOUND:  Las Vegas
REMOVED: Las Vegas
DID NOT REMOVE: Chicago
--------------------------------------------------
* Pop each value off list...
{New York 881}
{Atlanta 0}
{ 0} ERROR - List is empty

Process finished with exit code 0

Golang Code Examples