GoLang完整實(shí)現(xiàn)快速列表

更新時(shí)間：2022年12月17日 15:18:00 作者：Onemorelight95

這篇文章主要介紹了GoLang完整實(shí)現(xiàn)快速列表，列表是一種非連續(xù)的存儲(chǔ)容器，由多個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)通過(guò)一些變量記錄彼此之間的關(guān)系，列表有多種實(shí)現(xiàn)方法，如單鏈表、雙鏈表等

快速列表介紹

快速列表（quicklist）是Redis中特有的一種數(shù)據(jù)結(jié)構(gòu)，主要是為了解決雙端鏈表的弊端：雙端鏈表的附加空間比較高，因?yàn)?code>prev和next指針會(huì)占掉一部分的空間（64位系統(tǒng)占用8 + 8 = 16字節(jié)）.而且鏈表的每個(gè)節(jié)點(diǎn)都是單獨(dú)分配內(nèi)存，會(huì)加劇內(nèi)存的碎片化。

Redis中的快速列表實(shí)際上是zipList（經(jīng)過(guò)優(yōu)化過(guò)的數(shù)組）和linkedList的混合體，它把zipList放在linkedList的每個(gè)結(jié)點(diǎn)中，實(shí)現(xiàn)緊湊存儲(chǔ)。如下圖所示：

實(shí)現(xiàn)快速列表

快速列表的結(jié)構(gòu)

由于Go語(yǔ)言自帶slice這種操作方便的“動(dòng)態(tài)數(shù)組”結(jié)構(gòu)，所以我給鏈表的每個(gè)節(jié)點(diǎn)中都分配一個(gè)容量為1024大小的切片，那么一個(gè)鏈表節(jié)點(diǎn)就可以看作是一頁(yè)，頁(yè)大小就是1024。

頁(yè)大小

首先定義頁(yè)大小為1024：

// pageSize 一頁(yè)的大小
const pageSize = 1024

表頭結(jié)構(gòu)

// QuickList 快速列表是在頁(yè)（切片）之上建立的鏈表
// QuickList 比普通鏈表的插入、遍歷以及內(nèi)存有著更好的性能
type QuickList struct {
	data *list.List // 每一頁(yè)就是interface{}的切片，大小為1024
	size int
}

表頭結(jié)構(gòu)中的data字段直接使用了Go語(yǔ)言list包中的List結(jié)構(gòu)：

// 雙向鏈表標(biāo)頭結(jié)構(gòu)
type List struct {
	root Element // 哨兵節(jié)點(diǎn)
	len  int     // 鏈表的節(jié)點(diǎn)個(gè)數(shù)
}

// 雙向鏈表的節(jié)點(diǎn)
type Element struct {
	// 前向和后向指針
	next, prev *Element
	// 表頭結(jié)構(gòu)
	list *List
	// 值域
	Value interface{}
}

Go語(yǔ)言自帶的list包實(shí)現(xiàn)了對(duì)雙向鏈表的封裝，雙向鏈表的節(jié)點(diǎn)元素是interface{}類型，利用這種方式實(shí)現(xiàn)了泛型。

我們對(duì)快速列表的實(shí)現(xiàn)，使得上述雙向鏈表節(jié)點(diǎn)中存儲(chǔ)的實(shí)際上是容量為1024的切片，此后對(duì)于鏈表的相關(guān)操作，直接調(diào)用list包向外暴露的API即可。

快速列表的迭代器

快速列表的迭代器中有三個(gè)字段：鏈表的節(jié)點(diǎn)node（可以看成一頁(yè)），元素在頁(yè)中的偏移量、表頭結(jié)構(gòu)。

這樣實(shí)現(xiàn)的迭代器，使得迭代器既可以在元素之前迭代，也可以在頁(yè)之間快速迭代。

// iterator 快速列表的迭代器，在[-1, ql.Len()]之間迭代
type iterator struct {
	// 快速列表的一頁(yè)
	node *list.Element
	// 元素下標(biāo)在頁(yè)中的偏移量
	offset int
	ql     *QuickList
}

使用迭代器返回一個(gè)元素

使用迭代器返回一個(gè)元素的復(fù)雜度為O(1)，一個(gè)元素的位置可以通過(guò) 頁(yè)的位置 + 該元素在頁(yè)中的位置快速定位。

// 使用迭代器返回一個(gè)元素
func (iter *iterator) get() interface{} {
	return iter.page()[iter.offset]
}

返回迭代器對(duì)應(yīng)的那一頁(yè)

上面我們說(shuō)過(guò)，鏈表的節(jié)點(diǎn)元素其實(shí)就是一個(gè)容量為1024的slice，通過(guò)類型斷言直接返回即可。

// 返回迭代器對(duì)應(yīng)的那一頁(yè)
func (iter *iterator) page() []interface{} {
	return iter.node.Value.([]interface{})
}

根據(jù)元素下標(biāo)返回對(duì)應(yīng)的迭代器

