列表与跳表实现

学习目标

深入理解双向链表的实现和优化技巧
掌握跳跃表的原理和概率分析
实现完整的跳表插入、删除、查找算法
理解 quicklist 的设计思想和实现
对比分析跳表与平衡树的性能差异

双向链表实现

1. 链表结构设计

双向链表是 Redis 列表的基础数据结构，支持 O(1) 的头部和尾部操作：

// list/doubly_linked_list.go
package list

import (
    "fmt"
    "sync"
)

// 链表节点
type ListNode struct {
    value interface{}
    prev  *ListNode
    next  *ListNode
}

// 双向链表
type DoublyLinkedList struct {
    head   *ListNode
    tail   *ListNode
    length int
    mu     sync.RWMutex
}

// 创建新链表
func NewDoublyLinkedList() *DoublyLinkedList {
    return &DoublyLinkedList{
        head:   nil,
        tail:   nil,
        length: 0,
    }
}

// 创建新节点
func newNode(value interface{}) *ListNode {
    return &ListNode{
        value: value,
        prev:  nil,
        next:  nil,
    }
}

2. 基础操作实现

// list/basic_operations.go
package list

// 在头部插入
func (dll *DoublyLinkedList) PushFront(value interface{}) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    newNode := newNode(value)
    
    if dll.head == nil {
        // 空链表
        dll.head = newNode
        dll.tail = newNode
    } else {
        // 非空链表
        newNode.next = dll.head
        dll.head.prev = newNode
        dll.head = newNode
    }
    
    dll.length++
}

// 在尾部插入
func (dll *DoublyLinkedList) PushBack(value interface{}) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    newNode := newNode(value)
    
    if dll.tail == nil {
        // 空链表
        dll.head = newNode
        dll.tail = newNode
    } else {
        // 非空链表
        newNode.prev = dll.tail
        dll.tail.next = newNode
        dll.tail = newNode
    }
    
    dll.length++
}

// 在指定位置插入
func (dll *DoublyLinkedList) Insert(index int, value interface{}) error {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if index < 0 || index > dll.length {
        return fmt.Errorf("index out of range")
    }
    
    if index == 0 {
        dll.PushFront(value)
        return nil
    }
    
    if index == dll.length {
        dll.PushBack(value)
        return nil
    }
    
    // 找到插入位置
    current := dll.head
    for i := 0; i < index; i++ {
        current = current.next
    }
    
    // 创建新节点
    newNode := newNode(value)
    newNode.prev = current.prev
    newNode.next = current
    current.prev.next = newNode
    current.prev = newNode
    
    dll.length++
    return nil
}

// 从头部弹出
func (dll *DoublyLinkedList) PopFront() (interface{}, error) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if dll.head == nil {
        return nil, fmt.Errorf("list is empty")
    }
    
    value := dll.head.value
    
    if dll.head == dll.tail {
        // 只有一个节点
        dll.head = nil
        dll.tail = nil
    } else {
        // 多个节点
        dll.head = dll.head.next
        dll.head.prev = nil
    }
    
    dll.length--
    return value, nil
}

// 从尾部弹出
func (dll *DoublyLinkedList) PopBack() (interface{}, error) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if dll.tail == nil {
        return nil, fmt.Errorf("list is empty")
    }
    
    value := dll.tail.value
    
    if dll.head == dll.tail {
        // 只有一个节点
        dll.head = nil
        dll.tail = nil
    } else {
        // 多个节点
        dll.tail = dll.tail.prev
        dll.tail.next = nil
    }
    
    dll.length--
    return value, nil
}

// 删除指定位置的元素
func (dll *DoublyLinkedList) Remove(index int) (interface{}, error) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if index < 0 || index >= dll.length {
        return nil, fmt.Errorf("index out of range")
    }
    
    if index == 0 {
        return dll.PopFront()
    }
    
    if index == dll.length-1 {
        return dll.PopBack()
    }
    
    // 找到要删除的节点
    current := dll.head
    for i := 0; i < index; i++ {
        current = current.next
    }
    
    // 删除节点
    current.prev.next = current.next
    current.next.prev = current.prev
    
    dll.length--
    return current.value, nil
}

