Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Goで学ぶコンピューターサイエンスAdvent Calendar 2024

Day 8
@engineer_tacky(Neko Punch)

【Goで学ぶコンピューターサイエンス】連結リストと木構造

Last updated at Posted at 2024-12-08

連結リスト

連結リストは、一連のデータを線形に格納するデータ構造です。各要素 (ノード) は、データと次のノードへの参照を持っています。

特徴

  • データは順番に並ぶ
  • 配列とは異なり、サイズを事前に固定する必要がない
  • 単方向連結リスト
    • 各ノードは次のノードへの参照のみを持つ
  • 双方向連結リスト
    • 各ノードが前後のノードへの参照を持つ

主な操作

  • 追加
    • ノードをリストの先頭、末尾、または特定の位置に挿入
  • 削除
    • ノードをリストから削除
  • 検索
    • リスト全体を巡回して特定のデータを探す

Goサンプルコード

package main

import (
	"fmt"
)

// ノードの定義
type Node struct {
	val  int
	next *Node
}

// 単方向連結リストの定義
type LinkedList struct {
	head *Node
	tail *Node
	size int
}

// 末尾に要素を追加するメソッド
func (l *LinkedList) Append(value int) {
	node := &Node{val: value}

	if l.size == 0 {
		l.head = node
	} else {
		l.tail.next = node
	}
	l.tail = node
	l.size++
}

// 先頭に要素を追加するメソッド
func (l *LinkedList) Prepend(value int) {
	node := &Node{val: value}

	if l.size == 0 {
		l.tail = node
	} else {
		node.next = l.head
	}
	l.head = node
	l.size++
}

// 指定した位置に要素を挿入するメソッド
func (l *LinkedList) Insert(index, value int) error {
	if index < 0 || index > l.size {
		return fmt.Errorf("index out of bounds")
	}

	if index == 0 {
		l.Prepend(value)
	} else if index == l.size {
		l.Append(value)
	} else {
		node := &Node{val: value}
		current := l.head
		for i := 0; i < index-1; i++ {
			current = current.next
		}
		node.next = current.next
		current.next = node
		l.size++
	}
	return nil
}

// 先頭の要素を削除するメソッド
func (l *LinkedList) RemoveFirst() error {
	if l.size == 0 {
		return fmt.Errorf("list is empty")
	}

	l.head = l.head.next
	l.size--
	if l.size == 0 {
		l.tail = nil
	}
	return nil
}

// 末尾の要素を削除するメソッド
func (l *LinkedList) RemoveLast() error {
	if l.size == 0 {
		return fmt.Errorf("list is empty")
	}

	if l.size == 1 {
		l.head = nil
		l.tail = nil
	} else {
		current := l.head
		for current.next != l.tail {
			current = current.next
		}
		current.next = nil
		l.tail = current
	}
	l.size--
	return nil
}

// 指定した位置の要素を削除するメソッド
func (l *LinkedList) Remove(index int) error {
	if index < 0 || index >= l.size {
		return fmt.Errorf("index out of bounds")
	}

	if index == 0 {
		l.head = l.head.next
	} else {
		current := l.head
		for i := 0; i < index-1; i++ {
			current = current.next
		}
		current.next = current.next.next
		if index == l.size-1 {
			l.tail = current
		}
	}
	l.size--
	return nil
}

// 指定した位置の要素を取得するメソッド
func (l *LinkedList) Get(index int) (int, error) {
	if index < 0 || index >= l.size {
		return 0, fmt.Errorf("index out of bounds")
	}

	current := l.head
	for i := 0; i < index; i++ {
		current = current.next
	}
	return current.val, nil
}

// リストの内容を表示するメソッド
func (l *LinkedList) Display() {
	current := l.head
	for current != nil {
		fmt.Println(current.val)
		current = current.next
	}
}

// メイン関数
func main() {
	list := LinkedList{}
	fmt.Println("----- Append -----")
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Display()

	fmt.Println("----- Prepend -----")
	list.Prepend(0)
	list.Display()

	fmt.Println("----- Insert -----")
	list.Insert(2, 5)
	list.Display()

	fmt.Println("----- RemoveFirst -----")
	list.RemoveFirst()
	list.Display()

	fmt.Println("----- RemoveLast -----")
	list.RemoveLast()
	list.Display()

	fmt.Println("----- Remove -----")
	list.Remove(1)
	list.Display()

	fmt.Println("----- Get -----")
	val, _ := list.Get(0)
	fmt.Println(val)
}

