Zenn
👾

双方向リスト（Doubly Linked List）をGoで実装してみた

2024/12/13に公開
Go
アルゴリズム
tech

はじめに

双方向リスト（Doubly Linked List）は、各ノードが前後のノードを指すポインタを持つデータ構造です。たとえば、ブラウザの「戻る」・「進む」機能や、音楽プレイリストの管理に役立ちます。本記事では、Goでの実装例と活用方法を紹介します。

双方向リストとは？

双方向リスト（Doubly Linked List）は、次の特徴を持つリスト構造です。

  • 各ノードは、データを持つだけでなく、次のノードと前のノードを指すポインタを持っています。
  • 順方向（次のノード）および逆方向（前のノード）での移動が可能です。

以下の図は、双方向リストの基本構造を表しています。

双方向リストに新しいノードを挿入する操作は、複雑に見える場合がありますが、図で示すと次のようになります。

メリットとデメリット

メリット デメリット
順方向・逆方向への移動が可能 メモリ消費が大きい
中間の挿入・削除が効率的 ポインタ管理が複雑

双方向リストを使う場面

  • ブラウザ履歴管理：「戻る」「進む」ボタン操作
  • プレイリスト：曲の再生順序変更
  • 操作履歴管理：変更の取り消しや再実行

実装例

以下は、Goのジェネリクスを活用して双方向リストを実装した例です。

package algorithm

import (
	"cmp"
	"fmt"
)

// ノードを表す構造体
type ListNode[T cmp.Ordered] struct {
	Value T
	Prev  *ListNode[T]
	Next  *ListNode[T]
}

// 双方向リストを表す構造体
type DoubleList[T cmp.Ordered] struct {
	Head   *ListNode[T]
	Tail   *ListNode[T]
	Length int
}

// リストを順方向に走査
func (list *DoubleList[T]) Traverse() {
	curr := list.Head
	for curr != nil {
		fmt.Printf("%v ", curr.Value)
		curr = curr.Next
	}
}

// リストを逆方向に走査
func (list *DoubleList[T]) ReverseTraverse() {
	curr := list.Tail
	for curr != nil {
		fmt.Printf("%v ", curr.Value)
		curr = curr.Prev
	}
}

// ノードをリストの先頭に追加
func (list *DoubleList[T]) PushFront(value T) {
	node := &ListNode[T]{Value: value}
	if list.Head == nil {
		list.Head = node
		list.Tail = node
	} else {
		node.Next = list.Head
		list.Head.Prev = node
		list.Head = node
	}
	list.Length++
}

// ノードをリストの末尾に追加
func (list *DoubleList[T]) PushBack(value T) {
	node := &ListNode[T]{Value: value}
	if list.Tail == nil {
		list.Head = node
		list.Tail = node
	} else {
		node.Prev = list.Tail
		list.Tail.Next = node
		list.Tail = node
	}
	list.Length++
}

// 指定したノードの後に新しいノードを挿入
func (list *DoubleList[T]) InsertAfter(value T, node *ListNode[T]) {
	if node == nil {
		return
	}
	newNode := &ListNode[T]{Value: value}
	newNode.Prev = node
	newNode.Next = node.Next

	if node.Next != nil {
		node.Next.Prev = newNode
	} else {
		list.Tail = newNode
	}
	node.Next = newNode
	list.Length++
}

// 指定したノードの前に新しいノードを挿入
func (list *DoubleList[T]) InsertBefore(value T, node *ListNode[T]) {
	if node == nil {
		return
	}
	newNode := &ListNode[T]{Value: value}
	newNode.Prev = node.Prev
	newNode.Next = node

	if node.Prev != nil {
		node.Prev.Next = newNode
	} else {
		list.Head = newNode
	}
	node.Prev = newNode
	list.Length++
}

// 指定したノードを削除
func (list *DoubleList[T]) Remove(node *ListNode[T]) {
	if node.Prev != nil {
		node.Prev.Next = node.Next
	} else {
		list.Head = node.Next
	}
	if node.Next != nil {
		node.Next.Prev = node.Prev
	} else {
		list.Tail = node.Prev
	}
	list.Length--
}

// 指定した値を持つノードを検索
func (list *DoubleList[T]) Find(value T) *ListNode[T] {
	curr := list.Head
	for curr != nil {
		if curr.Value == value {
			return curr
		}
		curr = curr.Next
	}
	return nil
}

