## 2020年6月14日日曜日

### Go - Go Packages, Algorithms, and Data Structures - linked list, delete method, insert method

Go Systems Programming: Master Linux and Unix system level programming with Go (Mihalis Tsoukalos(著)、Packt Publishing)のChapter 4(Go Packages, Algorithms, and Data Structures)、Exercises 6.の解答を求めてみる。

コード

```package main

import (
"fmt"
"math/rand"
"time"
)

type node struct {
value int
next  *node
}

func (n *node) add(v int) {
if v == n.value {
fmt.Println("Node already exists:", v)
} else if n.next == nil {
n.next = &node{v, nil}
} else {
}
}
func (n *node) delete(v int) {
if n == nil {
return
}
if v == n.value {
if n.next == nil {
n = nil
} else {
*n = *n.next
}
} else {
n.next.delete(v)
}
}
func (n *node) insert(m, v int) {
if n.next == nil {
n.next = &node{v, nil}
} else if m == 1 {
t := *n.next
*n.next = node{v, &t}
} else {
n.next.insert(m-1, v)
}
}

type root struct {
*node
}

func newRoot() *root {
return &root{nil}
}
func (r *root) add(v int) {
if r.node == nil {
r.node = &node{v, nil}
} else {
}
}

func (r *root) delete(v int) {
if r.node == nil {
return
}
r.node.delete(v)
}
func (r *root) insert(n, v int) {
if r.node == nil {
*r.node = node{v, nil}
} else if n == 0 {
t := *r.node
*r.node = node{v, &t}
} else {
r.node.insert(n, v)
}
}
func (r *root) traverse() {
if r.node == nil {
fmt.Println("-> Empty list!")
return
}
n := r.node
for n != nil {
fmt.Printf("%d -> ", n.value)
n = n.next
}
fmt.Println()
}
func main() {
rand.Seed(time.Now().UnixNano())

r := newRoot()
r.traverse()
for i := 0; i < 20; i++ {
v := rand.Intn(10)
r.traverse()
}
for i := 0; i < 10; i++ {
v := rand.Intn(10)
fmt.Printf("delete(%v)\n", v)
r.delete(v)
r.traverse()
}
for i := 0; i < 10; i++ {
n := rand.Intn(10)
v := rand.Intn(10)
fmt.Printf("insert(%v, %v)\n", n, v)
r.insert(n, v)
r.traverse()
}
}
```

```% go build linkedlist.go
-> Empty list!
6 ->
6 -> 5 ->
6 -> 5 -> 4 ->
6 -> 5 -> 4 -> 0 ->
6 -> 5 -> 4 -> 0 -> 1 ->
6 -> 5 -> 4 -> 0 -> 1 -> 9 ->
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 ->
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 ->
Node already exists: 5
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 ->
Node already exists: 6
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 ->
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 ->
Node already exists: 1
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 ->
Node already exists: 4
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 ->
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 ->
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 ->
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 ->
Node already exists: 1
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 ->
Node already exists: 5
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 ->
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 ->
Node already exists: 1
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 ->
delete(2)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 3 -> 7 ->
delete(7)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 3 -> 7 ->
delete(6)
5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 3 -> 7 ->
delete(9)
5 -> 4 -> 0 -> 1 -> 8 -> 3 -> 7 ->
delete(8)
5 -> 4 -> 0 -> 1 -> 3 -> 7 ->
delete(8)
5 -> 4 -> 0 -> 1 -> 3 -> 7 ->
delete(3)
5 -> 4 -> 0 -> 1 -> 7 ->
delete(4)
5 -> 0 -> 1 -> 7 ->
delete(6)
5 -> 0 -> 1 -> 7 ->
delete(3)
5 -> 0 -> 1 -> 7 ->
insert(3, 0)
5 -> 0 -> 1 -> 0 -> 7 ->
insert(8, 6)
5 -> 0 -> 1 -> 0 -> 7 -> 6 ->
insert(3, 3)
5 -> 0 -> 1 -> 3 -> 0 -> 7 -> 6 ->
insert(6, 3)
5 -> 0 -> 1 -> 3 -> 0 -> 7 -> 3 -> 6 ->
insert(3, 9)
5 -> 0 -> 1 -> 9 -> 3 -> 0 -> 7 -> 3 -> 6 ->
insert(6, 2)
5 -> 0 -> 1 -> 9 -> 3 -> 0 -> 2 -> 7 -> 3 -> 6 ->
insert(7, 1)
5 -> 0 -> 1 -> 9 -> 3 -> 0 -> 2 -> 1 -> 7 -> 3 -> 6 ->
insert(5, 6)
5 -> 0 -> 1 -> 9 -> 3 -> 6 -> 0 -> 2 -> 1 -> 7 -> 3 -> 6 ->
insert(6, 5)
5 -> 0 -> 1 -> 9 -> 3 -> 6 -> 5 -> 0 -> 2 -> 1 -> 7 -> 3 -> 6 ->
insert(3, 7)
5 -> 0 -> 1 -> 7 -> 9 -> 3 -> 6 -> 5 -> 0 -> 2 -> 1 -> 7 -> 3 -> 6 ->
-> Empty list!
2 ->
Node already exists: 2
2 ->
2 -> 8 ->
2 -> 8 -> 1 ->
2 -> 8 -> 1 -> 0 ->
Node already exists: 2
2 -> 8 -> 1 -> 0 ->
2 -> 8 -> 1 -> 0 -> 5 ->
Node already exists: 1
2 -> 8 -> 1 -> 0 -> 5 ->
Node already exists: 2
2 -> 8 -> 1 -> 0 -> 5 ->
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 ->
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 5
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 0
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 2
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
Node already exists: 5
2 -> 8 -> 1 -> 0 -> 5 -> 7 ->
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 6 ->
Node already exists: 7
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 6 ->
delete(9)
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 6 ->
delete(0)
2 -> 8 -> 1 -> 5 -> 7 -> 6 ->
delete(3)
2 -> 8 -> 1 -> 5 -> 7 -> 6 ->
delete(2)
8 -> 1 -> 5 -> 7 -> 6 ->
delete(5)
8 -> 1 -> 7 -> 6 ->
delete(7)
8 -> 1 -> 6 ->
delete(1)
8 -> 6 ->
delete(4)
8 -> 6 ->
delete(2)
8 -> 6 ->
delete(3)
8 -> 6 ->
insert(7, 8)
8 -> 6 -> 8 ->
insert(9, 6)
8 -> 6 -> 8 -> 6 ->
insert(0, 5)
5 -> 8 -> 6 -> 8 -> 6 ->
insert(7, 3)
5 -> 8 -> 6 -> 8 -> 6 -> 3 ->
insert(5, 4)
5 -> 8 -> 6 -> 8 -> 6 -> 4 -> 3 ->
insert(4, 1)
5 -> 8 -> 6 -> 8 -> 1 -> 6 -> 4 -> 3 ->
insert(7, 0)
5 -> 8 -> 6 -> 8 -> 1 -> 6 -> 4 -> 0 -> 3 ->
insert(5, 4)
5 -> 8 -> 6 -> 8 -> 1 -> 4 -> 6 -> 4 -> 0 -> 3 ->
insert(2, 6)
5 -> 8 -> 6 -> 6 -> 8 -> 1 -> 4 -> 6 -> 4 -> 0 -> 3 ->
insert(5, 9)
5 -> 8 -> 6 -> 6 -> 8 -> 9 -> 1 -> 4 -> 6 -> 4 -> 0 -> 3 ->
%
```