list

list 模块提供了双向链表数据结构，支持高效的头尾插入删除操作。这是 xmake 的扩展模块。

提示

使用此模块需要先导入：import("core.base.list")

list.new

创建空的链表

lua

import("core.base.list")

local l = list.new()

创建一个新的空双向链表对象。

lua

local l = list.new()
print(l:size())   -- 输出: 0
print(l:empty())  -- 输出: true

list:push

在链表尾部添加元素

lua

list:push(item)

在链表的尾部添加一个元素。等同于 list:insert_last(item)。

这是最常用的添加元素方式：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

print(l:size())        -- 输出: 3
print(l:first().value) -- 输出: 1
print(l:last().value)  -- 输出: 3

提示

链表存储的是对元素的引用，而不是副本。可以存储任意类型的值（数字、字符串、table 等）。

list:pop

从链表尾部移除元素

lua

list:pop()

从链表的尾部移除一个元素。等同于 list:remove_last()。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

l:pop()
print(l:last().value)  -- 输出: 2

list:unshift

在链表头部添加元素

lua

list:unshift(item)

在链表的头部添加一个元素。等同于 list:insert_first(item)。

lua

local l = list.new()
l:push({value = 2})
l:push({value = 3})
l:unshift({value = 1})

for item in l:items() do
    print(item.value)  -- 输出: 1, 2, 3
end

list:shift

从链表头部移除元素

lua

list:shift()

从链表的头部移除一个元素。等同于 list:remove_first()。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

l:shift()
print(l:first().value)  -- 输出: 2

list:insert

插入元素

lua

list:insert(item, after)

在指定元素后面插入新元素。如果不提供 after 参数，则在链表尾部插入。

参数：

item：要插入的元素
after：可选，在此元素后插入，如果为 nil 则在尾部插入

lua

local l = list.new()
local v3 = {value = 3}
l:insert({value = 1})
l:insert({value = 2})
l:insert(v3)
l:insert({value = 5})
l:insert({value = 4}, v3)  -- 在 v3 后插入 {value = 4}

local idx = 1
for item in l:items() do
    print(item.value)  -- 输出: 1, 2, 3, 4, 5
    idx = idx + 1
end

list:insert_first

在链表头部插入元素

lua

list:insert_first(item)

在链表的头部插入一个元素。

用于需要在头部插入的场景：

lua

local l = list.new()
l:push({value = 2})
l:push({value = 3})
l:insert_first({value = 1})

print(l:first().value)  -- 输出: 1

list:insert_last

在链表尾部插入元素

lua

list:insert_last(item)

在链表的尾部插入一个元素。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:insert_last({value = 3})

print(l:last().value)  -- 输出: 3

list:remove

删除指定元素

lua

local removed_item = list:remove(item)

从链表中删除指定的元素，返回被删除的元素。

lua

local l = list.new()
local v3 = {value = 3}
l:push({value = 1})
l:push({value = 2})
l:push(v3)
l:push({value = 4})
l:push({value = 5})

l:remove(v3)
print(l:size())  -- 输出: 4

在遍历时删除元素的安全方式：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

-- 遍历并删除所有元素
local item = l:first()
while item ~= nil do
    local next = l:next(item)
    l:remove(item)
    item = next
end
print(l:empty())  -- 输出: true

list:remove_first

删除链表头部元素

lua

local removed_item = list:remove_first()

从链表头部删除一个元素，返回被删除的元素。如果链表为空，返回 nil。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

l:remove_first()
print(l:first().value)  -- 输出: 2

list:remove_last

删除链表尾部元素

lua

local removed_item = list:remove_last()

从链表尾部删除一个元素，返回被删除的元素。如果链表为空，返回 nil。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

l:remove_last()
print(l:last().value)  -- 输出: 2

list:first

获取链表首元素

lua

local item = list:first()

返回链表的第一个元素，不删除。如果链表为空，返回 nil。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

print(l:first().value)  -- 输出: 1

list:last

