List
A common list is very similar to an array (do not be confused with a linked list). A list is a finite type that stores ordered values, where the same value may occur more than once.
Usually list contains basic operations:
append- adds a value to the end of the list;prepend- adds a value to the beginning of the list;insertAt- adds a value in a given position of the list;removeAt- removes a value in a given position of the list;find- searches for the current value;contains- checks that the list contains a given value;size- returns the size of the list.- More if needed.
There is nothing special about the list in Lua language. Type table already has a list concept and implements it out-of-box.
Consider:
-- create a new list
local list = {}
-- append
list[#list + 1] = "C"
-- prepend
table.insert(list, "A")
-- insertAt(2)
table.insert(list, 2, "B")
-- size
#list
-- find
local foundIndex = 0
for i = 1, #list do
if list[i] == "B" then
foundIndex = i
break
end
end
Warning
Things to remember that in Lua indexation begins from 1 not 0. Secondly, table, function, thread and userdata types are passed by reference.
Consider:
local table1 = { a = 1 } – 0x00000001
local table2 = { a = 1 } – 0x00000002
Despite values being the same, technically these are 2 different tables with different memory addresses. When comparing and searching for values in the list take this into account.
List class
There is no point in making a class wrapper for the list because table offers everything out-of-box and works faster than the class wrapper, but to keep the consistency of the data structures section I created this one as well.
This list is not very efficient especially if there will be millions of records. On every deletion of insertion, the average complexity is O(n/2). Probably it is better to look at stack, queue or linked list, which have O(1) complexity.
Class implementation with OOP principles and annotations.
List.lua
---@class List
local List = {}
List.__index = List
---@return List
function List:new()
return setmetatable({}, self)
end
---@param v any
---@return nil
function List:append(v)
self[#self + 1] = v
end
---@param v any
---@retrurn nil
function List:prepend(v)
table.insert(self, 1, v)
end
---@param v any
---@param pos number
---@return nil
function List:insertAt(v, pos)
table.insert(self, pos, v)
end
---@param pos number
---@return nil
function List:insertAt(pos)
table.remove(self, pos)
end
---Returns the index of the found elemen, if not found returns 0.
---@param v any
---@return number
function List:find(v)
for i, value in ipairs(self) do
if v == value then
return i
end
end
return 0
end
---@return number
function List:size()
return #self
end
---@return boolean
function List:contains(v)
return self:find(v) ~= 0
end
---@param sep? string
---@return string
function List:toString(sep)
sep = sep or ","
return table.concat(self, sep)
end
return List
Usage of List class
local l = List:new()
l:append("C")
l:prepend("A")
l:insertAt("B", 2)
print(l:toString(), l:size(), l:find("B")) -- "A,B,C" 3 2
print(l:contains("A"), l:contains("D")) -- true false