概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

リスト（線形リストの片方向リスト）

データを一直線上に並べた構造
- 各ノードは次のノードへのポインタを持つ
データの追加や削除は容易だが、アクセスには時間がかかる
リストでは、データは連続したメモリ領域に格納される必要はない
- 一般的には離れた領域に格納される

計算時間

リストに格納されているデータ数をnとする。

データへのアクセス

O(n)
- データの先頭から順次アクセス（シーケンシャルアクセス）する必要があるため、線形時間となる

データの追加

O(₁)
- 追加箇所へのデータアクセスは完了しているという前提で、ポインタを2つ差し替えるだけなので定数時間で済む

データの削除

データの追加と同様

実装

線形リスト

片方向リスト

package main

import (
	"errors"
	"fmt"
)

// A node is a node of list.
type node struct {
	value string
	next  *node
}

// A list is a singly linked list.
type list struct {
	head *node
}

// add add a node to tail of a list.
func (l *list) add(newn *node) {
	if l.head == nil {
		l.head = newn
		newn.next = nil
		return
	}

	// sequential access
	for n := l.head; n != nil; n = n.next {
		if n.next == nil {
			n.next = newn
			return
		}
	}

	return
}

// insert a node before a particular node of a list.
func (l *list) insert(newn *node, v string) error {
	if l.head == nil {
		return errors.New("a target node is not exists")
	}

	// sequential access
	for n := l.head; n.next != nil; n = n.next {
		if n.next.value == v {
			newn.next = n.next
			n.next = newn
			return nil
		}
	}

	return errors.New("a target node is not exists")
}

// display display all nodes of a list.
func (l *list) display() {
	// sequential access
	for n := l.head; n != nil; n = n.next {
		fmt.Println(n.value, n.next)
	}
}

func main() {
	l := &list{}

	first := &node{"first", nil}
	second := &node{"second", nil}
	third := &node{"third", nil}

	l.add(first)
	l.add(second)
	l.add(third)

	between := &node{"between", nil}
	l.insert(between, "second")

	l.display()

	fmt.Printf("%#v\n", l)
}

構造体Listにはリストの先頭ノードを格納しておく
- リストのデータアクセスを順次アクセスで行うため
add
- リストの末尾にノードを追加するメソッド
insert
- リストの指定したノードの手前にノードを追加追加するメソッド
  - 追加する位置を特定する→追加位置の一つ手前のポインタと追加するノードのポインタを調整
  - 追加する位置を特定する時は、ループ内で次のノードのポインタを参照して次のノードの値が指定した値とマッチするか判定する
ノート