// 获取指定位置的元素
func (dll *DoublyLinkedList) Get(index int) (interface{}, error) {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    
    if index < 0 || index >= dll.length {
        return nil, fmt.Errorf("index out of range")
    }
    
    // 优化：从头部或尾部开始遍历
    if index < dll.length/2 {
        // 从头部开始
        current := dll.head
        for i := 0; i < index; i++ {
            current = current.next
        }
        return current.value, nil
    } else {
        // 从尾部开始
        current := dll.tail
        for i := dll.length - 1; i > index; i-- {
            current = current.prev
        }
        return current.value, nil
    }
}

// 设置指定位置的元素
func (dll *DoublyLinkedList) Set(index int, value interface{}) error {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if index < 0 || index >= dll.length {
        return fmt.Errorf("index out of range")
    }
    
    // 找到节点
    current := dll.head
    for i := 0; i < index; i++ {
        current = current.next
    }
    
    current.value = value
    return nil
}

// 获取链表长度
func (dll *DoublyLinkedList) Length() int {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    return dll.length
}

// 检查是否为空
func (dll *DoublyLinkedList) IsEmpty() bool {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    return dll.length == 0
}

// 清空链表
func (dll *DoublyLinkedList) Clear() {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    dll.head = nil
    dll.tail = nil
    dll.length = 0
}

3. 高级操作实现

// list/advanced_operations.go
package list

// 查找元素
func (dll *DoublyLinkedList) Find(value interface{}) int {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    
    current := dll.head
    index := 0
    
    for current != nil {
        if current.value == value {
            return index
        }
        current = current.next
        index++
    }
    
    return -1
}

// 查找所有匹配的元素
func (dll *DoublyLinkedList) FindAll(value interface{}) []int {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    
    var indices []int
    current := dll.head
    index := 0
    
    for current != nil {
        if current.value == value {
            indices = append(indices, index)
        }
        current = current.next
        index++
    }
    
    return indices
}

// 删除所有匹配的元素
func (dll *DoublyLinkedList) RemoveAll(value interface{}) int {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    count := 0
    current := dll.head
    
    for current != nil {
        next := current.next
        
        if current.value == value {
            // 删除当前节点
            if current.prev == nil {
                // 头部节点
                dll.head = current.next
                if dll.head != nil {
                    dll.head.prev = nil
                }
            } else {
                current.prev.next = current.next
            }
            
            if current.next == nil {
                // 尾部节点
                dll.tail = current.prev
                if dll.tail != nil {
                    dll.tail.next = nil
                }
            } else {
                current.next.prev = current.prev
            }
            
            dll.length--
            count++
        }
        
        current = next
    }
    
    return count
}

// 反转链表
func (dll *DoublyLinkedList) Reverse() {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    current := dll.head
    var prev *ListNode
    
    for current != nil {
        next := current.next
        current.next = prev
        current.prev = next
        prev = current
        current = next
    }
    
    // 交换头部和尾部
    dll.head, dll.tail = dll.tail, dll.head
}

// 获取子链表
func (dll *DoublyLinkedList) SubList(start, end int) (*DoublyLinkedList, error) {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    
    if start < 0 || end > dll.length || start > end {
        return nil, fmt.Errorf("invalid range")
    }
    
    subList := NewDoublyLinkedList()
    current := dll.head
    
    // 移动到起始位置
    for i := 0; i < start; i++ {
        current = current.next
    }
    
    // 复制元素
    for i := start; i < end; i++ {
        subList.PushBack(current.value)
        current = current.next
    }
    
    return subList, nil
}

