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
楽天ブックス紀伊國屋書店

開発環境

macOS Catalina - Apple (OS)
Emacs (Text Editor)
Windows 10 Pro (OS)
Visual Studio Code (Text Editor)
Go (プログラミング言語)

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 {
  n.next.add(v)
 }
}
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 {
  r.node.add(v)
 }
}

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)
  fmt.Printf("add(%v)\n", v)
  r.add(v)
  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()
 }
}

入出力結果(Zsh、PowerShell、Terminal)

% go build linkedlist.go
% ./linkedlist          
-> Empty list!
add(6)
6 -> 
add(5)
6 -> 5 -> 
add(4)
6 -> 5 -> 4 -> 
add(0)
6 -> 5 -> 4 -> 0 -> 
add(1)
6 -> 5 -> 4 -> 0 -> 1 -> 
add(9)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 
add(8)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 
add(8)
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 
add(5)
Node already exists: 5
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 
add(6)
Node already exists: 6
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 
add(2)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 
add(1)
Node already exists: 1
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 
add(4)
Node already exists: 4
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 
add(8)
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 
add(3)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 
add(7)
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 -> 
add(1)
Node already exists: 1
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 -> 
add(5)
Node already exists: 5
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 -> 
add(8)
Node already exists: 8
6 -> 5 -> 4 -> 0 -> 1 -> 9 -> 8 -> 2 -> 3 -> 7 -> 
add(1)
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 -> 
% ./linkedlist
-> Empty list!
add(2)
2 -> 
add(2)
Node already exists: 2
2 -> 
add(8)
2 -> 8 -> 
add(1)
2 -> 8 -> 1 -> 
add(0)
2 -> 8 -> 1 -> 0 -> 
add(2)
Node already exists: 2
2 -> 8 -> 1 -> 0 -> 
add(5)
2 -> 8 -> 1 -> 0 -> 5 -> 
add(1)
Node already exists: 1
2 -> 8 -> 1 -> 0 -> 5 -> 
add(2)
Node already exists: 2
2 -> 8 -> 1 -> 0 -> 5 -> 
add(8)
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 
add(7)
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(5)
Node already exists: 5
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(8)
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(8)
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(0)
Node already exists: 0
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(2)
Node already exists: 2
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(8)
Node already exists: 8
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(5)
Node already exists: 5
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 
add(6)
2 -> 8 -> 1 -> 0 -> 5 -> 7 -> 6 -> 
add(7)
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 -> 
%

Kamimura's blog

2020年6月14日日曜日

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

0 コメント:

コメントを投稿