// 指定したインデックスのノードを取得
func (list *DoubleList[T]) Get(index int) *ListNode[T] {
	if index < 0 || index >= list.Length {
		return nil
	}
	if index < list.Length/2 {
		curr := list.Head
		for i := 0; i < index; i++ {
			curr = curr.Next
		}
		return curr
	} else {
		curr := list.Tail
		for i := list.Length - 1; i > index; i-- {
			curr = curr.Prev
		}
		return curr
	}
}

テストコード

次に、双方向リストの実装が正しく動作するかを確認するためのテストコードです。

func TestList(t *testing.T) {
	list := &DoubleList[int]{}
	list.PushBack(1)  // 1
	list.PushBack(2)  // 1 -> 2
	list.PushFront(3) // 3 -> 1 -> 2
	list.PushFront(4) // 4 -> 3 -> 1 -> 2

	third := list.Get(2)        //1
	list.InsertAfter(8, third)  // 4 -> 3 -> 1 -> 8 -> 2
	list.InsertBefore(9, third) // 4 -> 3 -> 9 -> 1 -> 8 -> 2
	list.Remove(third)          // 4 -> 3 -> 9 -> 8 -> 2

	fmt.Println(list.Length) // 5

	list.Traverse()        // 4 -> 3 -> 9 -> 8 -> 2
	list.ReverseTraverse() // 2 -> 8 -> 9 -> 3 -> 4
}

Goの標準ライブラリ: container/list

Goの標準ライブラリには、双方向リスト（Doubly Linked List）を提供する container/list パッケージがあります。このパッケージを使うと、リストの操作（要素の追加、削除、走査など）を簡単に実現できます。

基本操作

container/list パッケージでは、以下の基本操作が提供されています。

操作 説明
PushBack リストの末尾に要素を追加
PushFront リストの先頭に要素を追加
InsertAfter 指定した要素の後ろに新しい要素を挿入
InsertBefore 指定した要素の前に新しい要素を挿入
Remove 指定した要素をリストから削除
Front / Back リストの先頭または末尾の要素を取得
Len リストの要素数を取得
Next / Prev 現在の要素から次または前の要素へのポインタを取得

使用例

以下は、container/list を使ってリスト操作をテストする例です。

package main

import (
	"container/list"
	"fmt"
	"testing"
)

func TestStdList(t *testing.T) {
	//リストの作成
	list := list.New()

	//リストの末尾に要素を追加
	list.PushBack(1) // 1
	list.PushBack(2) // 1 -> 2

	//リストの先頭に要素を追加
	list.PushFront(3) // 3 -> 1 -> 2
	list.PushFront(4) // 4 -> 3 -> 1 -> 2

	//リストの先頭から3番目の要素を取得
	third := list.Front().Next().Next() // 1

	//リストの3番目の要素の後ろに要素を追加
	list.InsertAfter(8, third) // 4 -> 3 -> 1 -> 8 -> 2

	//リストの3番目の要素の前に要素を追加
	list.InsertBefore(9, third) // 4 -> 3 -> 9 -> 1 -> 8 -> 2

	//リストの3番目の要素を削除
	list.Remove(third) // 4 -> 3 -> 9 -> 8 -> 2

	//リストの要素数を取得
	fmt.Println(list.Len()) // 5

	//リストの要素を順方向に走査
	expected := []int{4, 3, 9, 8, 2}
	actual := make([]int, 0, list.Len())
	for e := list.Front(); e != nil; e = e.Next() {
		actual = append(actual, e.Value.(int))
	}

	for i, v := range actual {
		if v != expected[i] {
			t.Errorf("expected %v at index %d, got %v", expected[i], i, v)
		}
	}
}

リストの走査

Goの標準ライブラリcontainer/listには、リストを順方向や逆方向に走査する専用の関数は用意されていません。ただし、Next や Prev メソッドを利用することで簡単に実装できます。

以下は、リストを順方向や逆方向に走査する関数を実装した例です。

package algorithm

import (
	"container/list"
	"fmt"
)
// リストを順方向に走査して各値を出力
func TraverseList(lst *list.List) {
	head := lst.Front()
	for head.Next() != nil {
		fmt.Printf("%v ", head.Value)
		head = head.Next()
	}
	fmt.Println()
}

// リストを逆方向に走査して各値を出力
func ReverseList(lst *list.List) {
	tail := lst.Back()
	for tail.Prev() != nil {
		fmt.Printf("%v ", tail.Value)
		tail = tail.Prev()
	}
	fmt.Println()
}

まとめ

本記事では、双方向リストを使ったGoでの実装例を紹介しました。また、双方向リストを利用することで、LRUキャッシュ（Least Recently Used Cache）を効率的に実装できます。LRUキャッシュの詳細については、こちらの記事で紹介しています。

Discussion