// 合并两个链表
func (dll *DoublyLinkedList) Merge(other *DoublyLinkedList) {
    dll.mu.Lock()
    defer dll.mu.Unlock()
    
    if other.head == nil {
        return
    }
    
    if dll.head == nil {
        dll.head = other.head
        dll.tail = other.tail
        dll.length = other.length
    } else {
        dll.tail.next = other.head
        other.head.prev = dll.tail
        dll.tail = other.tail
        dll.length += other.length
    }
    
    // 清空另一个链表
    other.head = nil
    other.tail = nil
    other.length = 0
}

// 转换为切片
func (dll *DoublyLinkedList) ToSlice() []interface{} {
    dll.mu.RLock()
    defer dll.mu.RUnlock()
    
    result := make([]interface{}, dll.length)
    current := dll.head
    index := 0
    
    for current != nil {
        result[index] = current.value
        current = current.next
        index++
    }
    
    return result
}

// 从切片创建链表
func NewDoublyLinkedListFromSlice(slice []interface{}) *DoublyLinkedList {
    dll := NewDoublyLinkedList()
    
    for _, value := range slice {
        dll.PushBack(value)
    }
    
    return dll
}

跳跃表实现

1. 跳表结构设计

跳跃表是一种概率数据结构，通过多层链表实现 O(log n) 的查找、插入和删除操作：

// skiplist/skiplist.go
package skiplist

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

// 跳表节点
type SkipListNode struct {
    key     interface{}
    value   interface{}
    score   float64
    level   int
    forward []*SkipListNode
}

// 跳跃表
type SkipList struct {
    header   *SkipListNode
    tail     *SkipListNode
    length   int
    level    int
    maxLevel int
    mu       sync.RWMutex
}

// 创建新节点
func newNode(key, value interface{}, score float64, level int) *SkipListNode {
    return &SkipListNode{
        key:     key,
        value:   value,
        score:   score,
        level:   level,
        forward: make([]*SkipListNode, level+1),
    }
}

// 创建跳跃表
func NewSkipList(maxLevel int) *SkipList {
    if maxLevel <= 0 {
        maxLevel = 16
    }
    
    // 创建头节点
    header := newNode(nil, nil, 0, maxLevel)
    
    return &SkipList{
        header:   header,
        tail:     nil,
        length:   0,
        level:    0,
        maxLevel: maxLevel,
    }
}

// 随机生成层数
func (sl *SkipList) randomLevel() int {
    level := 0
    for rand.Float64() < 0.5 && level < sl.maxLevel {
        level++
    }
    return level
}

2. 查找操作实现

// skiplist/search.go
package skiplist

// 查找节点
func (sl *SkipList) Search(key interface{}) (interface{}, bool) {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    node := sl.searchNode(key)
    if node != nil {
        return node.value, true
    }
    
    return nil, false
}

// 查找节点（内部方法）
func (sl *SkipList) searchNode(key interface{}) *SkipListNode {
    current := sl.header
    
    // 从最高层开始搜索
    for i := sl.level; i >= 0; i-- {
        // 在当前层向前搜索
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, key) < 0 {
            current = current.forward[i]
        }
    }
    
    // 移动到下一个节点
    current = current.forward[0]
    
    // 检查是否找到
    if current != nil && sl.compare(current.key, key) == 0 {
        return current
    }
    
    return nil
}

// 比较函数
func (sl *SkipList) compare(key1, key2 interface{}) int {
    switch k1 := key1.(type) {
    case string:
        if k2, ok := key2.(string); ok {
            if k1 < k2 {
                return -1
            } else if k1 > k2 {
                return 1
            }
            return 0
        }
    case int:
        if k2, ok := key2.(int); ok {
            if k1 < k2 {
                return -1
            } else if k1 > k2 {
                return 1
            }
            return 0
        }
    case float64:
        if k2, ok := key2.(float64); ok {
            if k1 < k2 {
                return -1
            } else if k1 > k2 {
                return 1
            }
            return 0
        }
    }
    
    // 默认字符串比较
    s1 := fmt.Sprintf("%v", key1)
    s2 := fmt.Sprintf("%v", key2)
    if s1 < s2 {
        return -1
    } else if s1 > s2 {
        return 1
    }
    return 0
}

