こんにちは。KOUKIです。
とあるWeb系企業で、Goエンジニアをやっています。
今回は、LinkedListを自作してみたので、紹介します。
<目次>
LinkedListについて
下記の画像を見てください。
A * B * C * D はそれぞれ、データのNodeを表しており、Prev, Next, Value(Aとか)を持っています。
それぞれLinkで繋がっており、このLinkを伝って各Nodeにアクセスできる、そんなコードを実装したいと思います。
Listパッケージを使えば?
実は、Go言語の組み込みパッケージであるlistパッケージを使えば、プログラムを自作する必要はありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package main import ( "container/list" "fmt" ) func main() { // Create a new list and put some numbers in it. l := list.New() e4 := l.PushBack("D") e1 := l.PushFront("A") l.InsertBefore("C", e4) l.InsertAfter("B", e1) for e := l.Front(); e != nil; e = e.Next() { fmt.Println(e.Value) } fmt.Println("-------------") for e := l.Back(); e != nil; e = e.Prev() { fmt.Println(e.Value) } } |
|
1 2 3 4 5 6 7 8 9 10 11 |
Output: A B C D ------------- D C B A |
しかし、アルゴリズムを学ぶことは綺麗なコードを書くことにつながるので、自力で実装できるようにしておいた方がいいと思います^^
実装
早速、実装しましょう。
モデルの定義
必要なモデルは、LinkedListとNodeですね。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package main import "fmt" type LinkedList struct { head *Node tail *Node } type Node struct { value string next *Node prev *Node } func NewNode(value string) *Node { return &Node{ value: value, next: nil, prev: nil, } } |
Nodeは先程の例で言うならA/B/C/Dです。LinkedListはNodeを繋げるために存在します。
Node – Next/Prevメソッド
Nodeのメソッドとして、Next/Prevを実装しましょう。
|
1 2 3 4 5 6 7 |
func (n *Node) Next() *Node { return n.next } func (n *Node) Prev() *Node { return n.prev } |
LinkedList – First/Last/Pushメソッド
LinkedListのメソッドとして、First/Last/Pushを実装しましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
func (l *LinkedList) First() *Node { return l.head } func (l *LinkedList) Last() *Node { return l.tail } func (l *LinkedList) Push(value string) { node := NewNode(value) if l.head == nil { l.head = node } else { l.tail.next = node node.prev = l.tail } l.tail = node } |
Pushが難しいかもしれませんね。
一番最初にNodeを追加した時は、当然headは空です。そのため、headにNodeを追加します。また、末尾(tail)もそのNodeにします。
2番目以降のNodeは、前回追加したNodeのtailのnextがそのNodeになるわけですから「l.tail.next」に格納します。そして、そのNodeのPrevは当然前回追加したNodeを指す必要があるので「node.prev」に前回作成したNodeを示す「l.tail」を追加しているわけです。
検証
main関数を追加して、挙動を確認しましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
func main() { l := NewLinkedList() l.Push("A") l.Push("B") l.Push("C") l.Push("D") n := l.First() for { println(n.value) n = n.Next() if n == nil { break } } fmt.Println("-------------") n = l.Last() for { println(n.value) n = n.Prev() if n == nil { break } } } |
|
1 2 3 4 5 6 7 8 9 10 |
$ go run main.go A B C D ------------- D C B A |
完璧ですね!
おわりに
いかがでしょうか？
自分で綺麗なアルゴリズムを実装できるようになると、一段階上のエンジニアになれると思いませんか?
絶対に無駄にならないと思うので、ぜひチャレンジしてみてください!
それでは、また!
Go記事まとめ
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
package main import "fmt" type LinkedList struct { head *Node tail *Node } func NewLinkedList() *LinkedList { return &LinkedList{} } func (l *LinkedList) First() *Node { return l.head } func (l *LinkedList) Last() *Node { return l.tail } func (l *LinkedList) Push(value string) { node := NewNode(value) // ヘッダがからの場合は一番最初のNodeということ if l.head == nil { l.head = node } else { l.tail.next = node node.prev = l.tail } l.tail = node } type Node struct { value string next *Node prev *Node } func NewNode(value string) *Node { return &Node{ value: value, next: nil, prev: nil, } } func (n *Node) Next() *Node { return n.next } func (n *Node) Prev() *Node { return n.prev } func main() { l := NewLinkedList() l.Push("A") l.Push("B") l.Push("C") l.Push("D") n := l.First() for { println(n.value) n = n.Next() if n == nil { break } } fmt.Println("-------------") n = l.Last() for { println(n.value) n = n.Prev() if n == nil { break } } } |
にほんブログ村
コメントを残す
コメントを投稿するにはログインしてください。