連結リスト

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

特徴

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

主な操作

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

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