今回は「構造体 (structure)」について説明します。Go 言語の構造体は、基本的にはＣ言語の構造体と同じですが、このほかにも「メソッド (method)」の定義や構造体の「埋め込み」といった高度な機能があります。Go 言語の場合、クラスや継承といったオブジェクト指向機能はサポートされていません。ところが、メソッドや埋め込み、まだ説明していませんがインターフェースを使うと、Go 言語でもオブジェクト指向プログラミングが可能になります。
近代的なプログラミング言語は、ユーザーが既存の型を組み合わせて、新しい型を定義する機能を備えています。Go 言語の場合、type 文を使って新しいユーザー型を定義することができます。既存の型の組み合わせは「構造体 (structure)」を使って行います。一般的には、一つまたはそれ以上のデータを構造体に格納し、type 文を使ってそれに新しい型名を付ける、という使い方になります。
構造体の定義を下図に示します。
type 型名 struct {
フィールド名1 型1
.....
フィールド名n 型n
}
図 : 構造体の定義
type の後ろに型名を、その後ろに struct を書き、{ ... } の中に要素を定義します。構造体の要素のことを「フィールド」といい、フィールドは名前 (フィールド名) と型で構成されます。なお、type と型名を省略すると「無名の構造体」になりますが、本稿では説明を割愛します。使う機会があれば、そのときに説明することにします。
次は構造体の使い方を説明します。構造体の変数は次のように宣言します。
var 変数名 型
var 変数名 型 = 型{値1, 値2, ..., 値n}
var 変数名 型 = 型{名前1: 値1, 名前2: 値2, ..., 名前n: 値n}
フィールドの初期値を指定する場合、構造体で定義した順番で値を指定します。フィールド名で値を指定することもできます。この場合、順番は関係ありません。初期値が省略されたフィールドはゼロ値で初期化されます。フィールドのアクセスは簡単で、変数名 + ドット (.) + フィールド名 で行います。
簡単な例を示しましょう。次のリストを見てください。
リスト : 構造体の使用例 (sample71.go)
package main
import (
"fmt"
"math"
)
type Point struct {
x float64 // x, y float64
y float64
}
func distance(p, q Point) float64 {
dx := p.x - q.x
dy := p.y - q.y
return math.Sqrt(dx * dx + dy * dy)
}
func main() {
var p Point // p := Point{}
var q Point = Point{10, 10} // q := Point{10, 10}
var r Point = Point{x:100, y:100} // r := Point{x:100, y:100}
fmt.Println(p)
fmt.Println(q)
fmt.Println(r)
fmt.Println(p.x)
fmt.Println(p.y)
fmt.Println(q.x)
fmt.Println(q.y)
fmt.Println(r.x)
fmt.Println(r.y)
fmt.Println(distance(p, q))
fmt.Println(distance(p, r))
fmt.Println(distance(q, r))
}
$ go run sample71.go
{0 0}
{10 10}
{100 100}
0
0
10
10
100
100
14.142135623730951
141.4213562373095
127.27922061357856
点を表す構造体 Point を定義します。Point の P は英大文字ですが、この例では point でもかまいません。Go 言語の場合、英大文字から始まる名前 (関数名、型名、フィールド名など) は、他のパッケージからアクセスすることができます。英小文字で始まる名前は、他のパッケージからアクセスすることはできません。同じパッケージ内であれば英小文字から始まる名前でもアクセスすることができます。
Point は座標を表す 2 つのフィールド x, y があり、それらの型は float64 です。x, y float64 と書いてもかまいません。var p Point と定義すると、p.x, p.y は 0 に初期化されます。p := Point{} としてもかまいませんが、p := Point とするとコンパイルエラーになります。同様に、q.x, q.y は 10 に、r.x, r.y は 100 に初期化されます。
関数 distance は p と q の距離を求めます。関数の引数に構造体を渡すとき、フィールドの値がコピーされることに注意してください。コピーしたくない場合やフィールドの値を書き換えたい場合はポインタを渡してください。
構造体にアドレス演算子 & を適用すると、構造体へのポインタを生成することができます。
簡単な例を示しましょう。次のリストを見てください。
リスト : 構造体とポインタ (sample72.go)
package main
import (
"fmt"
"math"
)
type Point struct {
x float64 // x, y float64
y float64
}
func distance(p, q *Point) float64 {
dx := p.x - q.x
dy := p.y - q.y
return math.Sqrt(dx * dx + dy * dy)
}
func main() {
var p *Point = &Point{} // p := &Point{}
var q *Point = &Point{10, 10} // q := &Point
var r *Point = new(Point) // r := new(Point)
r.x, r.y = 100, 100
fmt.Println(p)
fmt.Println(q)
fmt.Println(r)
fmt.Println(p.x)
fmt.Println(p.y)
fmt.Println(q.x)
fmt.Println(q.y)
fmt.Println(r.x)
fmt.Println(r.y)
fmt.Println(distance(p, q))
fmt.Println(distance(p, r))
fmt.Println(distance(q, r))
}
$ go run sample72.go
&{0 0}
&{10 10}
&{100 100}
0
0
10
10
100
100
14.142135623730951
141.4213562373095
127.27922061357856
構造体のポインタ型は構造体の型名に * を付けたものになります。フィールド変数のアクセスは、ポインタ変数の場合でも 変数名 + ドット (.) + フィールド名 で行うことができます。Ｃ言語のように矢印 (->) を使う必要はありません。構造体の実体は new を使って動的に確保することもできます。この場合、フィールドはゼロ値で初期化されます。Go 言語では、次のような初期化関数を作るのが一般的な作法のようです。
リスト : Point の初期化関数
func newPoint(x, y float64) *Point {
p := new(Point)
p.x, p.y = x, y
return p
}
関数 distance の引数はポインタ型 *Point に変更しています。これで Point をコピーしないで distance に渡すことができます。
構造体は配列 (スライス) に格納することができます。スライスの場合、宣言は次のようになります。
var 変数名 []型 = []型{型a{ ... }, 型b{ ... }, ..., 型n{ ... }}
var 変数名 []型 = []型{{ ... }, { ... }, ..., { ... }}
初期値の指定で、型a, 型b, ..., 型n が型と同じ場合は 型a, 型b, ..., 型n を省略することができます。通常、変数や配列の宣言と異なるデータ型は変数や配列に格納することはできませんが、interface という型で変数や配列を宣言すると、異なるデータ型でも変数や配列に格納することができます。interface は回を改めて詳しく説明する予定です。
簡単な例を示しましょう。次のリストを見てください。
リスト : 構造体と配列 (sample73.go)
package main
import "fmt"
type Point struct {
x, y float64
}
func newPoint(x, y float64) *Point {
p := new(Point)
p.x, p.y = x, y
return p
}
func main () {
var a []Point = []Point{
{x:0, y:0}, {10, 10}, {100, 100},
}
var b []*Point = make([]*Point, 8)
fmt.Println(a)
fmt.Println(b)
for i := 0; i < 8; i++ {
b[i] = newPoint(float64(i), float64(i))
}
fmt.Println(b)
for i := 0; i < 8; i++ {
fmt.Println(*b[i])
}
}
$ go run sample73.go
[{0 0} {10 10} {100 100}]
[<nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil>]
[0xc0000160d0 0xc0000160e0 0xc0000160f0 0xc000016100 0xc000016110 0xc000016120 0xc000016130 0xc000016140]
{0 0}
{1 1}
{2 2}
{3 3}
{4 4}
{5 5}
{6 6}
{7 7}
スライス a は 3 個の Point を格納しています。スライス b は 10 個の Point へのポインタを格納します。ただし、make でポインタ型 (*Point) のスライスを生成すると、スライスの各要素の値はゼロ値 (nil) になるので、関数 newPoint を使ってスライスの要素に構造体へのポインタをセットします。float64() は整数値を float64 に変換する関数です。スライス b はポインタを格納しているので、*b[i] とすると i 番目に格納されている構造体にアクセスすることができます。
次は、三次元の座標を表す構造体 Point3d を追加しましょう。構造体 Point3d は簡単に定義できますが、二点間の距離を求める関数は distance と名前を付けることはできません。それは Point の距離を求める関数として定義されているからです。データの型と距離を求める関数は一対一に対応しているので、距離を求めるときは関数を自動的に選択してくれる機能があると便利です。
実をいうと、このような処理は特別な機能がなくても、構造体に関数を含めることで実現できます。今回の場合は、距離を求める関数を構造体のフィールド名 distance に格納しておきます。距離を求めるときは、構造体から distance に格納されている関数を取り出して評価すればいいわけです。
プログラムは次のようになります。
リスト : 構造体に関数を格納する (sample74.go)
package main
import (
"fmt"
"math"
)
type Point struct {
x, y float64
distance func(*Point) float64
}
type Point3d struct {
x, y, z float64
distance func(*Point3d) float64
}
func distance(p, q *Point) float64 {
dx := p.x - q.x
dy := p.y - q.y
return math.Sqrt(dx * dx + dy * dy)
}
func distance3d(p, q *Point3d) float64 {
dx := p.x - q.x
dy := p.y - q.y
dz := p.z - q.z
return math.Sqrt(dx * dx + dy * dy + dz * dz)
}
func newPoint(x, y float64) *Point {
p := new(Point)
p.x, p.y = x, y
p.distance = func(q *Point) float64 { return distance(p, q) }
return p
}
func newPoint3d(x, y, z float64) *Point3d {
p := new(Point3d)
p.x, p.y, p.z = x, y, z
p.distance = func(q *Point3d) float64 { return distance3d(p, q) }
return p
}
func main() {
p1 := newPoint(0, 0)
p2 := newPoint(10, 10)
q1 := newPoint3d(0, 0, 0)
q2 := newPoint3d(10, 10, 10)
fmt.Println(p1.distance(p2))
fmt.Println(q1.distance(q2))
}
$ go run sample74.go 14.142135623730951 17.320508075688775
Point にフィールド distance を追加します。関数の型は func(*Point) float64 とします。Point3d は座標を表すフィールド x, y, z と、関数を格納するフィールド distance を用意します。関数の型は func(*Point3d) float64 になります。
そして、newPoint と newPoint3d で座標と関数をフィールドにセットします。関数は匿名関数を使います。匿名関数はクロージャなので、new で確保した構造体の実体 p にアクセスすることができます。あとは、p と引数の q を関数 distance (または distance3d) に渡して評価すれば距離を求めることができます。呼び出し方法も簡単です。点 p1 の distance は関数型なので、p1.distance(p2) とすれば、p1 と p2 の距離を求めることができます。
ところで、この方法には大きな欠点があります。Point や Point3d をひとつ生成するたびにクロージャも生成されるので、多量の点を生成するとメモリを無駄に消費してしまうのです。Go 言語の場合、同じ事をもっと簡単に効率的に行うことができます。それが「メソッド (method)」です。
Go 言語の場合、メソッドは構造体と結び付けられた (関連付けられた) 関数です。一般的なオブジェクト指向言語の場合、メソッドはクラスと強く関連付けられていて、メソッドの定義もクラスの中で行います。これに対し、Go 言語のメソッドは構造体の中に定義するのではなく、メソッドの引数の型で構造体と関連付けられます。このような方法は他のプログラミング言語にもあって、Common Lisp のオブジェクト指向システム CLOS でもメソッドの定義はクラスと独立しています。
メソッドは func 文を使って定義します。
func (仮引数 型) 名前(仮引数 型, ...) 返り値の型 { ... }
func と名前の間にある (仮引数 型) を「レシーバ」といいます。メソッドはレシーバの型と関連付けられることに注意してください。残りの引数の型とは関連付けられません。ご注意ください。[*1]
メソッドの型はレシーバを第 1 引数とした関数の型と同じになります。
func 名前(レシーバの型, 仮引数の型, ...) 返り値の型
つまり、関数の第 1 引数をレシーバとして特別に扱うのが Go 言語のメソッドなのです。
Go 言語の場合、レシーバの型が異なれば、同じ名前のメソッドでも定義することができます。つまり、Point と Point3d で同名のメソッド distance を定義することができるわけです。メソッドの呼び出し方法も簡単で、構造体 + ドット (.) + メソッド名(引数, ...) となります。ようするに、フィールドのアクセス方法と同じで、構造体にメソッド名のフィールドがあるかのように動作します。
なお、Go 言語のメソッドは構造体だけではなく、既存のデータ型でも type で別名を付けるとメソッドを定義することができます。
簡単な例を示しましょう。Point と Point3d でメソッドを使うと次のようになります。
リスト : メソッドの使用例
package main
import (
"fmt"
"math"
)
type Point struct {
x, y float64
}
type Point3d struct {
x, y, z float64
}
func newPoint(x, y float64) *Point {
p := new(Point)
p.x, p.y = x, y
return p
}
func newPoint3d(x, y, z float64) *Point3d {
p := new(Point3d)
p.x, p.y, p.z = x, y, z
return p
}
func (p *Point) distance(q *Point) float64 {
dx := p.x - q.x
dy := p.y - q.y
return math.Sqrt(dx * dx + dy * dy)
}
func (p *Point3d) distance(q *Point3d) float64 {
dx := p.x - q.x
dy := p.y - q.y
dz := p.z - q.z
return math.Sqrt(dx * dx + dy * dy + dz * dz)
}
func main() {
p1 := newPoint(0, 0)
p2 := newPoint(10, 10)
q1 := newPoint3d(0, 0, 0)
q2 := newPoint3d(10, 10, 10)
fmt.Println(p1.distance(p2))
fmt.Println(q1.distance(q2))
}
とても簡単になりましたね。
ところで、レシーバの型を T とすると、メソッドは T とそのポインタ型 *T の両方に関連付けることはできません。たとえば、func (p *Point) distance ... と定義したら、func (p Point) distance ... と定義することはできません。逆に、distance と Point を関連付けたら、*Point と関連付けることはできません。
それから、レシーバの型がポインタ型でない場合、実引数はレシーバの仮引数にコピーされることに注意してください。逆にポインタ型の場合は、レシーバの仮引数にはポインタが渡されるので、実引数がコピーされることはありません。次の例を見てください。
リスト : レシーバの型 (sample75.go)
package main
import "fmt"
type Foo struct {
a, b int
}
func (p Foo) swap() {
p.a, p.b = p.b, p.a
fmt.Println("Foo swap!", p)
}
type Bar struct {
a, b int
}
func (p *Bar) swap() {
p.a, p.b = p.b, p.a
fmt.Println("Bar swap!", p)
}
func main() {
a := Foo{1, 2}
b := &Foo{3, 4}
c := Bar{5, 6}
d := &Bar{5, 6}
fmt.Println(a)
fmt.Println(b)
fmt.Println(c)
fmt.Println(d)
a.swap()
b.swap()
c.swap()
d.swap()
fmt.Println(a)
fmt.Println(b)
fmt.Println(c)
fmt.Println(d)
}
$ go run sample75.go
{1 2}
&{3 4}
{5 6}
&{5 6}
Foo swap! {2 1}
Foo swap! {4 3}
Bar swap! &{6 5}
Bar swap! &{6 5}
{1 2}
&{3 4}
{6 5}
&{6 5}
メソッド swap は構造体のフィールド a, b の値を交換します。Foo のメソッドは、レシーバの型が Foo なので、構造体の値は仮引数 p にコピーされます。したがって、p.a と p.b の値を交換しても、実引数の a, b の値は元のままです。Bar のメソッドは、レシーバの型が *Bar なので、仮引数に渡されるのはポインタです。p.a, p.b の値を交換すると、実引数の値も交換されます。
メソッド swap は、ドット ( . ) の左辺の型が Foo, Bar でも *Foo, *Bar でも呼び出すことができます。どちらの場合でも、Foo のメソッドでは実引数は仮引数にコピーされ、Bar のメソッドの仮引数にはポインタが渡されます。
最後に簡単な例題として「連結リスト (linked list)」というデータ構造を作ってみましょう。連結リストはデータを一方向につなげたデータ構造です。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが連結リストです。下図に連結リストの構造を示します。
(1)変数
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(nil)
└─┘ └─┴─┘ └─┴─┘ └─┴─┘
(2)ヘッダセル
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(nil)
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 : 連結リスト
連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへのポインタを格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば nil）を格納します。そして、図 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 (2) のようにヘッダセルを用意する方法もあります。
連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかります。これが連結リストの短所です。
それではプログラムを作りましょう。最初に連結リストを表す構造体 List とセルを表す構造体 Cell を定義します。次のリストを見てください。
リスト : 連結リストの定義
// セル
type Cell struct {
item int
next *Cell
}
// 連結リスト
type List struct {
top *Cell
}
// セルの生成
func newCell(x int, cp *Cell) *Cell {
newcp := new(Cell)
newcp.item, newcp.next = x, cp
return newcp
}
// 連結リストの生成
func newList() *List {
lst := new(List)
lst.top = new(Cell)
return lst
}
Cell のフィールド item にデータを格納し、next に次のセルへのポインタを格納します。構造体は自分自身を格納することはできませんが、自分自身へのポインタであれば格納することができます。これを「自己参照構造体」といい、Ｃ言語と同じです。
今回は簡単な例題なので、item の型は int とします。ここで空インターフェース (interface{}) を使うと、いろいろなデータ型を格納できるようになります。これは次回以降に詳しく説明する予定です。
次に、セルを使って連結リスト List を作成します。List はセルを保持するフィールド top を用意します。関数 newList で top にヘッダセルをセットします。ヘッダセルの item はダミーで、このプログラムではゼロ値 (0) になります。next もゼロ値 (nil) で初期化されるので、最初は空のリストになります。
あとは、連結リストを操作するメソッドを定義します。連結リストを操作する基本的なメソッドを下表に示します。
| 関数 | 機能 |
|---|---|
| (lst *List) nth(n int) (int, bool) | n 番目の要素を求める |
| (lst *List) insertNth(n, x int) bool | n 番目の位置にデータ x を挿入する |
| (lst *List) deleteNth(n int) bool | n 番目の要素を削除する |
| (lst *List) isEmpty() | 連結リストが空の場合は真を返す |
要素の位置は配列と同様に 0 から数えることにします。位置 n がリストの要素数（長さ）よりも多い場合、nth は 0 と false を, insertNth, deleteNth は false を返すことにします。isEmpty は連結リストが空の場合は true を返し、データがあれば false を返します。
次は、作業用のメソッドとして n 番目のセルを求める処理を作ります。メソッド名は nthCell としました。
リスト : n 番目のセルを求める
func (cp *Cell) nthCell(n int) *Cell {
i := -1
for cp != nil {
if i == n { return cp }
i++
cp = cp.next
}
return nil
}
引数 cp にはヘッダセル top を渡します。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、for ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。
cp1 cp2 cp3
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼→│20│・┼→│30│・┼→
└─┴─┘ └─┴─┘ └─┴─┘
↑ ↑
(1) (2)
(1) cp = cp.next => cp2
(2) cp = cp.next => cp3
図 : セルのたどり方
セルのたどり方は実に簡単です。上図を見てください。セル cp1 の next にはセル cp2 へのポインタが格納されています。変数 cp が cp1 の場合、cp = cp.next とすれば、cp の値はセル cp2 になります (図 (1))。さらに cp = cp.next とすれば、cp の値は cp3 になります (図 (2))。nthCell の場合、for ループでセルをたどっていきますが、途中でセルがなくなった場合、cp の値は nil になるので for ループを終了して nil を返します。
それでは、n 番目の要素を求めるメソッド nth から作りましょう。次のリストを見てください。
リスト : n 番目の要素を求める
func (lst *List) nth(n int) (int, bool) {
cp := lst.top.nthCell(n)
if cp == nil { return 0, false }
return cp.item, true
}
メソッド nthCell を呼び出して n 番目のセルを求めます。cp が nil でなければ、格納されているデータ cp.item と true を返します。cp が nil の場合は 0 と false を返します。
次は、データの挿入を行うメソッド insertNth を作りましょう。データの挿入はセルの next を書き換えることで実現できます。次の図を見てください。セル (1) とセル (2) の間に、セル (3) を挿入します。
top (1) (2)
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼──→│10│・┼─ X ─→│20│・┼→│30│／│
└─┘ └─┴┼┘ └─┴─┘ └─┴─┘
│ (3) ↑
│ ┌─┬─┐│
└→│40│・┼┘
└─┴─┘
セル(1)とセル(2)の間にセル(3)を挿入する場合
図 : データの挿入
セル (1) の後ろにセル (3) を挿入する場合、セル (1) の next にはセル (2) へのポインタがセットされているので、この値をセル (3) の next にセットします。これで、セル (3) とセル (2) がリンクされます。次に、セル (1) の next にセル (3) へのポインタをセットします。これで、セル (1) とセル (2) の間に、セル (3) を挿入することができます。
プログラムは次のようになります。
リスト : データの挿入
func (lst *List) insertNth(n, x int) bool {
cp :=lst.top.nthCell(n - 1)
if cp == nil { return false }
cp.next = newCell(x, cp.next)
return true
}
連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。nthCell で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろに x を挿入します。n が 0 の場合、nthCell はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。
newCell(x, cp.next) で x を格納する新しいセルを生成します。第 2 引数に cp.next を指定することで、新しいセルの後ろに、cp の次のセルを接続することができます。そして、cp.next の値を新しいセルに書き換えます。これで cp の後ろに新しいセルを挿入することができます。最後に true を返します。
次は、データを削除するメソッド deleteNth を作りましょう。データを削除する場合も、セルを付け替えるだけで済ますことができます。上図を見てください。セル (1) の後ろにあるセル (2) を削除する場合、セル (1) の next をセル (3) へのポインタに書き換えればいいのです。セル (3) はセル (2) の next から求めることができます。つまり、セル (1) を保持する変数を cp とすると、セル (3) は cp.next.next で求めることができるのです。
(1) (2) (3)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼Ｘ→│20│・┼→│30│・┼→
└─┴┼┘ └─┴─┘ └─┴─┘
│ ↑
└─────────┘
図 : データの削除:セル(2) を削除する場合
プログラムは次のようになります。
リスト : データの削除
func (lst *List) deleteNth(n int) bool {
cp := lst.top.nthCell(n - 1)
if cp == nil || cp.next == nil { return false }
cp.next = cp.next.next
return true
}
データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。nthCell で n - 1 番目のセルを求めます。次に、削除するセルがあるか cp.next の値をチェックします。値が nil でなければ、cp.next の値を cp.next.next に書き換えるだけです。これでセルを削除することができます。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは実行してみましょう。
リスト : 簡単な実行例
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()
}
}
$ 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
printList は連結リストを表示するメソッドです。正常に動作していますね。
今回はここまでです。次回は構造体の埋め込みについて説明します。
//
// linkedlist.go : 連結リスト
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import "fmt"
// セル
type Cell struct {
item int
next *Cell
}
// 連結リスト
type List struct {
top *Cell
}
// セルの生成
func newCell(x int, cp *Cell) *Cell {
newcp := new(Cell)
newcp.item, newcp.next = x, cp
return newcp
}
// 連結リストの生成
func newList() *List {
lst := new(List)
lst.top = new(Cell)
return lst
}
// n 番目のセルを求める
func (cp *Cell) nthCell(n int) *Cell {
i := -1
for cp != nil {
if i == n { return cp }
i++
cp = cp.next
}
return nil
}
// n 番目の要素を求める
func (lst *List) nth(n int) (int, bool) {
cp := lst.top.nthCell(n)
if cp == nil { return 0, false }
return cp.item, true
}
// データの挿入
func (lst *List) insertNth(n, x int) bool {
cp :=lst.top.nthCell(n - 1)
if cp == nil { return false }
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 }
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()
}
}