【Go】Linked List (連結リスト)

# Goでプログラミングの基礎を学ぶシリーズ
スクールでは教えてくれないプログラミングの基礎、**データ構造とアルゴリズム**をGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単に説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。

|  | タイトル |
|------|---------|
| #0 | [はじめに (環境構築と勉強方法)](https://qiita.com/miyyuk/items/0b959774a2e436f087c0) |
| #1 | [Pointer, Array, String (ポインタと配列と文字列と)](https://qiita.com/miyyuk/items/75fad6c02b76354fa49d) |
| #2 | [File operations (ファイル操作)](https://qiita.com/miyyuk/items/641faf682e09709727af) |
| #3 | Linked List (連結リスト) **☜ here** |
| #4 | [Stack & Queue (スタックとキュー)](https://qiita.com/miyyuk/items/a188def21c31367330f3) |
| #5 | [Search algorithms (探索アルゴリズム)](https://qiita.com/miyyuk/items/91920dee5151e9c4c43e) |
| #6 | [Tree (木構造)](https://qiita.com/miyyuk/items/a11c22a62bb95c1996ba) |
| #7 | [Sorting algorithms (ソートアルゴリズム)](https://qiita.com/miyyuk/items/85c2ed8176e9bdf7e677)|
| #8 | [String pattern matching algorithms (文字列探索アルゴリズム)](https://qiita.com/miyyuk/items/bce37f7f8c24b48cfd3f) |

今回は**#3 Linked List (連結リスト)**です。

# Linked List とは
>連結リストとは、データ構造の一種であるリストの中で、自分の次、および、前の要素を示す情報（リンク情報）を持つことで、要素を連結（リンク）させたリストのことである。
リストは、データの要素を順番に並べて扱うデータ構造のことである。
次の要素へのリンクしか持たない連結リストのことを単方向（一方向）リスト、次と前への要素へのリンクを持つものを双方向リストと言うこともある。
引用: [IT用語辞典バイナリ](https://www.weblio.jp/content/LinkedList)

これだけ聞いて、あぁそういうことね！となるプログラミング初心者は少ないと思います。
英語の記事の方がわかりやすいものが多いので参考にしていただきたいのですが、簡単に図で説明します。

https://betterprogramming.pub/an-introduction-to-d1957df2f406

https://www.youtube.com/watch?v=NobHlGUjV3g

![スクリーンショット 2021-04-10 22.59.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653268/10870524-fb06-f938-45dd-d8283efcb5cf.png)

`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 (スタックとキュー)](https://qiita.com/miyyuk/items/a188def21c31367330f3#-exercise-1)で取り扱っていますので、合わせてご参考ください

リストを作りたいだけなら、配列を使ったらいいじゃない。わざわざ`Node`を連ねる必要なくない？
って思いませんか？
筆者は思いました笑

`Array`(配列)と`Linked List`には下図のような違いがあります。

![スクリーンショット 2021-04-11 10.12.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653268/b732182e-a4ca-1630-c126-f6a1f483c648.png)

`Linked List`は要素同士が隣り合っている必要がありません。
そのため、リストに要素を追加したり削除したりする場合は、リンク情報を書き換えるだけなので、`Linked List`の方が短時間で処理できます。
反対に、特定の要素を検索するのは、先頭の`Node`から順番に検索していく必要があるので、`index`がある`Array`の方が短時間で処理できます。
参考: 
[LinkedList と ArrayList の使い分け方](https://qiita.com/BumpeiShimada/items/522798a380dc26c50a50)
[Summary - Linked List (LeetCode)](https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1230/)

では、Exerciseで、`Linked List`の要素追加、削除、検索をやっていきましょう。

### 💻 Exercise
名前、電話番号、メールアドレスが記載されたアドレス帳を想定します。

1. `Singly Linked List`でアドレス帳を作りましょう
1. `List`の最後尾にアドレスを追加する`function`を作りましょう
1. `List`にあるアドレスを表示する`function`を作りましょう
1. `List`からアドレスを削除する`function`を作りましょう

☟ 解答例

```golang
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]](https://medium.com/since-i-want-to-start-blog-that-looks-like-men-do/%E5%88%9D%E5%BF%83%E8%80%85%E3%81%AB%E9%80%81%E3%82%8A%E3%81%9F%E3%81%84interface%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9-golang-48eba361c3b4)
[【Go】基本文法⑥(インターフェース)](https://qiita.com/k-penguin-sato/items/885a61d819cc431304f5)

`Traverse`と`GetAddress`は`List`を`root`から順番に辿っていき、要素を出力したり、取得したりしています。
`Insert`と`Remove`は図を見た方がわかりやすいと思いますので、以下詳説です。

#### Insert (要素の追加)
図①
![スクリーンショット 2021-04-11 14.34.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653268/a6529cc0-aa99-7012-a2de-9e83c9ce17ca.png)
Exerciseでは`cur`が最後尾の`Node`ですが、図では任意の`Node`にしています。
`Insert`する`node.next`は`cur.next`になり、`cur.next`は`node`になります。
最後に`cur`を`Insert`した`node`に変更します。

```golang
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 (要素の削除)
図②
![スクリーンショット 2021-04-11 14.31.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/653268/fb23d673-de8d-c0f6-f6d1-d346796588b5.png)
`Remove`する`Node`の前の`Node`の`next`を、`Remove`する`Node`の次の`Node`にします。

先頭の`Node`を削除する場合はもっと簡単で、`root`がリンクしている`Node`を`root.next`に変えればよいだけです。

```golang
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 (スタックとキュー)**です。