获取链表尾元素

lua

local item = list:last()

返回链表的最后一个元素，不删除。如果链表为空，返回 nil。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

print(l:last().value)  -- 输出: 3

list:next

获取下一个元素

lua

local next_item = list:next(current)

获取指定元素的下一个元素。如果 current 为 nil，返回第一个元素。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

local first = l:first()
local second = l:next(first)
print(second.value)  -- 输出: 2

用于手动遍历链表：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

local item = l:next(nil)  -- 获取第一个元素
while item do
    print(item.value)
    item = l:next(item)
end

list:prev

获取上一个元素

lua

local prev_item = list:prev(current)

获取指定元素的上一个元素。如果 current 为 nil，返回最后一个元素。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

local last = l:last()
local second = l:prev(last)
print(second.value)  -- 输出: 2

用于反向遍历：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

local item = l:prev(nil)  -- 获取最后一个元素
while item do
    print(item.value)  -- 输出: 3, 2, 1
    item = l:prev(item)
end

list:size

获取链表大小

lua

local count = list:size()

返回链表中元素的个数。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

print(l:size())  -- 输出: 3

list:empty

判断链表是否为空

lua

local is_empty = list:empty()

返回 true 表示链表为空（不包含任何元素）。

lua

local l = list.new()
print(l:empty())  -- 输出: true

l:push({value = 1})
print(l:empty())  -- 输出: false

list:clear

清空链表

lua

list:clear()

删除链表中的所有元素，重置为空链表。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

l:clear()
print(l:empty())  -- 输出: true
print(l:size())   -- 输出: 0

list:items

正向遍历链表

lua

for item in list:items() do
    -- 处理 item
end

返回一个迭代器函数，用于从头到尾遍历链表中的所有元素。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

for item in l:items() do
    print(item.value)  -- 输出: 1, 2, 3
end

验证顺序：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})
l:push({value = 4})
l:push({value = 5})

local idx = 1
for item in l:items() do
    assert(item.value == idx)
    idx = idx + 1
end

list:ritems

反向遍历链表

lua

for item in list:ritems() do
    -- 处理 item
end

返回一个迭代器函数，用于从尾到头遍历链表中的所有元素。

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})

for item in l:ritems() do
    print(item.value)  -- 输出: 3, 2, 1
end

反向遍历并删除：

lua

local l = list.new()
l:push({value = 1})
l:push({value = 2})
l:push({value = 3})
l:push({value = 4})
l:push({value = 5})

local item = l:last()
while item ~= nil do
    local prev = l:prev(item)
    l:remove(item)
    item = prev
end
print(l:empty())  -- 输出: true

提示

list 模块实现的是双向链表，提供 O(1) 时间复杂度的头尾插入删除操作。适合需要频繁在两端操作的场景，如队列、栈、LRU 缓存等。

注意

链表存储的是对元素的引用，修改元素会影响链表中的内容
遍历时删除元素需要注意先获取下一个/上一个元素的引用
插入或删除操作的时间复杂度为 O(1)（如果已有元素引用）

base

compress

language

project

tool

list

list.new

list:push

list:pop

list:unshift

list:shift

list:insert

list:insert_first

list:insert_last

list:remove

list:remove_first

list:remove_last

list:first

list:last

list:next

list:prev

list:size

list:empty

list:clear

list:items

list:ritems

list ​

list.new ​

list:push ​

list:pop ​

list:unshift ​

list:shift ​

list:insert ​

list:insert_first ​

list:insert_last ​

list:remove ​

list:remove_first ​

list:remove_last ​

list:first ​

list:last ​

list:next ​

list:prev ​

list:size ​

list:empty ​

list:clear ​

list:items ​

list:ritems ​

list

list.new

list:push

list:pop

list:unshift

list:shift

list:insert

list:insert_first

list:insert_last

list:remove

list:remove_first

list:remove_last

list:first

list:last

list:next

list:prev

list:size

list:empty

list:clear

list:items

list:ritems