// 查找范围
func (sl *SkipList) SearchRange(start, end interface{}) []interface{} {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    var result []interface{}
    current := sl.findFirst(start)
    
    for current != nil && sl.compare(current.key, end) <= 0 {
        result = append(result, current.value)
        current = current.forward[0]
    }
    
    return result
}

// 查找第一个大于等于指定键的节点
func (sl *SkipList) findFirst(key interface{}) *SkipListNode {
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, key) < 0 {
            current = current.forward[i]
        }
    }
    
    return current.forward[0]
}

3. 插入操作实现

// skiplist/insert.go
package skiplist

// 插入节点
func (sl *SkipList) Insert(key, value interface{}) error {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    // 查找插入位置
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, key) < 0 {
            current = current.forward[i]
        }
        update[i] = current
    }
    
    current = current.forward[0]
    
    // 如果键已存在，更新值
    if current != nil && sl.compare(current.key, key) == 0 {
        current.value = value
        return nil
    }
    
    // 生成随机层数
    level := sl.randomLevel()
    
    // 如果新层数大于当前层数，更新头节点
    if level > sl.level {
        for i := sl.level + 1; i <= level; i++ {
            update[i] = sl.header
        }
        sl.level = level
    }
    
    // 创建新节点
    newNode := newNode(key, value, 0, level)
    
    // 插入节点
    for i := 0; i <= level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
    
    // 更新尾节点
    if newNode.forward[0] == nil {
        sl.tail = newNode
    }
    
    sl.length++
    return nil
}

// 插入带分数的节点
func (sl *SkipList) InsertWithScore(key, value interface{}, score float64) error {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    // 查找插入位置
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            (current.forward[i].score < score || 
             (current.forward[i].score == score && 
              sl.compare(current.forward[i].key, key) < 0)) {
            current = current.forward[i]
        }
        update[i] = current
    }
    
    current = current.forward[0]
    
    // 如果键已存在，更新值
    if current != nil && sl.compare(current.key, key) == 0 {
        current.value = value
        current.score = score
        return nil
    }
    
    // 生成随机层数
    level := sl.randomLevel()
    
    // 如果新层数大于当前层数，更新头节点
    if level > sl.level {
        for i := sl.level + 1; i <= level; i++ {
            update[i] = sl.header
        }
        sl.level = level
    }
    
    // 创建新节点
    newNode := newNode(key, value, score, level)
    
    // 插入节点
    for i := 0; i <= level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
    
    // 更新尾节点
    if newNode.forward[0] == nil {
        sl.tail = newNode
    }
    
    sl.length++
    return nil
}

4. 删除操作实现

// skiplist/delete.go
package skiplist

// 删除节点
func (sl *SkipList) Delete(key interface{}) bool {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    // 查找删除位置
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, key) < 0 {
            current = current.forward[i]
        }
        update[i] = current
    }
    
    current = current.forward[0]
    
    // 如果找到节点，删除它
    if current != nil && sl.compare(current.key, key) == 0 {
        // 更新前驱节点的指针
        for i := 0; i <= current.level; i++ {
            update[i].forward[i] = current.forward[i]
        }
        
        // 更新尾节点
        if current == sl.tail {
            if current.level > 0 {
                sl.tail = update[0]
            } else {
                sl.tail = nil
            }
        }
        
        // 更新层数
        for sl.level > 0 && sl.header.forward[sl.level] == nil {
            sl.level--
        }
        
        sl.length--
        return true
    }
    
    return false
}

