需求
大家都知道基本链表得有以下特性:链表的初始化、链表的长度、节点的插入、删除、查找等一些常见的基本操作,最后写好之后,需要测试。
实现
初始化
有语言基础的人都知道,链表是由节点连接而成,这其中在定义一个 List 数据结构之外,还需要定义一个 Node 类型的数据结构。先说 Node 类型的数据结构,首先 List 按照正常的设计应该是可以存储基本类型的数据的,这就要求 Node 中的 Value
的类型不能固定。
type Node struct {
Value interface{}
next, prev *Node
}
下面就是定义 List 结构体了,有了上面的分析,List 结构体的定义就很好实现了:
type List struct {
// 头节点
root Node
// list 长度
length int
}
处理好空 List:
// 返回 List 的指针
func New() *List {
// 获取 List{} 的地址
l := &List{}
// list 初始长度为0
l.length = 0
l.root.next = &l.root
l.root.prev = &l.root
return l
}
判空和长度
List 的判空和获取长度也是非常基础和重要的,判断是否为空,返回的数据类型是布尔类型的。什么情况下 List 是为空呢?根据前面的定义,头节点的 next 指针域指向是头结点本身的地址即为空。另外,判空函数写好了,总不能什么类型的数据都去调用这个函数,我们需要指定调用的数据类型,在本例中当然是 List 类型的了,为了方便操作,传入一个 List 的地址即可。
func (l *List) IsEmpty() bool {
return l.root.next == &l.root
}
分析完毕之后,获取 list 的长度就简单很多了:
func (l *List) Length() int {
return l.length
}
头插和尾插
因为在定义 List 数据结构的时候,就定义了一个 root 头节点。所以此时,可以很方便的实现头插入和尾插入。考虑能够同时插入多个 Node 节点,利用 Go 中的变长参数实现该特性。对插入的 Node 节点进行循环处理,新节点的指针域和 root 节点的指针域做相应改变:
func (l *List) PushFront(elements ...interface{}) {
for _, element := range elements {
n := &Node{Value: element}
// 新节点的 next 是 root 节点的 next
n.next = l.root.next
// 新节点的 prev 存储的是 root 的地址
n.prev = &l.root
// 原来 root 节点的 next 的 prev 是新节点
l.root.next.prev = n
// 头插法 root 之后始终是新节点
l.root.next = n
// list 长度加1
l.length++
}
}
尾插法:
func (l *List) PushBack(elements ...interface{}) {
for _, element := range elements {
n := &Node{Value: element}
n.next = &l.root
n.prev = l.root.prev
l.root.prev.next = n
l.root.prev = n
l.length++
}
}
查找
查找最终的效果是返回指定数值的索引,如果不存在的话返回-1即可。对于链表的查找是一个遍历的过程,在此时就需要考虑遍历的起始和终止区间了,不能越界出错。因为是循环链表,终止节点也很好办。
func (l *List) Find(element interface{}) int {
index := 0
p := l.root.next
for p != &l.root && p.Value != element {
p = p.next
index++
}
// p 不是 root
if p != &l.root {
return index
}
return -1
}
删除
链表的删除操作逻辑很清晰,将一个 Node 的节点与前后节点断开即可,同时前后节点和 Node 节点本身指针域也要做相应修改,最后别忘记将链表的长度减少相应长度。
func (l *List) remove(n *Node) {
n.prev.next = n.next
n.next.prev = n.prev
n.next = nil
n.prev = nil
l.length--
}
删除并返回 List 中的第一个数据:
func (l *List) Lpop() interface{} {
if l.length == 0 {
// null 的表现形式 nil
return nil
}
n := l.root.next
l.remove(n)
return n.Value
}
遍历
下面 normalIndex 函数的作用返回一个正常逻辑的 Index,例如处理好一些越界问题:
func (l *List) normalIndex(index int) int {
if index > l.length-1 {
index = l.length - 1
}
if index < -l.length {
index = 0
}
// 将给定的 index 与 length 做取余处理
index = (l.length + index) % l.length
return index
}
如下的函数为获取指定范围内的数据,根据传入的参数需要指定 start 和 end,最后返回的应该是一个切片或者数组,具体类型未知:
func (l *List) Range(start, end int) []interface{} {
// 获取正常的 start 和 end
start = l.normalIndex(start)
end = l.normalIndex(end)
// 声明一个 interface 类型的数组
res := []interface{}{}
// 如果上下界不符合逻辑,返回空 res
if start > end {
return res
}
sNode := l.index(start)
eNode := l.index(end)
// 起始点和重点遍历
for n := sNode; n != eNode; {
// res的append方式
res = append(res, n.Value)
n = n.next
}
res = append(res, eNode.Value)
return res
}