Redis 的 List 很常拿來做 Message Queue，或是處理需要從頭尾推資料的場景。它本質上是一串二進位安全字串。

今天來做 List，先補最常用的 LPUSH、RPUSH、LPOP 與 RPOP，順便處理空容器該不該留在記憶體裡這件事。

為什麼選擇雙向鏈結串列（Doubly Linked List）？

Redis 的 List 具備以下效能特點：

• 在 頭部（左側） 或 尾部（右側） 插入與彈出元素的時間複雜度皆為 $O(1)$。
• 獲取靠近頭部或尾部的元素效能高，但隨機存取中間元素的複雜度為 $O(N)$。

要做到頭尾操作接近 $O(1)$，Go 標準庫的 container/list（雙向鏈結串列）剛好可以用。它已經把指標操作包好，先拿來當第一版底層結構很省事。

核心設計與實作

我在 code/db/list.go 中實作了所有的 List API。

1. 延遲初始化與型別檢查

當使用者發送 LPUSH 或 RPUSH 時，如果 Key 不存在，需要自動初始化一個新的 List 實例；如果 Key 已存在但不是 List 類型，則必須回傳 ErrWrongType 錯誤：

func (db *DB) getOrInitList(key string) (*list.List, error) {
	e, exists := db.getEntryWithoutLock(key)
	if !exists {
		l := list.New()
		db.data[key] = &entry{
			dataType: TypeList,
			val:      l,
		}
		return l, nil
	}

	if e.dataType != TypeList {
		return nil, ErrWrongType // 拋出類型不相符錯誤
	}

	return e.val.(*list.List), nil
}

2. 左推（LPUSH）與右推（RPUSH）

這兩個操作會將一或多個值依序推入 List 的頭部或尾部，並回傳操作完成後 List 的長度：

func (db *DB) LPush(key string, values ...[]byte) (int, error) {
	db.mu.Lock()
	defer db.mu.Unlock()

	l, err := db.getOrInitList(key)
	if err != nil {
		return 0, err
	}

	for _, val := range values {
		l.PushFront(val) // 插入至頭部
	}
	return l.Len(), nil
}

3. 左彈（LPOP）與右彈（RPOP）

彈出操作除了將元素從頭部或尾部取出外，還需要將其從雙向鏈結串列中移除。

一個很重要的 Redis 設計哲學：如果彈出後 List 的長度變為 0，必須將該 Key 從資料庫的 map 中徹底刪除。 這可以防止空容器殘留佔用記憶體空間。

func (db *DB) LPop(key string) ([]byte, bool, error) {
	db.mu.Lock()
	defer db.mu.Unlock()

	e, exists := db.getEntryWithoutLock(key)
	if !exists {
		return nil, false, nil // 鍵不存在
	}

	if e.dataType != TypeList {
		return nil, false, ErrWrongType
	}

	l := e.val.(*list.List)
	if l.Len() == 0 {
		return nil, false, nil
	}

	elem := l.Front()
	l.Remove(elem) // 從鏈結中移除

	// 如果為空，清除該鍵
	if l.Len() == 0 {
		delete(db.data, key)
	}

	return elem.Value.([]byte), true, nil
}

4. 區間查詢：LRANGE

LRANGE 支援從 List 中獲取指定範圍的元素，並支援負數索引（如 -1 代表最後一個元素，-2 代表倒數第二個，依此類推）。在實作時，需要先將負數索引轉換為正數，並進行嚴格的邊界修正：

func (db *DB) LRange(key string, start, stop int) ([][]byte, error) {
	db.mu.Lock()
	defer db.mu.Unlock()

	// ... 類型與存在性檢查 ...
	
	length := l.Len()
	
	// 負數索引轉換
	if start < 0 { start = length + start }
	if stop < 0  { stop = length + stop }

	// 邊界修正
	if start < 0 { start = 0 }
	if stop >= length { stop = length - 1 }

	if start > stop || start >= length {
		return [][]byte{}, nil
	}

	res := make([][]byte, 0, stop-start+1)
	curr := l.Front()
	
	// 1. 移動到 start 節點
	for i := 0; i < start && curr != nil; i++ {
		curr = curr.Next()
	}
	// 2. 收集至 stop 節點
	for i := start; i <= stop && curr != nil; i++ {
		res = append(res, curr.Value.([]byte))
		curr = curr.Next()
	}
	return res, nil
}

處理 LRange 負數索引的時候，為了算那些 index 和 length 到底怎麼轉換，我在白板上畫了好久的圖才沒寫錯邊界。

跑起來看看

List 寫起來挺有意思的，來試試看它的表現吧：

$ go run ./code/main.go

用 printf 送 List 相關指令：

# RPUSH 從右邊推進元素
$ printf "*3\r\n\$5\r\nRPUSH\r\n\$6\r\nmylist\r\n\$5\r\nitem1\r\n" | nc localhost 6379
# 預期回覆：:1

$ printf "*3\r\n\$5\r\nRPUSH\r\n\$6\r\nmylist\r\n\$5\r\nitem2\r\n" | nc localhost 6379
# 預期回覆：:2

# LPOP 從左邊彈出元素
$ printf "*2\r\n\$4\r\nLPOP\r\n\$6\r\nmylist\r\n" | nc localhost 6379
# 預期回覆：$5\r\nitem1

# 用 LRANGE 看剩下的元素 (0 到 -1 代表全部)
$ printf "*4\r\n\$6\r\nLRANGE\r\n\$6\r\nmylist\r\n\$1\r\n0\r\n\$2\r\n-1\r\n" | nc localhost 6379
# 預期回覆：*1\r\n$5\r\nitem2\r\n

看著資料從左進右出（或右進左出），開始比較有在做資料結構的感覺了。

總結

今天用 container/list 把 List 的雙端操作和範圍查詢做出來，也補了空 List 要清掉 key 的細節。

明天換寫 Hash，剛好可以把 Go 的 map 派上用場，明天見！