- 链表在Redis中的应用场景
1.列表键的底层实现之一
2.RedisServer中保存的客户端状态信息
3.发布与订阅
4.慢查询
5.监视器
- 链表节点数据结构
Redis实现的是双端无环链表，pre指针指向其前置节点，next指针指向其后置节点，表头节点的pre属性和表尾节点的next属性为nil，节点值的类型为interface{}，从而达到保存不同类型值的目的。
代码语言：javascript复制//链表节点
type listNode struct {
pre *listNode //前置节点
next *listNode //后置节点
value interface{} //节点值
}- 链表结构
通过list结构持有链表，其中head、tail属性分别指向表头和表尾节点，length属性用于记录链表长度，从而可以使获取链表长度的复杂度从O(N)降低为O(1)。此外，还有三个函数类型的属性，分别为节点值复制函数dup，节点值释放函数free，节点值对比函数match。
代码语言：javascript复制//持有链表结构
type list struct {
//指向表头节点
head *listNode
//指向表尾节点
tail *listNode
//记录链表长度
length int64
//节点值复制函数
dup func(ptr interface{}) interface{}
//节点值释放函数
free func(ptr interface{})
//节点值对比函数
match func(ptr interface{}, key interface{}) bool
}例如，一个长度为4的节点如下图所示：
1.创建（初始化）链表
代码语言：javascript复制//创建链表
func ListCreate() *list {
list := &list{}
list.head, list.tail = nil, nil
list.length = 0
list.dup = nil
list.free = nil
list.match = nil
return list
}2.从表头方向插入节点
代码语言：javascript复制//从表头方向插入节点
func (l *list) AddNodeHead(v interface{}) {
//为节点分配内存
node := &listNode{value: v}
if l.length == 0 {//插入空链表
node.pre, node.next = nil, nil
l.head, l.tail = node, node
} else {//插入非空链表
node.pre, node.next = nil, l.head
//维护表头
l.head.pre = node
l.head = node
}
//维护链表长度
l.length
}3.从表尾方向插入节点
代码语言：javascript复制//从表尾方向插入节点
func (l *list) AddNodeTail(v interface{}) {
//为节点分配内存
node := &listNode{value: v}
if l.length == 0 {//插入空链表
node.pre, node.next = nil, nil
l.head, l.tail = node, node
} else {//插入非空链表
node.pre, node.next = l.tail, nil
//维护表尾
l.tail.next = node
l.tail = node
}
//维护链表长度
l.length
}4.插入节点到链表中某个节点之前或之后
分为两步处理：
第一步：维护插入节点的相关属性，顺带维护链表的head和tail
第二步：维护插入节点影响到的前置节点的next和后置节点的pre属性
代码语言：javascript复制//创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后
func (l *list) InsertNode(oldNode *listNode, value interface{}, after bool) {
if nil == oldNode {
return
}
//为节点分配内存
node := &listNode{value: value}
//执行插入操作，这里只涉及node节点pre和next属性以及表头、表尾属性的维护
if after { //插入节点到oldNode节点后，即oldNode.next = node
node.pre = oldNode
node.next = oldNode.next
if l.tail == oldNode { //如果oldNode为原表尾，则需要维护表尾属性
l.tail = node
}
} else { //插入节点到oldNode节点前，即oldNode.pre = node
node.pre = oldNode.pre
node.next = oldNode
if l.head == oldNode { //如果oldNode为原表头，则需要维护表头属性
l.head = node
}
}
//统一处理插入节点前后节点的属性
//统一维护插入节点的后置节点next属性
if nil != node.next {
node.next.pre = node
}
//统一维护插入节点的前置节点pre属性
if nil != node.pre {
node.pre.next = node
}
//维护链表长度
l.length
}5.删除节点
代码语言：javascript复制//删除节点
func (l *list) DeleteNode(node *listNode) {
if 0 == l.length || nil == node {
return
}
if nil != node.pre {//节点非表头
node.pre.next = node.next
} else {//节点是表头
l.head = node.next
}
if nil != node.next {//节点非表尾
node.next.pre = node.pre
} else {//节点是表尾
l.tail = node.pre
}
if nil != l.free {
l.free(node.value)
}
node = nil
//维护链表长度
l.length--
}6.通过key值查找节点
如果节点比对函数match为nil则直接判断节点值是否相等。
代码语言：javascript复制//通过key查找节点
func (l *list) SearchKey(key interface{}) *listNode {
if nil == l {
return nil
}
//初始化返回节点
var node *listNode = nil
//初始化迭代器
iter := ListGetIterator(l, AL_START_HEAD)
//迭代查找
for current:=iter.Next();nil!=current;current=iter.Next() {
if nil != l.match {//链表有匹配方法
if l.match(current.GetValue(), key) {
node = current
break
}
} else {//链表无匹配方法
if current.GetValue() == key {
node = current
break
}
}
}
//释放迭代器
ListReleaseIterator(iter)
return node
}7.链表给定索引节点的值
PS:源码中并没有用到迭代器，重写使用了迭代器
代码语言：javascript复制//返回链表给定索引上的值
func (l *list) Index(index int64) *listNode {
var node *listNode = nil
var n int64
var iter *listIter
if index < 0 {//从表尾方向查找
iter = ListGetIterator(l, AL_START_TAIL)
n = (-index)-1 //例如：index为-1则n为0
} else {//从表头方向查找
iter = ListGetIterator(l, AL_START_HEAD)
n = index
}
//利用迭代器查找
for current:=iter.Next();nil!=current&&n>=0;current=iter.Next(){
node = current
//计数减一，当n为负数时break，则当前node指向头或尾节点
n--
}
if n < 0 { //补偿操作，只要n为负数，则证明out of range，返回nil
node = nil
}
ListReleaseIterator(iter)
return node
}8.取出链表的表尾节点，并将它移动到表头，成为新的表头节点
例如：
原表：1->2->3->4
Rotate后：4->1->2->3
代码语言：javascript复制func (l *list) Rotate() {
if nil == l || l.length <= 1 {
return
}
//取出表尾
tail := l.tail
l.tail = tail.pre
l.tail.next = nil
//将表尾插到表头
tail.next = l.head
tail.pre = nil
l.head.pre = tail
l.head = tail
}9.复制链表
如果节点复制函数dup为nil则直接复制节点值
代码语言：javascript复制//复制链表
func (l *list)Dup() (*list) {
//源链表为空直接返回
if nil == l {
return nil
}
//为链表分配内存
dest := ListCreate()
if nil == dest {
return nil
}
//复制三个函数属性
dest.dup = l.dup
dest.free = l.free
dest.match = l.match
//通过源链表获取迭代器
iter := ListGetIterator(l, AL_START_HEAD)
for current:=iter.Next();nil!=current;current=iter.Next() {
var value interface{}
if nil != l.dup {//链表存在复制函数
value = l.dup(current.GetValue())
} else {
value = current.GetValue()
}
//从表尾插入
dest.AddNodeTail(value)
}
//释放掉迭代器
ListReleaseIterator(iter)
return dest
}- 链表迭代器
实际上，上文中的代码已经涉及到了迭代器的使用，迭代器有两个属性，next指向迭代节点，direction为迭代方向（表头or表尾）
代码语言：javascript复制//迭代器
type listIter struct {
//指向迭代节点，通过Next方法返回
next *listNode
//迭代方向
direction int
}1.为某个链表创建迭代器
代码语言：javascript复制//获取迭代器
func ListGetIterator(l *list, direction int) *listIter {
var listIter = &listIter{direction: direction}
if direction == AL_START_HEAD {//从表头开始迭代
listIter.next = l.head
} else {//从表尾开始迭代
listIter.next = l.tail
}
return listIter
}2.返回迭代器当前指向节点
代码语言：javascript复制//返回迭代器当前所指向的节点
func (iter *listIter) Next() *listNode {
//获取迭代器下一个节点作为当前节点
current := iter.next
if nil != current {
if iter.direction == AL_START_HEAD { //从头方向迭代
iter.next = current.next
} else { //从尾方向迭代
iter.next = current.pre
}
}
return current
}- 综述
adlist体现了Redis精简干练的风格，不到600行的代码读起来让人身心愉悦。尤其是在实现了迭代器之后，可以通过它来实现各种遍历方法，比如：
代码语言：javascript复制//打印链表
func (l *list) Print(direction int) {
//获取迭代器
iter := ListGetIterator(l, direction)
for cur:=iter.Next();nil!=cur;cur=iter.Next(){
fmt.Println(cur.GetValue())
}
}
