[Go] Linked List

Go provide some useful data structure.

Usage

package main

import (
  "container/list"
  "fmt"
)

func main() {
  v := list.New()
  testList1 := v.PushBack(1)
  testList2 := v.PushFront(2)
  v.InsertBefore(3, testList1)
  v.InsertAfter(4, testList2)

  for e := v.Front(); e != nil; e = e.Next() {
    fmt.Print(e.Value, " ")
  }
  fmt.Println()
  // 2 4 3 1

  for e := v.Back(); e != nil; e = e.Prev() {
    fmt.Print(e.Value, " ")
  }
  fmt.Println()
  // 1 3 4 2
}

The list is included in the container/list package.

You can add elements through PushBack(), PushFront(), InsertBefore(), and InsertAfter() methods.

And, you can traverse list using Front(), Back(), and Next(), Prev() methods.

Pros and Cons

List is faster than array in insert elements and remove elements.

But, list is slower than array in accessing elements.

Create Queue using List

Queue is a data structure in which the data input/output operates as a FIFO(First In First Out).

In other words, there is one entrance and one exit each.

//       ---------
// OUT <-  QUEUE  <- IN 
//       ---------

package main

import (
  "container/list"
  "fmt"
)

type Queue struct {
  l *list.List
}

func NewQueue() *Queue {
  return &Queue{list.New()}
}

func (q *Queue) Enqueue(v interface{}) {
  q.l.PushBack(v)
}

func (q *Queue) Dequeue() interface{} {
  front := q.l.Front()
  if front != nil {
    return q.l.Remove(front)
  }
  return nil
}

func main() {
  queue := NewQueue()

  for i := 1; i < 5; i++ {
    queue.Enqueue(i)
  }

  v := queue.Dequeue()
  for v != nil {
    fmt.Printf("%v -> ", v)
    v = queue.Dequeue()
  }
  fmt.Println("End")
  // 1 -> 2 -> 3 -> 4 -> End
}

Create Stack using List

Stack is a data structure in which the data input/output operates as aLIFO(Last In First Out).

In other words, there is only one entrance and exit.

// ----------
// |  STACK  <- IN
// |         -> OUT
// ----------

package main

import (
  "container/list"
  "fmt"
)

type Stack struct {
  l *list.List
}

func NewStack() *Stack {
  return &Stack{list.New()}
}

func (s *Stack) Push(v interface{}) {
  s.l.PushBack(v)
}

func (s *Stack) Pop() interface{} {
  back := s.l.Back()
  if back != nil {
    return s.l.Remove(back)
  }
  return nil
}

func main() {
  stack := NewStack()

  for i := 1; i < 5; i++ {
    stack.Push(i)
  }

  v := stack.Pop()
  for v != nil {
    fmt.Printf("%v -> ", v)
    v = stack.Pop()
  }
  fmt.Println("End")
  // 4 -> 3 -> 2 -> 1 -> End
}

Circular Linked List (Ring)

Ring is the data structure that doesn't have an end.

It continuously circularly traverses items.

package main

import (
  "container/ring"
  "fmt"
)

func main() {
  r := ring.New(4)

  for i := 0; i < r.Len(); i++ {
    r.Value = i
    r = r.Next()
  }

  for i := 0; i < r.Len(); i++ {
    fmt.Print(r.Value, " ")
    r = r.Next()
  }
  fmt.Println()
  // 0 1 2 3

  for i := 0; i < r.Len(); i++ {
    fmt.Print(r.Value, " ")
    r = r.Prev()
  }
  fmt.Println()
  // 0 3 2 1
}

The ring is included in the container/ring package.

The number of elements is fixed in the creation time.

You can put values through Value property.

And, you can traverse ring using Next(), Prev() methods.