// 删除范围
func (sl *SkipList) DeleteRange(start, end interface{}) int {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    count := 0
    current := sl.findFirst(start)
    
    for current != nil && sl.compare(current.key, end) <= 0 {
        next := current.forward[0]
        sl.deleteNode(current)
        current = next
        count++
    }
    
    return count
}

// 删除节点（内部方法）
func (sl *SkipList) deleteNode(node *SkipListNode) {
    // 查找前驱节点
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, node.key) < 0 {
            current = current.forward[i]
        }
        update[i] = current
    }
    
    // 更新前驱节点的指针
    for i := 0; i <= node.level; i++ {
        update[i].forward[i] = node.forward[i]
    }
    
    // 更新尾节点
    if node == sl.tail {
        if node.level > 0 {
            sl.tail = update[0]
        } else {
            sl.tail = nil
        }
    }
    
    // 更新层数
    for sl.level > 0 && sl.header.forward[sl.level] == nil {
        sl.level--
    }
    
    sl.length--
}

5. 范围查询实现

// skiplist/range.go
package skiplist

// 获取排名
func (sl *SkipList) GetRank(key interface{}) int {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    rank := 0
    current := sl.header
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            sl.compare(current.forward[i].key, key) < 0 {
            rank += (1 << i)
            current = current.forward[i]
        }
    }
    
    current = current.forward[0]
    if current != nil && sl.compare(current.key, key) == 0 {
        return rank
    }
    
    return -1
}

// 根据排名获取节点
func (sl *SkipList) GetByRank(rank int) (interface{}, bool) {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    if rank < 0 || rank >= sl.length {
        return nil, false
    }
    
    current := sl.header
    currentRank := 0
    
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            currentRank+(1<<i) <= rank {
            currentRank += (1 << i)
            current = current.forward[i]
        }
    }
    
    return current.value, true
}

// 获取范围排名
func (sl *SkipList) GetRangeByRank(start, end int) []interface{} {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    if start < 0 || end >= sl.length || start > end {
        return nil
    }
    
    var result []interface{}
    current := sl.header
    currentRank := 0
    
    // 移动到起始位置
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            currentRank+(1<<i) <= start {
            currentRank += (1 << i)
            current = current.forward[i]
        }
    }
    
    // 收集范围内的节点
    for i := start; i <= end; i++ {
        if current != nil {
            result = append(result, current.value)
            current = current.forward[0]
        }
    }
    
    return result
}

// 获取分数范围
func (sl *SkipList) GetRangeByScore(minScore, maxScore float64) []interface{} {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    var result []interface{}
    current := sl.header
    
    // 移动到起始位置
    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && 
            current.forward[i].score < minScore {
            current = current.forward[i]
        }
    }
    
    // 收集范围内的节点
    current = current.forward[0]
    for current != nil && current.score <= maxScore {
        result = append(result, current.value)
        current = current.forward[0]
    }
    
    return result
}

QuickList 实现

1. QuickList 结构设计

QuickList 是 Redis 3.2 引入的列表实现，结合了双向链表和压缩列表的优点：

// quicklist/quicklist.go
package quicklist

import (
    "fmt"
    "sync"
)

// 压缩列表节点
type ZipListNode struct {
    data []byte
    len  int
}

// 压缩列表
type ZipList struct {
    data   []byte
    length int
    tail   int
}

// QuickList 节点
type QuickListNode struct {
    prev *QuickListNode
    next *QuickListNode
    zl   *ZipList
    size int
}

// QuickList
type QuickList struct {
    head   *QuickListNode
    tail   *QuickListNode
    length int
    count  int
    mu     sync.RWMutex
}

// 创建 QuickList
func NewQuickList() *QuickList {
    return &QuickList{
        head:   nil,
        tail:   nil,
        length: 0,
        count:  0,
    }
}

// 创建压缩列表
func NewZipList() *ZipList {
    return &ZipList{
        data:   make([]byte, 0),
        length: 0,
        tail:   0,
    }
}

