2B.md

块链表

上一节暴露了链表相对数组而言在访问效率上的不足，而本节则要把数组吸收进来以改造传统链表。此时链表节点中承载的不再是单个元素，而是一个数组。

type piece[T any] struct {
    fw, bw *piece[T]
    data   [PieceSize]T
}

双向队列

块链表强化了顺序访问性能，又保留了扩容的便利，很适宜用于构造双向对列。这实际上很容易，加两个游标就是了。

type deque[T any] struct {
    f, b struct {         //游标
        p *piece[T]
        i int
    }
    size int
}

func (dq *deque[T]) reset(block *piece[T]) {
    dq.size = 0
    block.fw, block.bw = nil, nil
    dq.f.p, dq.b.p = block, block
    dq.f.i, dq.b.i = PieceSize/2, PieceSize/2-1
}

func (dq *deque[T]) init() {
    dq.reset(new(piece[T]))
}

双向队列的主要操作就是插入和弹出：

func (dq *deque[T]) PushFront(unit T) {
    if dq.f.i == PieceSize {           //跨界
        dq.f.i = 0
        if dq.f.p.fw == nil {          //扩容
            block := new(piece[T])
            block.bw, block.fw = dq.f.p, nil
            dq.f.p.fw = block
        }
        dq.f.p = dq.f.p.fw
    }
    dq.f.p.data[dq.f.i] = unit
    dq.f.i++
    dq.size++
}

func (dq *deque[T]) PopFront() T {
    if dq.IsEmpty() {
        panic("empty deque")
    }
    dq.size--
    dq.f.i--
    unit := dq.f.p.data[dq.f.i]
    if dq.f.i == 0 {                    //跨界
        dq.f.i = PieceSize              //dq.f.idx永远不为0
        dq.f.p.fw = nil                 //只保留一块缓冲
        dq.f.p = dq.f.p.bw
    }
    return unit
}

//PushBack和PopBack类似

---

目录　上一节　下一节