快速列表查找元素效率比雙向列表要快，首先利用迭代器一頁(yè)一頁(yè)進(jìn)行迭代，當(dāng)確定了元素在哪一頁(yè)后，利用元素的下標(biāo)直接在頁(yè)內(nèi)的slice中直接定位即可。

func (ql *QuickList) find(index int) *iterator {
	if ql == nil {
		panic("list is nil")
	}
	if index < 0 || index >= ql.size {
		panic("index out of bound")
	}
	var n *list.Element
	// 保存當(dāng)前頁(yè)的所有元素
	var page []interface{}
	// 累加遍歷到當(dāng)前頁(yè)為止，前面的所有元素?cái)?shù)量
	var pageBeg int
	if index < ql.size/2 {
		// 從表頭進(jìn)行查找
		n = ql.data.Front()
		pageBeg = 0
		for {
			page = n.Value.([]interface{})
			if pageBeg+len(page) > index {
				break
			}
			pageBeg += len(page)
			n = n.Next()
		}
	} else {
		// 從表尾進(jìn)行查找
		n = ql.data.Back()
		pageBeg = ql.size
		for {
			page = n.Value.([]interface{})
			pageBeg -= len(page)
			if pageBeg <= index {
				break
			}
			n = n.Prev()
		}
	}
	pageOffset := index - pageBeg
	return &iterator{
		node:   n,
		offset: pageOffset,
		ql:     ql,
	}
}

向后迭代一位

// next 頁(yè)內(nèi)迭代器，向后迭代一位
// 如果當(dāng)前元素下標(biāo)未出界且不在最后一位，就向后移動(dòng)一位，返回true
// 如果當(dāng)前元素下標(biāo)在快速列表的最后一頁(yè)且是最后一個(gè)元素，直接返回false
// 如果當(dāng)前元素下標(biāo)不在快速列表的最后一頁(yè)，但是是當(dāng)前頁(yè)的最后一個(gè)元素，跳轉(zhuǎn)到下一頁(yè)，返回true
func (iter *iterator) next() bool {
	// 得到迭代器對(duì)應(yīng)的那一頁(yè)
	page := iter.page()
	// 當(dāng)前位置未出界且不在最后一位，就向后移動(dòng)一位，返回true
	if iter.offset < len(page)-1 {
		iter.offset++
		return true
	}
	// 當(dāng)前元素在快速列表的最后一頁(yè)且是最后一個(gè)元素，直接返回false
	if iter.node == iter.ql.data.Back() {
		// already at last node
		iter.offset = len(page)
		return false
	}
	// 當(dāng)前元素不在快速列表的最后一頁(yè)，但是是當(dāng)前頁(yè)的最后一個(gè)元素，跳轉(zhuǎn)到下一頁(yè)，返回true
	iter.offset = 0
	iter.node = iter.node.Next()
	return true
}

往前迭代一位

// prev 頁(yè)內(nèi)迭代器，向前迭代一位
func (iter *iterator) prev() bool {
	if iter.offset > 0 {
		iter.offset--
		return true
	}
	if iter.node == iter.ql.data.Front() {
		iter.offset = -1
		return false
	}
	iter.node = iter.node.Prev()
	prevPage := iter.node.Value.([]interface{})
	iter.offset = len(prevPage) - 1
	return true
}

添加和插入元素

向表尾添加一個(gè)元素

向表尾添加元素需要考慮三種情況：

列表是空的，創(chuàng)建新的一頁(yè)，添加到表尾即可。
表尾節(jié)點(diǎn)那一頁(yè)是滿的，獲取表尾節(jié)點(diǎn)，創(chuàng)建新的一頁(yè)，添加到表尾節(jié)點(diǎn)的后面即可。
表尾節(jié)點(diǎn)那一頁(yè)不是滿的，正常添加到表尾即可。

// Add 添加元素到表尾
func (ql *QuickList) Add(val interface{}) {
	ql.size++
	// 列表是空的
	if ql.data.Len() == 0 {
		page := make([]interface{}, 0, pageSize)
		page = append(page, val)
		ql.data.PushBack(page)
		return
	}
	// 獲取表尾節(jié)點(diǎn)
	backNode := ql.data.Back()
	backPage := backNode.Value.([]interface{})
	// 表尾節(jié)點(diǎn)頁(yè)滿了，需要新創(chuàng)建一頁(yè)
	if len(backPage) == cap(backPage) {
		page := make([]interface{}, 0, pageSize)
		page = append(page, val)
		ql.data.PushBack(page)
		return
	}
	// 默認(rèn)將節(jié)點(diǎn)添加進(jìn)表尾頁(yè)中
	backPage = append(backPage, val)
	backNode.Value = backPage
}

根據(jù)下標(biāo)插入一個(gè)元素