2. 压缩列表操作

// quicklist/ziplist.go
package quicklist

// 压缩列表插入
func (zl *ZipList) Insert(index int, value []byte) error {
    if index < 0 || index > zl.length {
        return fmt.Errorf("index out of range")
    }
    
    // 简化的插入实现
    if index == zl.length {
        zl.data = append(zl.data, value...)
        zl.length++
        return nil
    }
    
    // 在中间插入
    newData := make([]byte, 0, len(zl.data)+len(value))
    newData = append(newData, zl.data[:index]...)
    newData = append(newData, value...)
    newData = append(newData, zl.data[index:]...)
    
    zl.data = newData
    zl.length++
    return nil
}

// 压缩列表删除
func (zl *ZipList) Delete(index int) error {
    if index < 0 || index >= zl.length {
        return fmt.Errorf("index out of range")
    }
    
    // 简化的删除实现
    if index == zl.length-1 {
        zl.data = zl.data[:len(zl.data)-1]
        zl.length--
        return nil
    }
    
    // 在中间删除
    newData := make([]byte, 0, len(zl.data)-1)
    newData = append(newData, zl.data[:index]...)
    newData = append(newData, zl.data[index+1:]...)
    
    zl.data = newData
    zl.length--
    return nil
}

// 压缩列表获取
func (zl *ZipList) Get(index int) ([]byte, error) {
    if index < 0 || index >= zl.length {
        return nil, fmt.Errorf("index out of range")
    }
    
    // 简化的获取实现
    return zl.data[index:index+1], nil
}

// 压缩列表长度
func (zl *ZipList) Length() int {
    return zl.length
}

3. QuickList 操作

// quicklist/operations.go
package quicklist

// 在头部插入
func (ql *QuickList) PushFront(value []byte) {
    ql.mu.Lock()
    defer ql.mu.Unlock()
    
    if ql.head == nil {
        // 创建第一个节点
        node := &QuickListNode{
            zl:   NewZipList(),
            size: 0,
        }
        ql.head = node
        ql.tail = node
    }
    
    // 在头部节点的压缩列表中插入
    if ql.head.zl.Length() < 8 { // 假设最大长度为 8
        ql.head.zl.Insert(0, value)
        ql.head.size++
    } else {
        // 创建新节点
        newNode := &QuickListNode{
            next: ql.head,
            zl:   NewZipList(),
            size: 0,
        }
        ql.head.prev = newNode
        ql.head = newNode
        ql.head.zl.Insert(0, value)
        ql.head.size++
    }
    
    ql.count++
}

// 在尾部插入
func (ql *QuickList) PushBack(value []byte) {
    ql.mu.Lock()
    defer ql.mu.Unlock()
    
    if ql.tail == nil {
        // 创建第一个节点
        node := &QuickListNode{
            zl:   NewZipList(),
            size: 0,
        }
        ql.head = node
        ql.tail = node
    }
    
    // 在尾部节点的压缩列表中插入
    if ql.tail.zl.Length() < 8 { // 假设最大长度为 8
        ql.tail.zl.Insert(ql.tail.zl.Length(), value)
        ql.tail.size++
    } else {
        // 创建新节点
        newNode := &QuickListNode{
            prev: ql.tail,
            zl:   NewZipList(),
            size: 0,
        }
        ql.tail.next = newNode
        ql.tail = newNode
        ql.tail.zl.Insert(0, value)
        ql.tail.size++
    }
    
    ql.count++
}

// 从头部弹出
func (ql *QuickList) PopFront() ([]byte, error) {
    ql.mu.Lock()
    defer ql.mu.Unlock()
    
    if ql.head == nil {
        return nil, fmt.Errorf("list is empty")
    }
    
    // 从头部节点的压缩列表中弹出
    value, err := ql.head.zl.Get(0)
    if err != nil {
        return nil, err
    }
    
    ql.head.zl.Delete(0)
    ql.head.size--
    ql.count--
    
    // 如果头部节点为空，删除它
    if ql.head.zl.Length() == 0 {
        if ql.head == ql.tail {
            ql.head = nil
            ql.tail = nil
        } else {
            ql.head = ql.head.next
            ql.head.prev = nil
        }
    }
    
    return value, nil
}

