Goでプログラミングの基礎を学ぶシリーズ
スクールでは教えてくれないプログラミングの基礎、データ構造とアルゴリズムをGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単に説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。
| タイトル | |
|---|---|
| #0 | はじめに (環境構築と勉強方法) |
| #1 | Pointer, Array, String (ポインタと配列と文字列と) |
| #2 | File operations (ファイル操作) |
| #3 | Linked List (連結リスト) ☜ here |
| #4 | Stack & Queue (スタックとキュー) |
| #5 | Search algorithms (探索アルゴリズム) |
| #6 | Tree (木構造) |
| #7 | Sorting algorithms (ソートアルゴリズム) |
| #8 | String pattern matching algorithms (文字列探索アルゴリズム) |
今回は#3 Linked List (連結リスト)です。
Linked List とは
連結リストとは、データ構造の一種であるリストの中で、自分の次、および、前の要素を示す情報（リンク情報）を持つことで、要素を連結（リンク）させたリストのことである。
リストは、データの要素を順番に並べて扱うデータ構造のことである。
次の要素へのリンクしか持たない連結リストのことを単方向（一方向）リスト、次と前への要素へのリンクを持つものを双方向リストと言うこともある。
引用: IT用語辞典バイナリ
これだけ聞いて、あぁそういうことね！となるプログラミング初心者は少ないと思います。
英語の記事の方がわかりやすいものが多いので参考にしていただきたいのですが、簡単に図で説明します。
Singly Linked Listで補足すると、
root（またはheadであることもある）が先頭のNodeへの情報を持っている。
先頭のNodeは自身のデータと、次のNodeへの情報を持っている。
2番目のNodeは自身のデータと、次のNodeへの情報を持っている、、、といった具合に、Nodeを連ねていきます。
上図でいうと、rootはListの先頭がdata: 6のNodeであるという情報だけ持っています。
先頭のNodeは自身のデータがdata: 6であることと、次のNodeがdata: 5のNodeであるという情報を持っているといった感じです。
つまり、rootから順番にNodeを辿っていけば、Listの要素全てにアクセスすることができます。
Doubly Linked Listは次のNodeの情報だけでなく、前のNodeの情報も持っているListです。
※Doubly Linked Listの例題は次の#4 Stack & Queue (スタックとキュー)で取り扱っていますので、合わせてご参考ください
リストを作りたいだけなら、配列を使ったらいいじゃない。わざわざNodeを連ねる必要なくない？
って思いませんか？
筆者は思いました笑
Array(配列)とLinked Listには下図のような違いがあります。
Linked Listは要素同士が隣り合っている必要がありません。
そのため、リストに要素を追加したり削除したりする場合は、リンク情報を書き換えるだけなので、Linked Listの方が短時間で処理できます。
反対に、特定の要素を検索するのは、先頭のNodeから順番に検索していく必要があるので、indexがあるArrayの方が短時間で処理できます。
参考:
LinkedList と ArrayList の使い分け方
Summary - Linked List (LeetCode)
では、Exerciseで、Linked Listの要素追加、削除、検索をやっていきましょう。
💻 Exercise
名前、電話番号、メールアドレスが記載されたアドレス帳を想定します。
-
Singly Linked Listでアドレス帳を作りましょう -
Listの最後尾にアドレスを追加するfunctionを作りましょう -
Listにあるアドレスを表示するfunctionを作りましょう -
Listからアドレスを削除するfunctionを作りましょう
☟ 解答例
package main
import "fmt"
type Address struct {
name string
phone_number string
email_address string
}
type Node struct {
addr *Address
next *Node
}
type AddressList struct {
root *Node
len int
}
type AddressListI interface {
Insert(cur *Node, name, phone_number, email_address string) *Node
GetAddress(n int) *Node
Remove(n int, cur *Node) (*Node, error)
Traverse()
}
var _ AddressListI = &AddressList{}
// ListにAddressを追加
func (a *AddressList) Insert(cur *Node, name, phone_number, email_address string) *Node {
address := &Address{
name: name,
phone_number: phone_number,
email_address: email_address,
}
var node *Node = &Node{addr: address}
// 図① 参照
if a.len != 0 {
node.next = cur.next // Insert する Node の next を cur の next にする
cur.next = node // cur の next を Insert する Node にする
cur = cur.next // cur を Insert した Node にする
} else { // Listが空のときは、 root を Insert したい Node にすればよい
a.root = node
cur = a.root
}
a.len++
return cur
}
// n 番目の Node を取得
func (a *AddressList) GetAddress(n int) *Node {
if n > a.len { // Node が存在しないので、 nil を return
return nil
}
ptr := a.root
for i := 1; i < n; i++ { // n 番目の Node まで、 root から辿っていく
ptr = ptr.next
}
return ptr
}
// n 番目の Node を List から削除
func (a *AddressList) Remove(n int, cur *Node) (*Node, error) {
if a.len == 0 {
return cur, fmt.Errorf("List is empty")
}
target := a.GetAddress(n) // 削除する Node を取得
if target == nil {
return cur, fmt.Errorf("Address not found")
}
// 図② 参照
if n > 1 {
prev := a.GetAddress(n - 1) // 削除する Node の前の Node を取得
prev.next = target.next // 削除する Node の前の Node の next を、削除する Node の次の Node にする
if n == a.len { // 最後の Node を削除する場合、 cur を最後の Node の前の Node にする
cur = prev
}
} else {
a.root = target.next // 最初の Node を削除する場合、 root を削除する Node の次の Nodeに変更する
}
a.len--
return cur, nil
}
// List の要素を全て表示
func (a *AddressList) Traverse() {
if a.len == 0 {
fmt.Println("List is empty")
}
fmt.Printf("Size of AddressList: %d\n", a.len)
ptr := a.root
for i := 1; i <= a.len; i++ {
fmt.Printf("%d name: %s, phone_number: %s, email_address: %s\n", i, ptr.addr.name, ptr.addr.phone_number, ptr.addr.email_address)
ptr = ptr.next
}
}
func main() {
var addressList *AddressList = &AddressList{} // AddressList を初期化
fmt.Println("\n~~Init AddressList~~")
addressList.Traverse()
var cur *Node = &Node{} // current Node を初期化
cur = addressList.Insert(cur, "Sakura", "090-1234-5678", "sakura@example.com")
cur = addressList.Insert(cur, "Kaede", "080-1234-5678", "kaede@example.com")
cur = addressList.Insert(cur, "Yuzu", "070-1234-5678", "yuzu@example.com")
fmt.Println("\n~~After Insert Addresses~~")
addressList.Traverse()
cur, err := addressList.Remove(2, cur)
if err != nil {
fmt.Println(err.Error())
}
fmt.Println("\n~~After Remove Address~~")
addressList.Traverse()
}
☟ 実行結果
~~Init AddressList~~
List is empty
Size of AddressList: 0
~~After Insert Addresses~~
Size of AddressList: 3
1 name: Sakura, phone_number: 090-1234-5678, email_address: sakura@example.com
2 name: Kaede, phone_number: 080-1234-5678, email_address: kaede@example.com
3 name: Yuzu, phone_number: 070-1234-5678, email_address: yuzu@example.com
~~After Remove Address~~
Size of AddressList: 2
1 name: Sakura, phone_number: 090-1234-5678, email_address: sakura@example.com
2 name: Yuzu, phone_number: 070-1234-5678, email_address: yuzu@example.com
interfaceを使って実装しています。
interfaceの説明をすると横道に逸れてしまうので、わからない方は、以下を参考にしてください。
参考:
初心者に送りたいinterfaceの使い方[Golang]
【Go】基本文法⑥(インターフェース)
TraverseとGetAddressはListをrootから順番に辿っていき、要素を出力したり、取得したりしています。
InsertとRemoveは図を見た方がわかりやすいと思いますので、以下詳説です。
Insert (要素の追加)
図①
Exerciseではcurが最後尾のNodeですが、図では任意のNodeにしています。
Insertするnode.nextはcur.nextになり、cur.nextはnodeになります。
最後にcurをInsertしたnodeに変更します。
func (a *AddressList) Insert(cur *Node, name, phone_number, email_address string) *Node {
address := &Address{
name: name,
phone_number: phone_number,
email_address: email_address,
}
var node *Node = &Node{addr: address}
// 図① 参照
if a.len != 0 {
node.next = cur.next // Insert する Node の next を cur の next にする
cur.next = node // cur の next を Insert する Node にする
cur = cur.next // cur を Insert した Node にする
} else { // Listが空のときは、 root を Insert したい Node にすればよい
a.root = node
cur = a.root
}
a.len++
return cur
}
Remove (要素の削除)
図②
RemoveするNodeの前のNodeのnextを、RemoveするNodeの次のNodeにします。
先頭のNodeを削除する場合はもっと簡単で、rootがリンクしているNodeをroot.nextに変えればよいだけです。
func (a *AddressList) Remove(n int, cur *Node) (*Node, error) {
if a.len == 0 {
return cur, fmt.Errorf("List is empty")
}
target := a.GetAddress(n) // 削除する Node を取得
if target == nil {
return cur, fmt.Errorf("Address not found")
}
// 図② 参照
if n > 1 {
prev := a.GetAddress(n - 1) // 削除する Node の前の Node を取得
prev.next = target.next // 削除する Node の前の Node の next を、削除する Node の次の Node にする
if n == a.len { // 最後の Node を削除する場合、 cur を最後の Node の前の Node にする
cur = prev
}
} else {
a.root = target.next // 最初の Node を削除する場合、 root を削除する Node の次の Nodeに変更する
}
a.len--
return cur, nil
}
おわりに
Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！
説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。
株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。
未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！
絶賛エンジニア募集中です！
Wantedly ▶︎ https://www.wantedly.com/projects/324177
Green ▶︎ https://www.green-japan.com/job/82003
次回は、データ構造とアルゴリズム#4 Stack & Queue (スタックとキュー)です。