Goメモ-501 (シンプルな循環連結リスト)(CircularLinkedList)

関連記事

Goメモ-498 (シンプルなラッチ)(CountdownLatch, CountdownEvent) - いろいろ備忘録日記

Goメモ-499 (シンプルなゲート)(Gate, カウント１のラッチ) - いろいろ備忘録日記

Goメモ-500 (シンプルな循環式バリア)(CyclicBarrier) - いろいろ備忘録日記

GitHub - devlights/blog-summary: ブログ「いろいろ備忘録日記」のまとめ

概要

以下、自分用のメモです。

前回、ラッチとゲートとサイクリックバリアについてのサンプルをメモしたので、ついでに循環連結リストもメモ。

サンプル

circular.go

package main

import (
    "fmt"
    "strings"
)

type (
    // Node は、連結リストのノートを表します.
    Node[T any] struct {
        Value T        // 値
        Next  *Node[T] // 次要素
    }

    // Circular は、循環連結リストを表します.
    // Capacityを超えた場合、最も古い要素から上書きされます.
    Circular[T any] struct {
        Head     *Node[T] // 先頭
        Tail     *Node[T] // 末尾
        Size     int      // 要素数
        Capacity int      // キャパシティ
    }
)

// String は、Nodeの文字列表現を返します.
func (me *Node[T]) String() string {
    if me == nil {
        return ""
    }

    if me.Next == nil {
        return fmt.Sprintf("(v:%v,n:nil)", me.Value)
    }

    return fmt.Sprintf("(v:%v,n:%v)", me.Value, me.Next.Value)
}

// NewCircular は、指定されたキャパシティを持つ[*Circular]を生成します.
func NewCircular[T any](capacity int) *Circular[T] {
    if capacity <= 0 {
        panic("capacity must be positive")
    }

    return &Circular[T]{
        Head:     nil,
        Tail:     nil,
        Size:     0,
        Capacity: capacity,
    }
}

// Add は、末尾に新しい要素を追加します.
func (me *Circular[T]) Add(value T) {
    var (
        n = &Node[T]{Value: value}
    )

    if me.Head == nil {
        me.Head = n
        me.Tail = n
        me.Size = 1

        return
    }

    if me.Size < me.Capacity {
        me.Tail.Next = n
        me.Tail = n
        me.Size++
    } else {
        me.Head = me.Head.Next
        me.Tail.Next = n
        me.Tail = n
    }
}

// Delete は、指定した値に合致する最初のノードを削除します.
//
// 型パラメータでは、comparableかどうかが判別できませんので、比較判定関数を指定する必要があります。
func (me *Circular[T]) Delete(value T, equal func(v1, v2 T) bool) bool {
    if me.Head == nil {
        return false
    }

    if equal(me.Head.Value, value) {
        me.Head = me.Head.Next
        me.Size--

        if me.Size == 0 {
            me.Tail = nil
        }

        return true
    }

    var (
        current = me.Head
    )
    for current.Next != nil {
        if equal(current.Next.Value, value) {
            current.Next = current.Next.Next // 削除対象を抜いて要素を詰める

            if current.Next == nil {
                me.Tail = current
            }

            me.Size--

            return true
        }

        current = current.Next
    }

    return false
}

// ToSlice は、要素の値をスライスにして返します.
func (me *Circular[T]) ToSlice() []T {
    var (
        result  = make([]T, 0, me.Size)
        current = me.Head
    )

    for range me.Size {
        result = append(result, current.Value)
        current = current.Next
    }

    return result
}

// String は、[*Circular]の文字列表現を返します.
func (me *Circular[T]) String() string {
    if me.Head == nil {
        return "[]"
    }

    var (
        sb      strings.Builder
        current = me.Head
    )

    sb.WriteString("[")
    {
        for i := 0; i < me.Size; i++ {
            if i > 0 {
                sb.WriteString(" -> ")
            }

            sb.WriteString(fmt.Sprintf("%v", current.Value))
            current = current.Next
        }
    }
    sb.WriteString(" ->]")

    return sb.String()
}

main.go

package main

import (
    "context"
    "fmt"
    "log"
)

func init() {
    log.SetFlags(0)
}

func main() {
    var (
        rootCtx          = context.Background()
        mainCtx, mainCxl = context.WithCancel(rootCtx)
        err              error
    )
    defer mainCxl()

    if err = run(mainCtx); err != nil {
        log.Fatal(err)
    }
}

func run(_ context.Context) error {
    var (
        circular = NewCircular[string](5)
    )

    //
    // Add
    //
    title("Add")
    {
        for _, r := range "helloworld" {
            circular.Add(string(r))
            log.Println(circular)
        }
    }

    //
    // Iterate (slice)
    //
    title("Iterate (slice)")
    {
        for i, v := range circular.ToSlice() {
            log.Printf("%02d: %v", i, v)
        }
    }

    //
    // Iterate (node)
    //
    title("Iterate (node)")
    {
        if circular.Head != nil {
            for n := circular.Head; ; n = n.Next {
                log.Println(n)

                if n == circular.Tail {
                    break
                }
            }
        }
    }

    //
    // Delete
    //
    title("Delete")
    {
        var (
            fn = func(v1, v2 string) bool {
                return v1 == v2
            }
            deletes = []string{"d", "w", "r"}
        )
        for _, d := range deletes {
            if ok := circular.Delete(d, fn); !ok {
                return fmt.Errorf("Delete() returns false (%v)", d)
            }

            log.Println(circular)
        }
    }

    return nil
}

func title(m string) {
    log.Printf("----------[%s]----------", m)
}

Taskfile.yml

# https://taskfile.dev

version: '3'

tasks:
  default:
    cmds:
      - go run .

実行

$ task
task: [default] go run .
----------[Add]----------
[h ->]
[h -> e ->]
[h -> e -> l ->]
[h -> e -> l -> l ->]
[h -> e -> l -> l -> o ->]
[e -> l -> l -> o -> w ->]
[l -> l -> o -> w -> o ->]
[l -> o -> w -> o -> r ->]
[o -> w -> o -> r -> l ->]
[w -> o -> r -> l -> d ->]
----------[Iterate (slice)]----------
00: w
01: o
02: r
03: l
04: d
----------[Iterate (node)]----------
(v:w,n:o)
(v:o,n:r)
(v:r,n:l)
(v:l,n:d)
(v:d,n:nil)
----------[Delete]----------
[w -> o -> r -> l ->]
[o -> r -> l ->]
[o -> l ->]

参考情報

github.com

Goのおすすめ書籍

初めてのGo言語 ―他言語プログラマーのためのイディオマティックGo実践ガイド

実用 Go言語 ―システム開発の現場で知っておきたいアドバイス

Go言語による並行処理

Go言語 100Tips ありがちなミスを把握し、実装を最適化する impress top gearシリーズ

Goならわかるシステムプログラミング 第2版

効率的なGo ―データ指向によるGoアプリケーションの性能最適化

---

過去の記事については、以下のページからご参照下さい。

• ブログ 「いろいろ備忘録日記」の記事まとめ | ブログ「いろいろ備忘録日記」のまとめ

サンプルコードは、以下の場所で公開しています。

• GitHub - devlights/try-golang: This is my TUTORIAL project for golang.
• GitHub - devlights/try-python: This is my TUTORIAL project for Python.
• GitHub - devlights/try-csharp: This is my TUTORIAL project for C#.