連結リスト

連結リストとは、値を保持するセルが数珠つなぎになった構造、つまり 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

うまくいった。