: jank    :   : 3479    : 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()

}