連結リストとは、値を保持するセルが数珠つなぎになった構造、つまり Scheme のリストと同じ構造だ。
今日は構造体やメソッドの練習として、連結リストのプログラムを写経してみる。
書き忘れていたけど、Go の一連の勉強は↓このページに沿ってやっている。
cf. お気楽 Go 言語プログラミング入門 – M.Hiroi’s Home Page
連結リストがあるのはこのページの中ほど。
cf. お気楽 Go 言語プログラミング入門 構造体 – M.Hiroi’s Home Page
それじゃ、行ってみよう。
package main
import (
"fmt"
)
type Cell struct {
item int
next *Cell
}
type List struct {
top *Cell
}
func newCell(x int, cp *Cell) *Cell {
c := new(Cell)
c.item, c.next = x, cp
return c
}
func newList() *List {
lst := new(List)
lst.top = new(Cell)
return lst
}
func (cp *Cell) nthCell(n int) *Cell {
i := -1
for cp != nil {
if i == n { return cp }
i++
cp = cp.next
}
return nil
}
func (lst *List) nth(n int) (int, bool) {
cp := lst.top.nthCell(n)
if cp == nil {
return 0, false
} else {
return cp.item, true
}
}
func (lst *List) insertNth(n, x int) bool {
cp := lst.top.nthCell(n - 1)
if cp == nil {
return false
} else {
cp.next = newCell(x, cp.next)
return true
}
}
func (lst *List) deleteNth(n int) bool {
cp := lst.top.nthCell(n - 1)
if cp == nil || cp.next == nil {
return false
} else {
cp.next = cp.next.next
return true
}
}
func (lst *List) isEmpty() bool {
return lst.top.next == nil
}
func (lst *List) printList() {
cp := lst.top.next
for ; cp != nil; cp = cp.next {
fmt.Print(cp.item, " ")
}
fmt.Println("")
}
func main() {
a := newList()
for i := 0; i < 4; i++ {
fmt.Println(a.insertNth(i, i))
}
a.printList()
for i := 0; i < 5; i++ {
n, ok := a.nth(i)
fmt.Println(n, ok)
}
for !a.isEmpty() {
a.deleteNth(0)
a.printList()
}
}
それほど難しくはない。ちょっと注意が必要なのは、List 構造体の top フィールドに入っている Cell 構造体はダミーで、その次の Cell が0番目の Cell になってるってところかな。
実行結果：
^o^ > go run linkedlist.go true true true true 0 1 2 3 0 true 1 true 2 true 3 true 0 false 1 2 3 2 3 3
うまくいった。