// 从尾部弹出
func (ql *QuickList) PopBack() ([]byte, error) {
    ql.mu.Lock()
    defer ql.mu.Unlock()
    
    if ql.tail == nil {
        return nil, fmt.Errorf("list is empty")
    }
    
    // 从尾部节点的压缩列表中弹出
    value, err := ql.tail.zl.Get(ql.tail.zl.Length() - 1)
    if err != nil {
        return nil, err
    }
    
    ql.tail.zl.Delete(ql.tail.zl.Length() - 1)
    ql.tail.size--
    ql.count--
    
    // 如果尾部节点为空，删除它
    if ql.tail.zl.Length() == 0 {
        if ql.head == ql.tail {
            ql.head = nil
            ql.tail = nil
        } else {
            ql.tail = ql.tail.prev
            ql.tail.next = nil
        }
    }
    
    return value, nil
}

// 获取长度
func (ql *QuickList) Length() int {
    ql.mu.RLock()
    defer ql.mu.RUnlock()
    return ql.count
}

// 检查是否为空
func (ql *QuickList) IsEmpty() bool {
    ql.mu.RLock()
    defer ql.mu.RUnlock()
    return ql.count == 0
}

测试验证

1. 双向链表测试

// list/doubly_linked_list_test.go
package list

import (
    "testing"
)

func TestDoublyLinkedList(t *testing.T) {
    dll := NewDoublyLinkedList()
    
    // 测试插入
    dll.PushFront(1)
    dll.PushBack(2)
    dll.Insert(1, 3)
    
    if dll.Length() != 3 {
        t.Errorf("Expected length 3, got %d", dll.Length())
    }
    
    // 测试获取
    val, err := dll.Get(0)
    if err != nil || val != 1 {
        t.Errorf("Expected 1, got %v", val)
    }
    
    val, err = dll.Get(1)
    if err != nil || val != 3 {
        t.Errorf("Expected 3, got %v", val)
    }
    
    val, err = dll.Get(2)
    if err != nil || val != 2 {
        t.Errorf("Expected 2, got %v", val)
    }
    
    // 测试删除
    val, err = dll.PopFront()
    if err != nil || val != 1 {
        t.Errorf("Expected 1, got %v", val)
    }
    
    val, err = dll.PopBack()
    if err != nil || val != 2 {
        t.Errorf("Expected 2, got %v", val)
    }
    
    if dll.Length() != 1 {
        t.Errorf("Expected length 1, got %d", dll.Length())
    }
}

func TestDoublyLinkedListConcurrent(t *testing.T) {
    dll := NewDoublyLinkedList()
    
    // 并发测试
    done := make(chan bool)
    
    // 写入协程
    go func() {
        for i := 0; i < 1000; i++ {
            dll.PushBack(i)
        }
        done <- true
    }()
    
    // 读取协程
    go func() {
        for i := 0; i < 1000; i++ {
            dll.Get(i % dll.Length())
        }
        done <- true
    }()
    
    // 等待完成
    <-done
    <-done
    
    if dll.Length() != 1000 {
        t.Errorf("Expected length 1000, got %d", dll.Length())
    }
}

2. 跳跃表测试

// skiplist/skiplist_test.go
package skiplist

import (
    "testing"
)

