[Go语言实现链接列表]

链接列表和数组是算法中的两个基本数据结构，通常在程序设计过程中使用. 尽管这两种结构都可以用来存储一系列数据，但是每种结构都有自己的特点.

该数组的优点是它可以轻松地遍历以查找所需的数据. 在查询数组指定位置的操作中（例如查询数组中的第四数据），仅需要执行一次操作，时间复杂度为O（1）. 但是，这一次的方便是因为该阵列在内存中占用了连续的空间. 当执行类似的搜索或遍历时，本质是指针在内存中的方向偏移. 但是，当需要添加和删除数组成员的操作时，在数组中完成此类操作的时间复杂度为O（n）.

在某些操作中，链表的特性使其比数组更有效. 例如，当执行插入和删除操作时，链表操作的时间复杂度仅为O（1）. 另外，由于链接列表不会连续存储在内存中实现链表，因此可以充分利用内存中的零散空间.

如果我们申请100MB阵列，则当内存中没有连续且足够大的存储空间时，即使内存的剩余总可用空间大于100MB，应用程序仍将失败. 链表恰好相反. 它不需要连续的存储空间. 它使用“指针”来串联连接一个组，因此，如果我们申请一个100MB的链表，将完全没有问题.

基础内存模型为:

最常见的链表类型是: 单链表，双链表和循环链表.

链表通过指针将一组分散的内存块连接在一起. 其中，我们将存储块称为链接列表的“节点”. 为了将所有节点串在一起，除了存储数据外，每个链表的节点还需要记录链上下一个节点的地址，称为下一个后续指针.

在插入和删除数组时，为了保持内存数据的连续性，需要移动大量数据，因此时间复杂度为O（n）. 要在链表中插入或删除数据实现链表，由于链表本身的存储空间不是连续的，因此无需移动节点即可保持内存的连续性. 因此，在链表中插入和删除数据的速度非常快.

但是，有优点也有缺点. 如果链表要随机访问第k个元素，则效率不如数组. 由于链接列表中的数据不是连续存储的，因此无法像数组一样直接通过基于第一个地址和下标的寻址公式直接计算相应的内存地址，但需要根据存储地址依次逐个进行计算. 指针. 遍历直到找到相应的节点.

循环链表是一种特殊的单链表.

循环链表和单个链表之间的唯一区别是尾节点. 我们知道，单链接列表尾节点的指针指向一个空地址，表明这是最后一个节点. 循环链表的尾节点指针是指链表的头节点. 从我绘制的圆形链接列表图片中，您应该能够看到它像一个环一样端对端相连，因此它被称为“循环”链接列表.

与单链表相比，圆形链表的优点是从链端到链头更方便. 当要处理的数据具有环形结构时，特别适合使用循环链表. 例如，著名的约瑟夫问题. 尽管可以用单个链表实现，但是如果用循环链表实现，则代码会简单得多.

单链列表只有一个方向，并且该节点在下一个节点旁边只有一个后继指针. 顾名思义，双向链表支持两个方向. 每个节点在下一个节点旁边都有一个以上的后继指针，而前一个指针prev指向前一个节点.

双向链表需要两个额外的空间来存储后续节点和先前节点的地址. 因此，如果存储了相同数量的数据，则双链表将比单链表占用更多的存储空间. 尽管这两个指针浪费了存储空间，但它们可以支持双向遍历，这也带来了双向链表操作的灵活性.

package linklist
import (
	"errors"
	"fmt"
)
type ListNode struct {
	data interface{}
	next *ListNode
}
type LinkList struct {
	head   *ListNode
	length uint
}
func NewLinkList() *LinkList {
	return &LinkList{
		head:   &ListNode{0, nil},
		length: 0,
	}
}
func NewLinkNode(value interface{})*ListNode{
	return &ListNode{
		data:value,
		next:nil,
	}
}
func (this *ListNode) GetNext() *ListNode {
	return this.next
}
func (this *ListNode) GetValue() interface{} {
	return this.data
}
func (this *LinkList) Insert(i uint, node *ListNode) error {
	if i < 0 || node == nil || i > this.length{
		return errors.New("index out of range or node is nil")
	}
	preItem := (*this).head
	for j := uint(0); j < i; j++ {
		preItem = preItem.next
	}
	node.next = preItem.next
	preItem.next = node
	this.length++
	return nil
}
func (this *LinkList) Delete(node *ListNode)error{
	if nil == node{
		return errors.New("node is nil")
	}
	pre := this.head
	cur := this.head.next
	for nil != cur{
		if cur.data == node.data {
			break
		}
		pre = cur
		cur = cur.next
	}
	if nil == cur{
		return errors.New("not find node")
	}
	pre.next = cur.next
	node = nil
	this.length--
	return nil
}
func (this LinkList) FindByIndex(index uint)(*ListNode,error){
	if index < 0 || index >= this.length {
		return nil,errors.New("out of range")
	}
	preItem := this.head.next
	for i := uint(0); i < index; i++ {
		preItem = preItem.next
	}
	return preItem,nil
}
func (this LinkList)Print(){
	pre := this.head.next
	for nil != pre{
		fmt.Printf("%v\n",pre.GetValue())
		pre = pre.next
	}
}

完整代码

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-200546-1.html