[Lua] Data types and structures

Introduction

Every programmer has used a data structure at least once. The goal of this topic is to provide easy access to the most common data types and structures written in Lua.

What is a data structure?

A data structure is a way to store and organize information so that it's easier to use and work with in a computer program.

Why data structures are so important?

Data structures are important because they help you keep information organized, so you can find and use it faster. Imagine you have a big box of legos, but they're all mixed up. If you need a red piece, it’s going to take a while to find it. But if you organize the Legos by color or size, you can find the piece you need much quicker.

What is a data type?

A data type is like a way to tell the computer what kind of information you're working with. It's like sorting your toys into different categories, so the computer knows what to expect and how to handle it.

An enum (enumeration) is like giving a list of things special names to make them easier to use.

Code:

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

local function enum(def)
    local enumTable = {}
    local cv = 0
    for key, value in pairs(def) do
        if type(key) == "string" then
            enumTable[key] = value or cv
            cv = enumTable[key] + 1
        elseif type(key) == "number" then
            enumTable[value] = cv
            cv = cv + 1
        end
    end

    return enumTable
end

Usage 1:

Code Lua

1
2
3
4
5
6
7
8
9
10
11

roomType = enum({
    NORMAL = 0,
    VANILLA = 1,
    SURVIVOR = 2,
    RACING = 3,
    BOOTCAMP = 4
})

print(roomType.NORMAL)  -- 0
print(roomType.VANILLA)   -- 1
-- and so on

Usage 2:

Code Lua

1
2
3
4
5
6
7
8
9

roomType2 = enum({
    "NORMAL", 
    "VANILLA", 
    "SURVIVOR", 
    "RACING", 
    "BOOTCAMP"
})

print(roomType2["NORMAL"])  -- 0

If key is does not exist in the enum it's nil.

Code Lua

print(roomType.UNKNOWN)   -- nil

A pair is a container that holds two values, which can be of different types.

Code Lua

1
2
3
4
5
6
7
8
9
10
11

local function pair(x, y)
   local p = { 
		first = x, 
		second = y 
	 }
    return setmetatable(p, {
        __index = function(_, key)
            error("Invalid key access: " .. tostring(key))
        end
    })
end

Usage:

Code Lua

1
2
3
4

p = pair(100, "luanoob")

print(p.first)  -- 100
print(p.second) -- luanoob

A tuple can store multiple values of different types.

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

local function tuple(...)
    local elements = {...}
    return setmetatable({}, {
        __index = function(_, key)
            if type(key) == "number" and key >= 1 and key <= #elements then
                return elements[key]
            else
                error("Invalid index: " .. tostring(key))
            end
        end,
        __newindex = function()
            error("Not allowed")
        end,
        __len = function()
            return #elements
        end
    })
end

Usage:

Code Lua

1
2
3
4
5
6
7
8

t = tuple(69, "touhouisbest", true, 3.14)

print(t[1])  -- 69
print(t[2])  -- touhouisbest
print(t[3])  -- true
print(t[4])  -- 3.14

