mission 2

mission-2.md

2.1

code

test.go

package main

import (
	"fmt"

	"go-learn/linkList"
)

func main() {
	list := &linkList.LinkList{}
	list.Append("a")
	list.Append("b")
	list.Append("c")
	list.Append("d")
	list.Append("e")

	PrintAll(list)

	fmt.Printf("list length: %d\n", list.Length())

	fmt.Printf("list is empty: %t\n", list.Length()==0)

	third, _ := list.GetNode(2)
	fmt.Printf("the third: %s\n", third.Value)

	fmt.Printf("the \"a\" is in: %d\n", list.IndexOfFirst("a"))

	list.InsertNode(3, "f")
	PrintAll(list)
	list.Remove(2)
	PrintAll(list)
	list.Clear()
}

func PrintAll(list *linkList.LinkList) {
	for i := 0; i < list.Length(); i++ {
		value, _ := list.GetNode(i)
		fmt.Printf("index: %d value: %s\n", i, value.Value)
	}
}

linkList.go

package linkList

import "fmt"

type Node struct {
	Value interface{}
	next  *Node
}

type LinkList struct {
	First  *Node
	length int
}

func (linkList *LinkList) Length() int {
	return linkList.length
}

func (linkList *LinkList) GetNode(index int) (*Node, error) {
	if index >= linkList.length || index < 0 {
		return nil, fmt.Errorf("index (%d) out of bound\n", index)
	}

	node := linkList.First

	for i := 0; i < index; i++ {
		node = node.next
	}

	return node, nil
}

func (linkList *LinkList) InsertNode(index int, value interface{}) error {
	node := &Node{Value: value}

	if index == 0 && linkList.length == 0 {
		linkList.First = node
		return nil
	}

	if index < 0 || index >= linkList.length {
		return fmt.Errorf("index (%d) out of bound\n", index)
	}

	/*switch index {

	case 0:
		tmp := linkList.First
		node.next = tmp
		linkList.First = node
		linkList.length++
		return nil

	default:
		tmp := linkList.First

		for i := 0; i < index-1; i++ {
			tmp = tmp.next
		}

		next := tmp.next
		tmp.next = node
		node.next = next
		linkList.length++
		return nil
	}*/
	if index == 0 {
		tmp := linkList.First
		node.next = tmp
		linkList.First = node
		linkList.length++
		return nil

	} else {
		tmp := linkList.First

		for i := 0; i < index-1; i++ {
			tmp = tmp.next
		}

		next := tmp.next
		tmp.next = node
		node.next = next
		linkList.length++
		return nil
	}
}

func (linkList *LinkList) setNode(index int, value interface{}) (Node, error) {
	if index == 0 && linkList.length == 0 {
		linkList.First = &Node{Value: value}
		return Node{}, nil
	}

	if index < 0 || index >= linkList.length {
		return Node{}, fmt.Errorf("index (%d) out of bound\n", index)
	}

	tmp := linkList.First
	for i := 0; i < index-1; i++ {
		tmp = tmp.next
	}
	old := tmp.next
	tmp.next = tmp.next.next
	return *old, nil
}

func (linkList *LinkList) Append(value interface{}) {
	node := &Node{Value: value}

	if linkList.length == 0 {
		linkList.First = node
		linkList.length++
		return
	}

	tail := linkList.First
	for i := 0; i < linkList.length-1; i++ {
		tail = tail.next
	}
	tail.next = node
	linkList.length++
}

func (linkList *LinkList) Remove(index int) error {
	if index < 0 || index >= linkList.length {
		fmt.Errorf("index (%d) out of bound\n", index)
	}

	if index == 0 {
		linkList.First = linkList.First.next
		linkList.length--
		return nil
	}

	tmp := linkList.First

	for i := 0; i < index-1; i++ {
		tmp = tmp.next
	}
	tmp.next = tmp.next.next
	linkList.length--
	return nil
}

func (linkList *LinkList) Clear() {
	linkList.First = nil
}

func (linkList *LinkList) IndexOfFirst(v interface{}) int {
	for i := 0; i < linkList.length; i++ {
		value, _ := linkList.GetNode(i)
		if v == value {
			return i
		}
	}

	return -1
}

result

index: 0 value: a
index: 1 value: b
index: 2 value: c
index: 3 value: d
index: 4 value: e
list length: 5
list is empty: false
the third: c
the "a" is in: -1
index: 0 value: a
index: 1 value: b
index: 2 value: c
index: 3 value: f
index: 4 value: d
index: 5 value: e
index: 0 value: a
index: 1 value: b
index: 2 value: f
index: 3 value: d
index: 4 value: e

2.2

code

test.go

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	//l.Init()
	l.PushBack("a")
	l.PushBack("d")
	l.PushBack("c")
	l.PushBack("b")
	l.PushBack("e")

	printAll(l)

	split(l, "d")
	fmt.Println()

	printAll(l)
}

func split(l *list.List, s string) (*list.List, error) {
	var middle *list.Element
	tmp := l.Front()

	var middleIndex int

	for i := 0; i < l.Len(); i++ {
		if tmp.Value.(string) == s {
			middle = tmp
			middleIndex = i
			break
		}
		tmp = tmp.Next()
	}
	if middle == nil {
		return nil, fmt.Errorf("s (%s) not in list\n", s)
	}

	tmp = l.Front()

	for i := 0; i < middleIndex; i++ {
		next := tmp.Next()

		if tmp.Value.(string) > s {
			l.MoveToBack(tmp)
		}
		tmp = next
	}

	for i := middleIndex; i < l.Len(); i++ {
		next := tmp.Next()

		if tmp.Value.(string) < s {
			l.MoveToFront(tmp)
		}
		tmp = next
	}
	return l, nil
}

func printAll(l *list.List) {
	elem := l.Front()

	for i := 0; i < l.Len(); i++ {
		fmt.Println(elem.Value)
		elem = elem.Next()
	}
}

result

a
d
c
b
e

b
c
a
d
e