: jank : : 4256 : 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) } }