: jank : : 7190 : 2018-03-02 00:29 数据结构和算法
单循环链表只需要指定尾部元素,因为头元素可以从尾部元素的next获得,下面通过golang分别实现了单循环链表的添加,插入,查询,和删除功能。
package main import ( "errors" "fmt" ) type Data struct { data interface{} next *Data } type List struct { tail *Data size uint32 } //初始化一个空单循环链表 func NewList() (list *List) { list = new(List) list.tail = nil list.size = 0 return } //单循环链表添加数据 func (list *List) Append(data *Data) bool { if data == nil { return false } if list.size == 0 { data.next = data } else { predata := list.tail.next data.next = predata list.tail.next = data } list.tail = data fmt.Println("append : list.tail :", list.tail) list.size++ return true } //单循环链表插入数据 func (list *List) Insert(num uint32, data *Data) (err error) { if data == nil { err = errors.New("data is nil") return } if list.size == 0 || list.size == num { list.Append(data) } else { var predata *Data if num == 0 { predata = list.tail } else { predata = list.Find(num - 1) if list.size == num { list.tail = data } } data.next = predata.next predata.next = data list.size++ } return } //单循环链表查询数据 func (list *List) Find(num uint32) (data *Data) { data = list.tail for i := uint32(0); i <= num; i++ { data = data.next } fmt.Println("find:", data.data) return } //单循环链表查询全部数据,并赋值给切片 func (list *List) FindAll() (data []*Data) { dd := list.tail for i := uint32(0); i < list.size; i++ { dd = dd.next fmt.Println("data:", dd) data = append(data, dd) } return } //单循环链表按序号删除数据 func (list *List) RemoveInt(num uint32) (err error) { if list.size == 0 { err = errors.New("this list is nil") } if num > list.size-1 { err = errors.New("this num error, large list size") return } if list.size == 1 { list.tail = nil list.size = 0 return } else { var ( data *Data predata *Data ) if num == 0 { predata = list.tail } else { predata = list.Find(num - 1) } data = predata.next predata.next = data.next if num == list.size-1 { list.tail = predata } data.next = nil data = nil } list.size-- return } //单循环链表删除指定数据 func (list *List) Remove(data *Data) bool { rem := list.tail for i := uint32(0); i < list.size; i++ { if data == rem { if i == 0 { list.RemoveInt(list.size - 1) } else { list.RemoveInt(i - 1) } return true } rem = rem.next } return false } //单循环链表删除全部数据 func (list *List) RemoveAll() bool { if list.size == 0 { return true } for i := uint32(0); i < list.size; i++ { rem := list.tail list.tail = rem.next rem.next = nil } list.tail = nil list.size = 0 return true } func main() { list := NewList() a := list.Append(&Data{data: "jank"}) b := list.Append(&Data{data: "满城烟花"}) c := list.Insert(0, &Data{data: 34}) d := list.Insert(1, &Data{data: "jason"}) ee := &Data{data: "hello"} list.Insert(3, ee) fmt.Println("a: ", a, ", b: ", b, " c: ", c, ", d: ", d) fmt.Println("size:", list.size, " tail: ", list.tail.data) list.FindAll() fmt.Println("list 3:", list.Find(3)) //remove // fmt.Println(list.RemoveInt(3)) fmt.Println(list.Remove(ee)) //fmt.Println("size:", list.size, " head: ", list.head.data, " tail: ", list.tail.data) //list.GetAll() //removeall list.RemoveAll() fmt.Println("size:", list.size, " tail: ", list.tail) list.FindAll() }