----- Append -----
1
2
3
----- Prepend -----
0
1
2
3
----- Insert -----
0
1
5
2
3
----- RemoveFirst -----
1
5
2
3
----- RemoveLast -----
1
5
2
----- Remove -----
1
2
----- Get -----
1

木構造(ツリー)

木構造は、階層的にデータを格納する非線形データ構造です。各ノードは、親ノードと子ノードを持つことができます。

特徴

  • 階層構造
    • ノード間の親子関係に基づく構造
  • 根(ルート)
    • ツリーの最上位のノード
      • 親ノードを持たない
    • 子ノードを持つ
  • 葉(リーフ)
    • 子ノードを持たないノード
  • 種類
    • 二分探索木
      • 各ノードが最大2つの子ノードを持つ
    • B木
      • 各ノードが複数のキーと子ノードを持つ
      • データベースやファイルシステムで使用されている

主な操作

  • 追加
    • ノードをツリーに追加
  • 削除
    • ノードをツリーから削除
  • 探索
    • 特定のデータを持つノードを探す

Goサンプルコード

package main

import "fmt"

// ノードの定義
type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

// 二分探索木の定義
type BinarySearchTree struct {
	root *TreeNode
}

// 二分探索木の挿入
func (bst *BinarySearchTree) Insert(val int) {
	if bst.root == nil {
		bst.root = &TreeNode{val: val}
		return
	}

	current := bst.root
	for {
		if val < current.val {
			if current.left == nil {
				current.left = &TreeNode{val: val}
				return
			}
			current = current.left
		} else {
			if current.right == nil {
				current.right = &TreeNode{val: val}
				return
			}
			current = current.right
		}
	}
}

// 二分探索木の探索
func (bst *BinarySearchTree) Search(val int) bool {
	current := bst.root
	for current != nil {
		if val == current.val {
			return true
		}

		if val < current.val {
			current = current.left
		} else {
			current = current.right
		}
	}

	return false
}

// 二分探索木の削除
func (bst *BinarySearchTree) Delete(val int) {
	var parent *TreeNode
	current := bst.root

	for current != nil {
		if val == current.val {
			if current.left == nil && current.right == nil {
				if parent == nil {
					bst.root = nil
				} else if parent.left == current {
					parent.left = nil
				} else {
					parent.right = nil
				}
			} else if current.left == nil {
				if parent == nil {
					bst.root = current.right
				} else if parent.left == current {
					parent.left = current.right
				} else {
					parent.right = current.right
				}
			} else if current.right == nil {
				if parent == nil {
					bst.root = current.left
				} else if parent.left == current {
					parent.left = current.left
				} else {
					parent.right = current.left
				}
			} else {
				min := bst.findMin(current.right)
				current.val = min.val
				val = min.val
				parent = current
				current = current.right
				continue
			}

			return
		}

		parent = current
		if val < current.val {
			current = current.left
		} else {
			current = current.right
		}
	}
}

// 二分探索木の最小値の探索
func (bst *BinarySearchTree) findMin(node *TreeNode) *TreeNode {
	current := node
	for current.left != nil {
		current = current.left
	}
	return current
}

// 二分探索木を標準出力でツリー上に表示
func (bst *BinarySearchTree) Print() {
	printTree(bst.root, 0)
}

func printTree(node *TreeNode, level int) {
	if node == nil {
		return
	}

	printTree(node.right, level+1)
	for i := 0; i < level; i++ {
		print("\t")
	}
	println(node.val)
	printTree(node.left, level+1)

}

func main() {
	bst := BinarySearchTree{}
	bst.Insert(30)
	bst.Insert(11)
	bst.Insert(59)
	bst.Insert(45)
	bst.Insert(27)
	bst.Insert(63)
	bst.Insert(7)
	bst.Insert(13)
	bst.Insert(43)
	bst.Insert(47)

	fmt.Println("------------- 削除前 -------------")

	bst.Print()

	bst.Delete(11)
	bst.Delete(45)
	bst.Delete(43)

	fmt.Println("------------- 削除後 -------------")

	bst.Print()
}

表示左側の30がルート

------------- 削除前 -------------
                63
        59
                        47
                45
                        43
30
                27
                        13
        11
                7
------------- 削除後 -------------
                63
        59
                47
30
                27
        13
                7
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?