// Insert 插入元素
// 插入元素的策略分三種情況：
// 1. 向最后一頁(yè)的最后一個(gè)位置插入元素，直接掉用ql.Add()插入即可
// 2. 某一頁(yè)插入一個(gè)元素，且該頁(yè)未滿，直接插入該頁(yè)即可
// 3. 某一頁(yè)插入一個(gè)元素，該頁(yè)滿了，就新創(chuàng)建一頁(yè)，然后將前512個(gè)元素留在原來(lái)那頁(yè)，將后512個(gè)元素移到新的頁(yè)中，
//    新插入的元素，如果下標(biāo)在[0,512]之間，就插入到原來(lái)頁(yè)，如果下標(biāo)在[516, 1024]之間，就插入到新創(chuàng)建的頁(yè)中
func (ql *QuickList) Insert(index int, val interface{}) {
	// 向表尾插入元素
	if index == ql.size {
		ql.Add(val)
		return
	}
	iter := ql.find(index)
	page := iter.node.Value.([]interface{})
	// 如果待插入頁(yè)的元素小于1024，直接插入到該頁(yè)即可
	if len(page) < pageSize {
		// insert into not full page
		page = append(page[:iter.offset+1], page[iter.offset:]...)
		page[iter.offset] = val
		iter.node.Value = page
		ql.size++
		return
	}
	// 待插入頁(yè)的元素已經(jīng)滿1024，就需要新創(chuàng)建一頁(yè)
	var nextPage []interface{}
	// 后一半的元素放在新創(chuàng)建的頁(yè)中，前一半元素放在原來(lái)的頁(yè)中
	nextPage = append(nextPage, page[pageSize/2:]...) // pageSize must be even
	page = page[:pageSize/2]
	// 待插入元素的下標(biāo)小于512，插到前面那頁(yè)
	if iter.offset < len(page) {
		page = append(page[:iter.offset+1], page[iter.offset:]...)
		page[iter.offset] = val
	} else {
		// 待插入元素的下標(biāo)大于512，插到后面那頁(yè)
		i := iter.offset - pageSize/2
		nextPage = append(nextPage[:i+1], nextPage[i:]...)
		nextPage[i] = val
	}
	// 儲(chǔ)存當(dāng)前頁(yè)和新創(chuàng)建的下一頁(yè)
	iter.node.Value = page
	ql.data.InsertAfter(nextPage, iter.node)
	ql.size++
}

刪除元素

// 刪除元素
// 刪除元素分為三種情況：
// 1.刪除后的頁(yè)不為空，且刪除的不是該頁(yè)的最后一個(gè)元素，什么都不用管
// 2.刪除后的頁(yè)不為空，且刪除的是該頁(yè)的最后一個(gè)元素，需要將迭代器移動(dòng)到下一頁(yè)的最后一個(gè)元素
// 3.刪除的頁(yè)為空（需要?jiǎng)h除該頁(yè)），且刪除的頁(yè)是最后一頁(yè)，將迭代器置空
// 4.刪除的頁(yè)為空（需要?jiǎng)h除該頁(yè)），且刪除的頁(yè)不是最后一頁(yè)，將迭代器指向下一頁(yè)
func (iter *iterator) remove() interface{} {
	page := iter.page()
	val := page[iter.offset]
	// 先直接在頁(yè)中刪除這個(gè)元素
	page = append(page[:iter.offset], page[iter.offset+1:]...)
	// 如果刪除后的頁(yè)不為空，只更新iter.offset即可
	if len(page) > 0 {
		iter.node.Value = page
		// 如果刪除的是頁(yè)中的最后一個(gè)元素，那么迭代器需要移動(dòng)到下一頁(yè)的第一個(gè)元素
		if iter.offset == len(page) {
			if iter.node != iter.ql.data.Back() {
				iter.node = iter.node.Next()
				iter.offset = 0
			}
		}
	} else {
		// 如果刪除后的頁(yè)為空，需要?jiǎng)h除該頁(yè)
		// 如果刪除的是最后一頁(yè)，迭代器需要置空
		if iter.node == iter.ql.data.Back() {
			iter.ql.data.Remove(iter.node)
			iter.node = nil
			iter.offset = 0
		} else {
			// 如果刪除的不是最后一頁(yè)，迭代器需要指向下一頁(yè)
			nextNode := iter.node.Next()
			iter.ql.data.Remove(iter.node)
			iter.node = nextNode
			iter.offset = 0
		}
	}
	iter.ql.size--
	return val
}

遍歷快速列表

// Consumer 用于遍歷中斷的函數(shù)，返回true表示繼續(xù)遍歷，可以在Consumer中調(diào)用自定義函數(shù)
type Consumer func(i int, v interface{}) bool

// ForEach 遍歷快速列表中的元素
// 如果consumer返回false，結(jié)束遍歷
func (ql *QuickList) ForEach(consumer Consumer) {
	if ql == nil {
		panic("list is nil")
	}
	if ql.Len() == 0 {
		return
	}
	iter := ql.find(0)
	i := 0
	for {
		goNext := consumer(i, iter.get())
		if !goNext {
			break
		}
		i++
		// 遍歷到表尾，結(jié)束
		if !iter.next() {
			break
		}
	}
}