課題12: ポインタとメモリ操作
課題概要
この課題では、ポインタを活用した効率的なデータ構造を実装します。連結リスト、ツリー構造、そしてポインタを使ったメモリ効率の最適化を通じて、ポインタの実践的な使い方を学びます。
マンダトリー要件
要件1: 単方向連結リストの実装（25点）
ポインタを使って単方向連結リストを実装してください。
ファイル: linkedlist.go
package collections
import "fmt"
// Node はリストのノード
type Node struct {
Value int
Next *Node
}
// LinkedList は単方向連結リスト
type LinkedList struct {
Head *Node
Size int
}
// NewLinkedList は新しい連結リストを作成
func NewLinkedList() *LinkedList {
return &LinkedList{
Head: nil,
Size: 0,
}
}
// Append はリストの末尾に要素を追加
func (l *LinkedList) Append(value int) {
newNode := &Node{Value: value, Next: nil}
if l.Head == nil {
l.Head = newNode
l.Size++
return
}
// 末尾まで走査
current := l.Head
for current.Next != nil {
current = current.Next
}
current.Next = newNode
l.Size++
}
// Prepend はリストの先頭に要素を追加
func (l *LinkedList) Prepend(value int) {
newNode := &Node{Value: value, Next: l.Head}
l.Head = newNode
l.Size++
}
// Insert は指定位置に要素を挿入
func (l *LinkedList) Insert(index, value int) error {
if index < 0 || index > l.Size {
return fmt.Errorf("インデックスが範囲外です: %d", index)
}
if index == 0 {
l.Prepend(value)
return nil
}
newNode := &Node{Value: value}
current := l.Head
// 挿入位置の一つ前まで移動
for i := 0; i < index-1; i++ {
current = current.Next
}
newNode.Next = current.Next
current.Next = newNode
l.Size++
return nil
}
// Delete は指定位置の要素を削除
func (l *LinkedList) Delete(index int) error {
if index < 0 || index >= l.Size {
return fmt.Errorf("インデックスが範囲外です: %d", index)
}
if index == 0 {
l.Head = l.Head.Next
l.Size--
return nil
}
current := l.Head
for i := 0; i < index-1; i++ {
current = current.Next
}
current.Next = current.Next.Next
l.Size--
return nil
}
// Get は指定位置の値を取得
func (l *LinkedList) Get(index int) (int, error) {
if index < 0 || index >= l.Size {
return 0, fmt.Errorf("インデックスが範囲外です: %d", index)
}
current := l.Head
for i := 0; i < index; i++ {
current = current.Next
}
return current.Value, nil
}
// Find は値を検索してインデックスを返す（見つからない場合は-1）
func (l *LinkedList) Find(value int) int {
current := l.Head
index := 0
for current != nil {
if current.Value == value {
return index
}
current = current.Next
index++
}
return -1
}
// Reverse はリストを反転
func (l *LinkedList) Reverse() {
var prev *Node
current := l.Head
for current != nil {
next := current.Next
current.Next = prev
prev = current
current = next
}
l.Head = prev
}
// ToSlice はリストをスライスに変換
func (l *LinkedList) ToSlice() []int {
result := make([]int, 0, l.Size)
current := l.Head
for current != nil {
result = append(result, current.Value)
current = current.Next
}
return result
}
// String はリストの文字列表現を返す
func (l *LinkedList) String() string {
return fmt.Sprintf("%v", l.ToSlice())
}
実装すべき内容：
Append: 末尾に追加Prepend: 先頭に追加Insert: 指定位置に挿入Delete: 指定位置を削除Get: 指定位置の値を取得Find: 値を検索Reverse: リストを反転ToSlice: スライスに変換
要件2: 二分探索木の実装（30点）
ポインタを使って二分探索木を実装してください。
ファイル: binarytree.go
package collections
import "fmt"
// TreeNode はツリーのノード
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
// BinarySearchTree は二分探索木
type BinarySearchTree struct {
Root *TreeNode
Size int
}
// NewBST は新しい二分探索木を作成
func NewBST() *BinarySearchTree {
return &BinarySearchTree{
Root: nil,
Size: 0,
}
}
// Insert は値を挿入
func (bst *BinarySearchTree) Insert(value int) {
bst.Root = bst.insertNode(bst.Root, value)
bst.Size++
}
func (bst *BinarySearchTree) insertNode(node *TreeNode, value int) *TreeNode {
if node == nil {
return &TreeNode{Value: value}
}
if value < node.Value {
node.Left = bst.insertNode(node.Left, value)
} else if value > node.Value {
node.Right = bst.insertNode(node.Right, value)
}
// 同じ値は挿入しない
return node
}
// Search は値を検索
func (bst *BinarySearchTree) Search(value int) bool {
return bst.searchNode(bst.Root, value)
}
func (bst *BinarySearchTree) searchNode(node *TreeNode, value int) bool {
if node == nil {
return false
}
if value == node.Value {
return true
} else if value < node.Value {
return bst.searchNode(node.Left, value)
} else {
return bst.searchNode(node.Right, value)
}
}
// Delete は値を削除
func (bst *BinarySearchTree) Delete(value int) bool {
var deleted bool
bst.Root, deleted = bst.deleteNode(bst.Root, value)
if deleted {
bst.Size--
}
return deleted
}
func (bst *BinarySearchTree) deleteNode(node *TreeNode, value int) (*TreeNode, bool) {
if node == nil {
return nil, false
}
var deleted bool
if value < node.Value {
node.Left, deleted = bst.deleteNode(node.Left, value)
} else if value > node.Value {
node.Right, deleted = bst.deleteNode(node.Right, value)
} else {
// ノード発見
deleted = true
// ケース1: 葉ノード
if node.Left == nil && node.Right == nil {
return nil, deleted
}
// ケース2: 子が1つ
if node.Left == nil {
return node.Right, deleted
}
if node.Right == nil {
return node.Left, deleted
}
// ケース3: 子が2つ
// 右部分木の最小値を見つける
minNode := bst.findMin(node.Right)
node.Value = minNode.Value
node.Right, _ = bst.deleteNode(node.Right, minNode.Value)
}
return node, deleted
}
func (bst *BinarySearchTree) findMin(node *TreeNode) *TreeNode {
for node.Left != nil {
node = node.Left
}
return node
}
// InOrder は中順走査（昇順）
func (bst *BinarySearchTree) InOrder() []int {
result := []int{}
bst.inOrderTraversal(bst.Root, &result)
return result
}
func (bst *BinarySearchTree) inOrderTraversal(node *TreeNode, result *[]int) {
if node == nil {
return
}
bst.inOrderTraversal(node.Left, result)
*result = append(*result, node.Value)
bst.inOrderTraversal(node.Right, result)
}
// PreOrder は前順走査
func (bst *BinarySearchTree) PreOrder() []int {
result := []int{}
bst.preOrderTraversal(bst.Root, &result)
return result
}
func (bst *BinarySearchTree) preOrderTraversal(node *TreeNode, result *[]int) {
if node == nil {
return
}
*result = append(*result, node.Value)
bst.preOrderTraversal(node.Left, result)
bst.preOrderTraversal(node.Right, result)
}
// PostOrder は後順走査
func (bst *BinarySearchTree) PostOrder() []int {
result := []int{}
bst.postOrderTraversal(bst.Root, &result)
return result
}
func (bst *BinarySearchTree) postOrderTraversal(node *TreeNode, result *[]int) {
if node == nil {
return
}
bst.postOrderTraversal(node.Left, result)
bst.postOrderTraversal(node.Right, result)
*result = append(*result, node.Value)
}
// Height はツリーの高さを返す
func (bst *BinarySearchTree) Height() int {
return bst.heightNode(bst.Root)
}
func (bst *BinarySearchTree) heightNode(node *TreeNode) int {
if node == nil {
return 0
}
leftHeight := bst.heightNode(node.Left)
rightHeight := bst.heightNode(node.Right)
if leftHeight > rightHeight {
return leftHeight + 1
}
return rightHeight + 1
}
実装すべき内容：
Insert: 値の挿入Search: 値の検索Delete: 値の削除（3つのケースに対応）InOrder: 中順走査（昇順）PreOrder: 前順走査PostOrder: 後順走査Height: ツリーの高さ
要件3: メモリ効率の比較（25点）
値渡しとポインタ渡しのメモリ効率を比較するベンチマークを実装してください。
ファイル: benchmark_test.go
package collections
import (
"testing"
)
type LargeStruct struct {
Data [10000]int
Name string
ID int
}
// 値渡し
func processByValue(s LargeStruct) LargeStruct {
s.Data[0] = 999
return s
}
// ポインタ渡し
func processByPointer(s *LargeStruct) {
s.Data[0] = 999
}
func BenchmarkValuePassing(b *testing.B) {
large := LargeStruct{Name: "Test", ID: 1}
b.ResetTimer()
for i := 0; i < b.N; i++ {
large = processByValue(large)
}
}
func BenchmarkPointerPassing(b *testing.B) {
large := LargeStruct{Name: "Test", ID: 1}
b.ResetTimer()
for i := 0; i < b.N; i++ {
processByPointer(&large)
}
}
// メモリ割り当てのベンチマーク
func BenchmarkValueAllocation(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = LargeStruct{Name: "Test", ID: i}
}
}
func BenchmarkPointerAllocation(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = &LargeStruct{Name: "Test", ID: i}
}
}
実装すべき内容：
- 値渡しとポインタ渡しのベンチマーク
- メモリ割り当てのベンチマーク
- 実行して結果を比較
要件4: メインプログラム（20点）
実装したデータ構造を使用するメインプログラムを作成してください。
ファイル: main.go
package main
import (
"fmt"
"yourmodule/collections"
)
func main() {
testLinkedList()
fmt.Println()
testBinarySearchTree()
}
func testLinkedList() {
fmt.Println("=== 連結リストのテスト ===")
list := collections.NewLinkedList()
// 要素の追加
list.Append(10)
list.Append(20)
list.Append(30)
fmt.Println("Append後:", list)
list.Prepend(5)
fmt.Println("Prepend後:", list)
// 挿入
list.Insert(2, 15)
fmt.Println("Insert(2, 15)後:", list)
// 検索
index := list.Find(20)
fmt.Printf("値20のインデックス: %d\n", index)
// 取得
value, _ := list.Get(2)
fmt.Printf("インデックス2の値: %d\n", value)
// 削除
list.Delete(3)
fmt.Println("Delete(3)後:", list)
// 反転
list.Reverse()
fmt.Println("Reverse後:", list)
fmt.Printf("リストのサイズ: %d\n", list.Size)
}
func testBinarySearchTree() {
fmt.Println("=== 二分探索木のテスト ===")
bst := collections.NewBST()
// 挿入
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, v := range values {
bst.Insert(v)
}
fmt.Printf("挿入した値: %v\n", values)
// 走査
fmt.Println("中順走査 (昇順):", bst.InOrder())
fmt.Println("前順走査:", bst.PreOrder())
fmt.Println("後順走査:", bst.PostOrder())
// 検索
searchValues := []int{40, 90}
for _, v := range searchValues {
found := bst.Search(v)
fmt.Printf("値%dは存在する: %v\n", v, found)
}
// 高さ
fmt.Printf("ツリーの高さ: %d\n", bst.Height())
// 削除
bst.Delete(30)
fmt.Println("30削除後の中順走査:", bst.InOrder())
fmt.Printf("ツリーのサイズ: %d\n", bst.Size)
}
実装すべき内容：
- 連結リストの全機能のテスト
- 二分探索木の全機能のテスト
- 結果の表示
期待される出力
=== 連結リストのテスト ===
Append後: [10 20 30]
Prepend後: [5 10 20 30]
Insert(2, 15)後: [5 10 15 20 30]
値20のインデックス: 3
インデックス2の値: 15
Delete(3)後: [5 10 15 30]
Reverse後: [30 15 10 5]
リストのサイズ: 4
=== 二分探索木のテスト ===
挿入した値: [50 30 70 20 40 60 80]
中順走査 (昇順): [20 30 40 50 60 70 80]
前順走査: [50 30 20 40 70 60 80]
後順走査: [20 40 30 60 80 70 50]
値40は存在する: true
値90は存在する: false
ツリーの高さ: 3
30削除後の中順走査: [20 40 50 60 70 80]
ツリーのサイズ: 6
ボーナス課題
> ボーナス: これらはオプションです。マンダトリー部分が完了してから取り組んでください。
ボーナス1: 双方向連結リスト（10点）
前のノードへのポインタも持つ双方向連結リストを実装してください。
type DNode struct {
Value int
Next *DNode
Prev *DNode
}
type DoublyLinkedList struct {
Head *DNode
Tail *DNode
Size int
}
func (l *DoublyLinkedList) Append(value int)
func (l *DoublyLinkedList) Prepend(value int)
func (l *DoublyLinkedList) DeleteFromEnd() error
func (l *DoublyLinkedList) ReverseTraversal() []int
ボーナス2: AVL木（自己平衡二分探索木）（5点）
木の高さを自動的にバランスするAVL木を実装してください。
type AVLNode struct {
Value int
Left *AVLNode
Right *AVLNode
Height int
}
type AVLTree struct {
Root *AVLNode
}
func (t *AVLTree) rotateLeft(node *AVLNode) *AVLNode
func (t *AVLTree) rotateRight(node *AVLNode) *AVLNode
func (t *AVLTree) balance(node *AVLNode) *AVLNode
ボーナス3: メモリプールの実装（5点）
頻繁な割り当て/解放を避けるメモリプールを実装してください。
type NodePool struct {
pool []*Node
}
func NewNodePool(size int) *NodePool
func (p *NodePool) Get() *Node
func (p *NodePool) Put(node *Node)
評価基準
| 項目 | 配点 | 詳細 |
|---|---|---|
| 連結リスト | 25点 | 全ての操作が正しく動作する |
| 二分探索木 | 30点 | 挿入、削除、走査が正しく実装されている |
| ベンチマーク | 25点 | 値渡しとポインタ渡しの違いが測定されている |
| メインプログラム | 20点 | 全機能をテストし、結果を表示している |
| **ボーナス1** | 10点 | 双方向連結リストが正しく動作する |
| **ボーナス2** | 5点 | AVL木の回転とバランス調整が実装されている |
| **ボーナス3** | 5点 | メモリプールが効率的に動作する |
提出方法
以下のファイルを提出してください：
submission/
├── go.mod
├── linkedlist.go # 連結リスト
├── binarytree.go # 二分探索木
├── benchmark_test.go # ベンチマーク
├── main.go # メインプログラム
└── bonus/ # ボーナス課題（オプション）
├── doublylist.go # 双方向連結リスト
├── avltree.go # AVL木
└── mempool.go # メモリプール
ヒント
go test -bench=. -benchmem-benchmemフラグで確認