Xmake

English

简体中文

English

简体中文

Appearance

list ​

The list module provides a doubly linked list data structure that supports efficient insertion and deletion operations at both ends. This is an extension module of xmake.

TIP

To use this module, you need to import it first: import("core.base.list")

list.new ​

  • Create an empty linked list
lua
import("core.base.list")

local l = list.new()

Creates a new empty doubly linked list object.

lua
local l = list.new()
print(l:size())   -- Output: 0
print(l:empty())  -- Output: true

list:push ​

  • Add element to the end of the list
lua
list:push(item)

Adds an element to the end of the list. Equivalent to list:insert_last(item).

This is the most common way to add elements:

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

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

TIP

The list stores references to elements, not copies. You can store values of any type (numbers, strings, tables, etc.).

list:pop ​

  • Remove element from the end of the list
lua
list:pop()

Removes an element from the end of the list. Equivalent to 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)  -- Output: 2

list:unshift ​

  • Add element to the beginning of the list
lua
list:unshift(item)

Adds an element to the beginning of the list. Equivalent to 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)  -- Output: 1, 2, 3
end

list:shift ​

  • Remove element from the beginning of the list
lua
list:shift()

Removes an element from the beginning of the list. Equivalent to 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)  -- Output: 2

list:insert ​

  • Insert an element
lua
list:insert(item, after)

Inserts a new element after the specified element. If the after parameter is not provided, inserts at the end of the list.

Parameters:

  • item: The element to insert
  • after: Optional, insert after this element; if nil, inserts at the end
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)  -- Insert {value = 4} after v3

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

list:insert_first ​

  • Insert element at the beginning
lua
list:insert_first(item)

Inserts an element at the beginning of the list.

Used for scenarios requiring insertion at the head:

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

print(l:first().value)  -- Output: 1

list:insert_last ​

  • Insert element at the end
lua
list:insert_last(item)

Inserts an element at the end of the list.

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

print(l:last().value)  -- Output: 3

list:remove ​

  • Remove specified element
lua
local removed_item = list:remove(item)

Removes the specified element from the list and returns the removed element.

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())  -- Output: 4

Safe way to remove elements during iteration:

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

-- Iterate and remove all elements
local item = l:first()
while item ~= nil do
    local next = l:next(item)
    l:remove(item)
    item = next
end
print(l:empty())  -- Output: true

list:remove_first ​

  • Remove element from the beginning
lua
local removed_item = list:remove_first()

Removes an element from the beginning of the list and returns the removed element. Returns nil if the list is empty.

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

l:remove_first()
print(l:first().value)  -- Output: 2

list:remove_last ​

  • Remove element from the end
lua
local removed_item = list:remove_last()

Removes an element from the end of the list and returns the removed element. Returns nil if the list is empty.

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

l:remove_last()
print(l:last().value)  -- Output: 2

list:first ​

  • Get the first element
lua
local item = list:first()

Returns the first element of the list without removing it. Returns nil if the list is empty.

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

print(l:first().value)  -- Output: 1

list:last ​

  • Get the last element
lua
local item = list:last()

Returns the last element of the list without removing it. Returns nil if the list is empty.

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

print(l:last().value)  -- Output: 3

list:next ​

  • Get the next element
lua
local next_item = list:next(current)

Gets the next element after the specified element. If current is nil, returns the first element.

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)  -- Output: 2

Used for manual iteration:

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

local item = l:next(nil)  -- Get the first element
while item do
    print(item.value)
    item = l:next(item)
end

list:prev ​

  • Get the previous element
lua
local prev_item = list:prev(current)

Gets the previous element before the specified element. If current is nil, returns the last element.

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)  -- Output: 2

Used for reverse iteration:

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

local item = l:prev(nil)  -- Get the last element
while item do
    print(item.value)  -- Output: 3, 2, 1
    item = l:prev(item)
end

list:size ​

  • Get list size
lua
local count = list:size()

Returns the number of elements in the list.

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

print(l:size())  -- Output: 3

list:empty ​

  • Check if list is empty
lua
local is_empty = list:empty()

Returns true if the list is empty (contains no elements).

lua
local l = list.new()
print(l:empty())  -- Output: true

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

list:clear ​

  • Clear the list
lua
list:clear()

Removes all elements from the list, resetting it to an empty list.

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

l:clear()
print(l:empty())  -- Output: true
print(l:size())   -- Output: 0

list:items ​

  • Iterate forward through the list
lua
for item in list:items() do
    -- Process item
end

Returns an iterator function for traversing all elements in the list from head to tail.

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)  -- Output: 1, 2, 3
end

Verify order:

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 ​

  • Iterate backward through the list
lua
for item in list:ritems() do
    -- Process item
end

Returns an iterator function for traversing all elements in the list from tail to head.

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)  -- Output: 3, 2, 1
end

Reverse iteration with deletion:

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())  -- Output: true

TIP

The list module implements a doubly linked list, providing O(1) time complexity for insertion and deletion operations at both ends. Suitable for scenarios requiring frequent operations at both ends, such as queues, stacks, LRU caches, etc.

WARNING

  • The list stores references to elements; modifying elements will affect the content in the list
  • When deleting elements during iteration, be careful to first obtain the reference to the next/previous element
  • The time complexity of insertion or deletion operations is O(1) (if you have the element reference)