: jank    :   : 4852    : 2018-02-01 17:53  数据结构和算法

package main

import (
	"fmt"
)

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

type List struct {
	size uint  // 数量
	head *Node // 头
	tail *Node // 尾
}

//初始化
func (list *List) Init() {
	list.size = 0   // 此时链表是空的
	list.head = nil // 没有头
	list.tail = nil // 没有尾
}

//添加元素
func (list *List) Append(node *Node) bool {
	if node == nil {
		return false
	}
	node.next = nil
	// 将新元素放入单链表中
	if list.size == 0 {
		list.head = node
	} else {
	        list.tail.next = node
	}

	// 调整尾部位置，及链表元素数量
	list.tail = node // node成为新的尾部
	list.size++      // 元素数量增加

	return true
}

//插入元素
func (list *List) Insert(i uint, node *Node) bool {
	// 空的节点、索引超出范围和空链表都无法做插入操作
	if node == nil || i > list.size || list.size == 0 {
		return false
	}

	if i == 0 {
		node.next = list.head
		list.head = node
	} else {
		preItem := list.Get(i - 1)
		// 原来元素放到新元素后面,新元素放到前一个元素后面
		node.next = preItem.next
		preItem.next = node
	}

	list.size++

	return true
}

//删除元素
func (list *List) Remove(i uint) bool {

	if i >= list.size {
		return false
	}
	var node *Node
	if i == 0 { // 删除头部
		node = list.head
		list.head = node.next
		if list.size == 1 { // 如果只有一个元素，那尾部也要调整
			list.tail = nil
		}
	} else {
		preItem := list.Get(i - 1)
		node = preItem.next
		preItem.next = node.next

		if i == list.size-1 { // 若删除的尾部，尾部指针需要调整
			list.tail = preItem
		}
	}
	list.size--
	return true
}

//查找元素
func (list *List) Get(i uint) *Node {
	if i >= list.size {
		return nil
	}

	item := list.head
	for j := uint(0); j < i; j++ {
		item = item.next
	}

	return item
}

//遍历查询并赋值给切片
func (list *List) GetAll() (nodes []*Node) {
	if list.size == 0 {
		return nil
	}
	item := list.head
	for i := uint(0); i < list.size; i++ {
		nodes = append(nodes, item)
		item = item.next
	}
	return
}

//删除整个链表
func (list *List) RemoveAll() bool {
	for i := uint(0); i < list.size; i++ {
		rem := list.head
		list.head = rem.next
		rem.next = nil
	}

	list.size = 0
	list.tail = nil
	return true
}

func NewList() (list *List) {
	list = new(List)
	list.Init()
	return
}

func main() {
	list := NewList()
	a := list.Append(&Node{data: "jank"})
	b := list.Append(&Node{data: "满城烟花"})
	c := list.Append(&Node{data: [2]string{"abc", "defg"}})
	d := list.Insert(uint(1), &Node{data: 123456})
	e := list.Insert(uint(0), &Node{data: "jason"})
	f := list.Remove(uint(2))
	//	list.RemoveAll()
	fmt.Println("append a:", a)
	fmt.Println("append b:", b)
	fmt.Println("append c:", c)
	fmt.Println("insert d:", d)
	fmt.Println("insert e:", e)
	fmt.Println("remove f:", f)
	fmt.Println("size:", list.size)
	fmt.Println("get:", list.Get(0))
	fmt.Println("head:", list.head)
	fmt.Println("tail:", list.tail)
	data := list.GetAll()
	for k, v := range data {
		fmt.Printf("data %d: %v 
", k, v)
	}
	list.RemoveAll()
	data = list.GetAll()
	fmt.Println(data)
	for k, v := range data {
		fmt.Printf("data new %d: %v 
", k, v)
	}

}