リスト

• 参照は必ずしも高速ではないが，挿入・削除は高速
• v.s. 配列：参照が高速だが，挿入・削除は最悪の場合$O(n)$の計算量がかかる．

線形リスト

package main

import "fmt"

type Cell struct {
	val int
	next *Cell
}

type LinkedList struct {
	head *Cell
}

func (l *LinkedList) Print() {
	cell := l.head
	for cell != nil {
		fmt.Printf("val: %d\n", cell.val)
		cell = cell.next
	}
}

func (l *LinkedList) Insert(val int, previous *Cell) {
	cell := NewCell(val)
	if previous == nil {
		fmt.Println("ERROR: Given previous cell does not exist yet.")
		return
	}
	cell.next = previous.next
	previous.next = cell
}

func (l *LinkedList) Prepend(val int) {
	cell := NewCell(val)
	cell.next = l.head
	l.head = cell
}

func (l *LinkedList) Append(val int) {
	cell := NewCell(val)
	last := l.head
	if last == nil {
		l.head = cell
		return
	}
	for last.next != nil {
		last = last.next
	}
	last.next = cell
}

func (l *LinkedList) Delete(val int) {
	if l.head == nil {
		fmt.Println("ERROR: linked list does not exist yet.")
		return
	}
	target := l.head
	var prev *Cell
	for target.next != nil {
		if target.val == val {
			break
		}
		prev = target
		target = target.next
	}
	if target == l.head {
		l.head = l.head.next
		return
	}
	prev.next = target.next
	target.next = nil
}

func NewCell(val int) *Cell {
	return &Cell{val: val, next: nil}
}

func NewLinkedList() *LinkedList {
	return &LinkedList{head: nil}
}

func main() {
	l0 := NewLinkedList()
	l0.head = NewCell(0)
	c1 := NewCell(1)
	c2 := NewCell(2)
	l0.head.next = c1
	c1.next = c2
	l0.Print()
    // val: 0
    // val: 1
    // val: 2

	l0.Prepend(-1)
	fmt.Println()
	l0.Print()
    // val: -1
    // val: 0
    // val: 1
    // val: 2

	l0.Append(99)
	fmt.Println()
	l0.Print()
    // val: -1
    // val: 0
    // val: 1
    // val: 2
    // val: 99

	l0.Insert(77, c2)
	fmt.Println()
	l0.Print()
    // val: -1
    // val: 0
    // val: 1
    // val: 2
    // val: 77
    // val: 99

	l0.Delete(0)
	fmt.Println()
	l0.Print()

    // val: -1
    // val: 1
    // val: 2
    // val: 77
    // val: 99
}

環状リスト

双方向リスト

気が向いたら追記