print(#t)    -- size of the tuple

A Linked List is a data structure used to store a collection of elements in a sequence, but it does not provide O(1) access to elements.

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

do
	LinkedList = {}
	LinkedList.__index = LinkedList

	function LinkedList:new()
		local self = setmetatable({}, LinkedList)
		self.head = nil
		return self
	end

	function LinkedList:newNode(value)
		return {data = value, next = nil}
	end

	function LinkedList:getList()
		local temp = self.head
		local result = {}
		while temp do
			table.insert(result, tostring(temp.data))
			temp = temp.next
		end
		return result
	end

	function LinkedList:insert(value)
		local newNode = self:newNode(value)
		if self.head == nil then
			self.head = newNode
		else
			local temp = self.head
			while temp.next do
				temp = temp.next
			end
			temp.next = newNode
		end
	end

	function LinkedList:insertBegin(value)
		local newNode = self:newNode(value)
		newNode.next = self.head
		self.head = newNode
	end

	function LinkedList:insertEnd(value)
		local newNode = self:newNode(value)
		if self.head == nil then
			self.head = newNode
		else
			local temp = self.head
			while temp.next do
				temp = temp.next
			end
			temp.next = newNode
		end
	end

	function LinkedList:delete(value)
		if self.head == nil then 
			return 
		end
		
		if self.head.data == value then
			self.head = self.head.next
			return
		end
		
		local temp = self.head
		while temp.next and temp.next.data ~= value do
			temp = temp.next
		end
		
		if temp.next then
			temp.next = temp.next.next
		end
	end

	function LinkedList:deleteBegin()
		if self.head ~= nil then
			self.head = self.head.next
		end
	end

	function LinkedList:deleteEnd()
		if self.head == nil then return end
		
		if self.head.next == nil then
			self.head = nil
			return
		end
		
		local temp = self.head
		while temp.next.next do
			temp = temp.next
		end
		temp.next = nil
	end

	function LinkedList:search(value)
		local temp = self.head
		while temp do
			if temp.data == value then
				return true
			end
			temp = temp.next
		end
		return false
	end
	LinkedList.find = LinkedList.search -- Alias of search
end

Function	Complexity
insert	~O(n)
insertBegin	O(1)
insertEnd	O(n)
delete	~O(n)
deleteBegin	O(1)
deleteEnd	O(n)
search	~O(n)
find	~O(n)
getList	O(1)

Usage:

Code Lua

1
2
3
4
5
6
7
8
9
10
11

list = LinkedList:new()
list:insert(10)
list:insert(20)
list:insert(30)
print(table.concat(list:getList(), " -> ")) -- 10 -> 20 -> 30

list:delete(20)
print(table.concat(list:getList(), " -> ")) -- 10 -> 30

print(list:search(30)) -- true
print(list:search(40)) -- false

A stack is a linear data structure that is LIFO. This means that the last element added to the stack is the first one to be removed.

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

do
	Stack = {}
	Stack.__index = Stack

	function Stack:new()
		local self = setmetatable({}, Stack)
		self.items = {}
		return self
	end

	function Stack:push(value)
		table.insert(self.items, value)
	end

	function Stack:pop()
		if #self.items == 0 then
			return nil
		end
		return table.remove(self.items)
	end

	function Stack:top()
		return self.items[#self.items]
	end

	function Stack:isEmpty()
		return #self.items == 0
	end

	function Stack:size()
		return #self.items
	end
end

Function	Complexity
push	O(1)
pop	O(1)
top	O(1)
isEmpty	O(1)
size	O(1)

Usage:

Code Lua

1
2
3
4
5
6
7
8

stack = Stack:new()
stack:push(10)
stack:push(20)
stack:push(30)

print(stack:top()) -- 30
print(stack:size()) -- 3
print(stack:isEmpty()) -- false

A queue is a linear data structure that is FIFO. This means that the first element added to the queue is the first one to be removed.

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

do
	Queue = {}
	Queue.__index = Queue

	function Queue.new()
		local self = setmetatable({}, Queue)
		self.items = {}
		return self
	end

	function Queue:push(item)
		table.insert(self.items, item)
	end

	function Queue:pop()
		if self:isEmpty() then
			return nil
		else
			return table.remove(self.items, 1)
		end
	end

	function Queue:isEmpty()
		return #self.items == 0
	end

	function Queue:size()
		return #self.items
	end
	
	function Queue:front()
		if self:isEmpty() then
			return nil
		else
			return self.items[1]
		end
	end

	function Queue:back()
		if self:isEmpty() then
			return nil
		else
			return self.items[#self.items]
		end
	end
end

Function	Complexity
push	O(1)
pop	O(n)
back	O(1)
front	O(1)
isEmpty	O(1)
size	O(1)

Usage:

Code Lua

1
2
3
4
5
6
7
8
9

-- Example Usage
queue = Queue:new()
queue:push(10)
queue:push(20)
queue:push(30)

print(queue:front()) -- 10
print(queue:back()) -- 30
print(queue:size()) -- 3

A set is a collection of elements, where each element is unique (no duplications).

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

do
	Set = {}
	Set.__index = Set

	function Set.new()
		local self = setmetatable({}, Set)
		self.elements = {}
		return self
	end

	function Set:add(element)
		if not self:contains(element) then
			self.elements[element] = true
		end
	end

	function Set:remove(element)
		self.elements[element] = nil
	end

	function Set:contains(element)
		return self.elements[element] ~= nil
	end

	function Set:size()
		local count = 0
		for _ in pairs(self.elements) do
			count = count + 1
		end
		return count
	end

	function Set:isEmpty()
		return next(self.elements) == nil
	end

	function Set:toList()
		local list = {}
		for element in pairs(self.elements) do
			table.insert(list, element)
		end
		return list
	end
end

Function	Complexity
add	O(1)
remove	O(1)
size	O(1)
contains	O(1)
isEmpty	O(1)
toList	O(n)

Usage:

Code Lua

1
2
3
4
5
6
7
8
9
10

s = Set.new()
print(s:isEmpty())  -- true

s:add(1)
s:add(2)
print(s:isEmpty())  -- false

s:remove(1)
s:remove(2)
print(s:isEmpty())  -- true

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

do
	Deque = {}
	Deque.__index = Deque

	function Deque.new()
		local self = setmetatable({}, Deque)
		self.items = {}
		return self
	end

	function Deque:pushFront(item)
		table.insert(self.items, 1, item)
	end

	function Deque:pushBack(item)
		table.insert(self.items, item)
	end

	function Deque:popFront()
		if self:isEmpty() then
			return nil
		else
			return table.remove(self.items, 1)
		end
	end

	function Deque:popBack()
		if self:isEmpty() then
			return nil
		else
			return table.remove(self.items)
		end
	end

	function Deque:isEmpty()
		return #self.items == 0
	end

	function Deque:size()
		return #self.items
	end

	function Deque:front()
		if self:isEmpty() then
			return nil
		else
			return self.items[1]
		end
	end

	function Deque:back()
		if self:isEmpty() then
			return nil
		else
			return self.items[#self.items]
		end
	end
end

Function	Complexity
pushFront	O(n)
pushBack	O(1)
popFront	O(n)
popBack	O(1)
isEmpty	O(1)
size	O(1)
front	O(1)
back	O(1)

Usage:

Code Lua

1
2
3
4
5
6
7
8
9
10
11

dq = Deque.new()

dq:pushBack(1)
dq:pushBack(2)
dq:pushFront(0)

print(dq:size())  -- 3
print(dq:popFront())  -- 0
print(dq:popBack())   -- 2
print(dq:size())  -- 1
print(dq:isEmpty()) -- false

A hash tableis a data structure that stores key-value pairs and allows for efficient data retrieval using keys. It provides constant-time average complexity for insert, delete and lookup.

Code Lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

do
	HashTable = {}
	HashTable.__index = HashTable

	function HashTable.new()
		local self = setmetatable({}, HashTable)
		self.table = {}
		self.size = 0
		return self
	end

	function HashTable:hash(key)
		local hashValue = 0
		for i = 1, #key do
			hashValue = (hashValue + string.byte(key, i)) % 1024  -- Using 1024 buckets
		end
		return hashValue
	end

	function HashTable:insert(key, value)
		local index = self:hash(key)
		if not self.table[index] then
			self.table[index] = {}
		end
		self.table[index][key] = value
		self.size = self.size + 1
	end

	function HashTable:get(key)
		local index = self:hash(key)
		if self.table[index] then
			return self.table[index][key]
		end
		return nil
	end

	function HashTable:remove(key)
		local index = self:hash(key)
		if self.table[index] and self.table[index][key] then
			self.table[index][key] = nil
			self.size = self.size - 1
		end
	end

	function HashTable:size()
		return self.size
	end
end

Dernière modification le

English	Français
Português do Brasil	Español
Türkçe	Polski
Magyar	Română
العربية	Skandinavisk
Nederlands	Deutsch
Bahasa Indonesia	Русский
中文	Filipino
Lietuvių kalba	日本語
Suomi	עברית
Italiano	Česky
Hrvatski	Slovensky
Български	Latviešu
Estonian

Langue