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
References¶
Feedback
For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.