// 第 9 周 – Go 中的单链表
// 运行：go run ./w09/singlylist
package main

import (
	"errors"
	"fmt"
	"strings"
)

// Node：值 + 指向下一个结点的指针
type Node struct {
	Value int
	Next  *Node
}

type List struct {
	Head *Node // 空链表：nil
}

func (l *List) String() string {
	var parts []string
	for p := l.Head; p != nil; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " -> ") + "]"
}

// Find – O(n)
func (l *List) Find(x int) *Node {
	p := l.Head
	for p != nil && p.Value != x {
		p = p.Next
	}
	return p
}

// InsertFirst – O(1)
func (l *List) InsertFirst(x int) {
	l.Head = &Node{Value: x, Next: l.Head}
}

// RemoveFirst – O(1)
func (l *List) RemoveFirst() (int, error) {
	if l.Head == nil {
		return 0, errors.New("empty list")
	}
	x := l.Head.Value
	l.Head = l.Head.Next
	return x, nil
}

// InsertAfter – O(1)
func (l *List) InsertAfter(q *Node, x int) {
	q.Next = &Node{Value: x, Next: q.Next}
}

// RemoveAfter – O(1)
func (l *List) RemoveAfter(q *Node) {
	if q.Next != nil {
		q.Next = q.Next.Next
	}
}

// InsertLast – O(n)
func (l *List) InsertLast(x int) {
	n := &Node{Value: x}
	if l.Head == nil {
		l.Head = n
		return
	}
	p := l.Head
	for p.Next != nil {
		p = p.Next
	}
	p.Next = n
}

// RemoveLast – O(n)：必须找到倒数第二个结点
func (l *List) RemoveLast() (int, error) {
	if l.Head == nil {
		return 0, errors.New("empty list")
	}
	if l.Head.Next == nil {
		x := l.Head.Value
		l.Head = nil
		return x, nil
	}
	p := l.Head
	for p.Next.Next != nil {
		p = p.Next
	}
	x := p.Next.Value
	p.Next = nil
	return x, nil
}

// Remove：删除具有给定值的结点 – O(n)
func (l *List) Remove(x int) bool {
	var prev *Node
	p := l.Head
	for p != nil && p.Value != x {
		prev, p = p, p.Next
	}
	if p == nil {
		return false
	}
	if prev == nil {
		l.Head = p.Next
	} else {
		prev.Next = p.Next
	}
	return true
}

func main() {
	var l List
	fmt.Println(&l)
	l.InsertFirst(31)
	l.InsertFirst(7)
	l.InsertFirst(12)
	fmt.Println("3 × InsertFirst:    ", &l)
	l.InsertLast(5)
	fmt.Println("InsertLast(5):      ", &l)
	q := l.Find(7)
	l.InsertAfter(q, 99)
	fmt.Println("InsertAfter(7, 99): ", &l)
	l.RemoveAfter(q)
	fmt.Println("RemoveAfter(7):     ", &l)
	a, _ := l.RemoveFirst()
	b, _ := l.RemoveLast()
	fmt.Println("RemoveFirst() =", a, ", RemoveLast() =", b, "->", &l)
	l.Remove(7)
	fmt.Println("Remove(7):          ", &l)
}