func TestSkipList(t *testing.T) {
    sl := NewSkipList(16)
    
    // 测试插入
    sl.Insert("key1", "value1")
    sl.Insert("key2", "value2")
    sl.Insert("key3", "value3")
    
    if sl.Length() != 3 {
        t.Errorf("Expected length 3, got %d", sl.Length())
    }
    
    // 测试查找
    val, exists := sl.Search("key1")
    if !exists || val != "value1" {
        t.Errorf("Expected 'value1', got %v", val)
    }
    
    val, exists = sl.Search("key2")
    if !exists || val != "value2" {
        t.Errorf("Expected 'value2', got %v", val)
    }
    
    // 测试删除
    if !sl.Delete("key1") {
        t.Error("Failed to delete key1")
    }
    
    _, exists = sl.Search("key1")
    if exists {
        t.Error("Key1 should not exist after deletion")
    }
    
    if sl.Length() != 2 {
        t.Errorf("Expected length 2, got %d", sl.Length())
    }
}

func TestSkipListRange(t *testing.T) {
    sl := NewSkipList(16)
    
    // 插入测试数据
    for i := 0; i < 100; i++ {
        key := fmt.Sprintf("key%d", i)
        value := fmt.Sprintf("value%d", i)
        sl.Insert(key, value)
    }
    
    // 测试范围查询
    result := sl.SearchRange("key10", "key20")
    if len(result) != 11 {
        t.Errorf("Expected 11 results, got %d", len(result))
    }
    
    // 测试排名
    rank := sl.GetRank("key50")
    if rank != 50 {
        t.Errorf("Expected rank 50, got %d", rank)
    }
    
    // 测试根据排名获取
    val, exists := sl.GetByRank(25)
    if !exists || val != "value25" {
        t.Errorf("Expected 'value25', got %v", val)
    }
}

3. 性能基准测试

// list/benchmark_test.go
package list

import (
    "testing"
)

func BenchmarkDoublyLinkedListPushBack(b *testing.B) {
    dll := NewDoublyLinkedList()
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        dll.PushBack(i)
    }
}

func BenchmarkDoublyLinkedListPushFront(b *testing.B) {
    dll := NewDoublyLinkedList()
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        dll.PushFront(i)
    }
}

func BenchmarkDoublyLinkedListGet(b *testing.B) {
    dll := NewDoublyLinkedList()
    
    // 预填充数据
    for i := 0; i < 1000; i++ {
        dll.PushBack(i)
    }
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        dll.Get(i % 1000)
    }
}

func BenchmarkGoSliceAppend(b *testing.B) {
    var slice []int
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        slice = append(slice, i)
    }
}

func BenchmarkGoSlicePrepend(b *testing.B) {
    var slice []int
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        slice = append([]int{i}, slice...)
    }
}

性能对比分析

1. 操作复杂度对比

操作	双向链表	跳跃表	平衡树	说明
查找	O(n)	O(log n)	O(log n)	跳跃表概率性
插入	O(1)	O(log n)	O(log n)	链表在已知位置
删除	O(1)	O(log n)	O(log n)	链表在已知位置
范围查询	O(n)	O(log n + k)	O(log n + k)	k 为结果数量

2. 内存使用对比

特性	双向链表	跳跃表	平衡树	说明
内存开销	低	中等	中等	跳跃表需要额外指针
内存局部性	差	好	好	跳跃表节点连续
缓存友好性	差	好	好	跳跃表访问模式更好

3. 性能测试结果

// 基准测试结果示例
func BenchmarkComparison(b *testing.B) {
    // 双向链表性能
    b.Run("DoublyLinkedList", func(b *testing.B) {
        dll := NewDoublyLinkedList()
        for i := 0; i < b.N; i++ {
            dll.PushBack(i)
        }
    })
    
    // 跳跃表性能
    b.Run("SkipList", func(b *testing.B) {
        sl := NewSkipList(16)
        for i := 0; i < b.N; i++ {
            sl.Insert(i, i)
        }
    })
    
    // Go 切片性能
    b.Run("GoSlice", func(b *testing.B) {
        var slice []int
        for i := 0; i < b.N; i++ {
            slice = append(slice, i)
        }
    })
}