Goでのリンクリストデータ構造の分析と実装
リンクリストは配列に似たデータ構造を提供しますが、リストの中央に要素を挿入することは、現在の位置の後にすべての要素をシフトする必要がある配列に挿入する場合と比較して、非常に安価であるという大きな利点があります。
配列はすべての要素を同じメモリブロックに並べて保持しますが、リンクリストには、次の要素へのポインタを格納することにより、メモリの周囲に散在する要素を含めることができます。
一方、配列に比べて不利な点は、リストの途中で要素を選択する場合、そのアドレスがわからないため、リストの最初から始めて、リストを次のように繰り返す必要があることです。私たちはそれを見つけます。
実装
リンクリストはこれらの方法を提供します：
Append(t)リンクリストの最後にアイテムtを追加しますInsert(i, t)位置iにアイテムtを追加しますRemoveAt(i)位置iのノードを削除しますIndexOf()アイテムtの位置を返しますIsEmpty()リストが空の場合はtrueを返しますSize()リンクリストのサイズを返しますString()リストの文字列表現を返しますHead()最初のノードを返すので、それを繰り返すことができます
作成しますItemLinkedListジェネリック型、並行性セーフ、を使用して任意の型を含むリンクリストを生成できますgenny、タイプ固有のリンクリスト実装を作成し、データを含む実際の値固有のデータ構造をカプセル化します。
// Package linkedlist creates a ItemLinkedList data structure for the Item type
package linkedlist
import (
“fmt”
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Item the type of the linked list
type Item generic.Type
// Node a single node that composes the list
type Node struct {
content Item
next *Node
}
// ItemLinkedList the linked list of Items
type ItemLinkedList struct {
head *Node
size int
lock sync.RWMutex
}
// Append adds an Item to the end of the linked list
func (ll *ItemLinkedList) Append(t Item) {
ll.lock.Lock()
node := Node{t, nil}
if ll.head == nil {
ll.head = &node
} else {
last := ll.head
for {
if last.next == nil {
break
}
last = last.next
}
last.next = &node
}
ll.size++
ll.lock.Unlock()
}
// Insert adds an Item at position i
func (ll *ItemLinkedList) Insert(i int, t Item) error {
ll.lock.Lock()
defer ll.lock.Unlock()
if i < 0 || i > ll.size {
return fmt.Errorf(“Index out of bounds”)
}
addNode := Node{t, nil}
if i == 0 {
addNode.next = ll.head
ll.head = &addNode
return nil
}
node := ll.head
j := 0
for j < i-2 {
j++
node = node.next
}
addNode.next = node.next
node.next = &addNode
ll.size++
return nil
}
// RemoveAt removes a node at position i
func (ll ItemLinkedList) RemoveAt(i int) (Item, error) {
ll.lock.Lock()
defer ll.lock.Unlock()
if i < 0 || i > ll.size {
return nil, fmt.Errorf(“Index out of bounds”)
}
node := ll.head
j := 0
for j < i-1 {
j++
node = node.next
}
remove := node.next
node.next = remove.next
ll.size–
return &remove.content, nil
}
// IndexOf returns the position of the Item t
func (ll *ItemLinkedList) IndexOf(t Item) int {
ll.lock.RLock()
defer ll.lock.RUnlock()
node := ll.head
j := 0
for {
if node.content == t {
return j
}
if node.next == nil {
return -1
}
node = node.next
j++
}
}
// IsEmpty returns true if the list is empty
func (ll *ItemLinkedList) IsEmpty() bool {
ll.lock.RLock()
defer ll.lock.RUnlock()
if ll.head == nil {
return true
}
return false
}
// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
ll.lock.RLock()
defer ll.lock.RUnlock()
size := 1
last := ll.head
for {
if last == nil || last.next == nil {
break
}
last = last.next
size++
}
return size
}
// Insert adds an Item at position i
func (ll *ItemLinkedList) String() {
ll.lock.RLock()
defer ll.lock.RUnlock()
node := ll.head
j := 0
for {
if node == nil {
break
}
j++
fmt.Print(node.content)
fmt.Print(" ")
node = node.next
}
fmt.Println()
}
// Head returns a pointer to the first node of the list
func (ll ItemLinkedList) Head() Node {
ll.lock.RLock()
defer ll.lock.RUnlock()
return ll.head
}
テスト
テストでは、上記の実装の使用法について説明します。
package linkedlist
import (
“fmt”
“testing”
)
var ll ItemLinkedList
func TestAppend(t *testing.T) {
if !ll.IsEmpty() {
t.Errorf(“list should be empty”)
}
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"first"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">IsEmpty</span>() {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"list should not be empty"</span>)
}
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">1</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 1 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"second"</span>)
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"third"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">3</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 3 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
}
func TestRemoveAt(t *testing.T) {
_, err := ll.RemoveAt(1)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">2</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 2 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
}
func TestInsert(t *testing.T) {
//test inserting in the middle
err := ll.Insert(2, “second2”)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
if size := ll.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
<span style="color:#75715e">//test inserting at head position
err = ll.Insert(0, “zero”)
if err != nil {
t.Errorf(“unexpected error %s”, err)
}
}
func TestIndexOf(t *testing.T) {
if i := ll.IndexOf(“zero”); i != 0 {
t.Errorf(“expected position 0 but got %d”, i)
}
if i := ll.IndexOf(“first”); i != 1 {
t.Errorf(“expected position 1 but got %d”, i)
}
if i := ll.IndexOf(“second2”); i != 2 {
t.Errorf(“expected position 2 but got %d”, i)
}
if i := ll.IndexOf(“third”); i != 3 {
t.Errorf(“expected position 3 but got %d”, i)
}
}
func TestHead(t *testing.T) {
ll.Append(“zero”)
h := ll.Head()
if “zero” != fmt.Sprint(h.content) {
t.Errorf(“Expected zero but got %s”, fmt.Sprint(h.content))
}
}
具体的なリンクリストデータ構造の作成
この一般的な実装を使用して、を使用してタイプ固有のリンクリストを生成できます。
//generate a `IntLinkedList` linked list of `int` values
genny -in linkedlist.go -out linkedlist-int.go gen "Item=int"
//generate a </span>StringLinkedList<span style="color:#e6db74"> linked list of </span>string<span style="color:#e6db74"> values
genny -in linkedlist.go -out linkedlist-string.go gen “Item=string”
その他のチュートリアル：
- NGINXリバースプロキシを使用してGoサービスを提供する
- Goで構造体のコピーを作成する
- GoWebサーバーの基本
- Goでのマップタイプの並べ替え
- 一言で言えばポインタを移動します
- タグの説明に行く
- 日付と時刻のフォーマットに移動
- Goを使用したJSON処理
- 可変個引数関数に移動
- GoStringsチートシート
- GoEmptyインターフェイスの説明
- Go withVSCodeとDelveのデバッグ
- NamedGoはパラメータを返します
- Goで乱数と文字列を生成する
- Goプロジェクトのファイルシステム構造
- Goに実装された二分探索アルゴリズム
- Goでのコマンドラインフラグの使用
- GOPATHの説明
- Goでコマンドラインアプリを作成する：lolcat
- Goを使用したCLIコマンドの作成：cowsay
- Goでのシェルパイプの使用
- CLIチュートリアルに移動：フォーチュンクローン
- Goを使用してフォルダ内のファイルを一覧表示します
- Goを使用して、GitHubからリポジトリのリストを取得します
- 移動し、文字列のスライスをファイルに追加します
- 文字列をバイトスライスに変換します
- GoでローカルGitの貢献を視覚化する
- GoCPUとメモリプロファイリングの開始
- Goプログラムの「インデックス作成をサポートしていません」エラーを解決する
- Goプログラムでの実行時間の測定
- 重複するタイトルを検出するためにGoを使用してWebクローラーを構築する
- ベストプラクティスに進む：ポインターまたは値のレシーバー？
- ベストプラクティスに進む：メソッドまたは関数を使用する必要がありますか？
- データ構造の移動：設定
- マップのチートシートに移動
- Goでジェネリック型の実装を生成する
- Goデータ構造：辞書
- Goデータ構造：ハッシュテーブル
- Go throughChannelsにイベントリスナーを実装する
- Goデータ構造：スタック
- データ構造の移動：キュー
- Goデータ構造：二分探索木
- Goデータ構造：グラフ
- Goデータ構造：リンクリスト
- Goデータ構造の完全ガイド
- Go値の比較
- Goはオブジェクト指向ですか？
- GoでのSQLデータベースの操作
- Goでの環境変数の使用
- チュートリアルに進む：PostgreSQLに裏打ちされたREST API
- GoWebサーバーでのCORSの有効化
- DockerコンテナへのGoアプリケーションのデプロイ
- GoがPHP開発者として学ぶための強力な言語である理由
- 移動し、io.Reader.ReadString改行文字を削除します
- 移動、変更を監視してプログラムを再構築する方法
- 行って、日付からの月を数えます
- GoでHTTPPOSTパラメーターにアクセスする