Lua - Inserting an element to a List

A linked list is a linear data structure which can store a collection of "nodes" connected together via links i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are linked using pointers to the different memory locations. A node consists of the data value and a pointer to the address of the next node within the linked list.

In Lua, each node can be representated by a table and link will be table field containing reference to the other table. We've seen how to create and traverse a list in Lua - Lists chapter. In this chapter we'll cover a more complex example to push an element at the end of the list and then iterate method to traverse the list.

We'll build the list and then add method to insert an element to the list and iterate method to traverse through elements of the list.

Step 1: Create List

Create a List with a push method to add an element to the end of the list.

-- List Implementation
list = {}
list.__index = list

-- push an element to the end of the list
function list:push(t)
   -- move till last node    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- set the node as first node
      self.first = t
      self.last = t
   end
   -- increment the length of the list
   self.length = self.length + 1
end

Step 2: Using setmetatable

modify list behavior when list is called to push elements.

setmetatable(list, { __call = function(_, ...)
   local t = setmetatable({ length = 0 }, list)
      for _, v in ipairs{...} 
         do t:push(v) 
      end
      return t
   end })

Step 3: Create iterator over list

Create an iterator to navigate through elements of the list.

-- iterate through the list
local function iterate(self, current)
   if not current then
      current = self.first
   elseif current then
      current = current._next
   end
  
   return current
end

function list:iterate()
   return iterate, self, nil
end

Step 4: Test insertion operations on List

In list, we can insert objects,

-- define data tables
local mon = { "Mon" }
local tue = { "Tue" }

-- create a new list with two values
local l = list(mon, tue)

-- create more data
local wed = { "Wed" }
local fri = { "Fri" }

-- add a table to the list 
l:push(wed)
-- add a table to the list
l:push({ "Thu" })
-- add a table to the list
l:push(fri)

-- iterate throgh entries
for v in l:iterate() do 
   print(v[1]) 
end

Complete Example - Insertion of Elements into a List

Following is the complete example of inserting and traversing elements of a list.

main.lua

-- List Implementation
list = {}
list.__index = list

setmetatable(list, { __call = function(_, ...)
   local t = setmetatable({ length = 0 }, list)
      for _, v in ipairs{...} 
         do t:push(v) 
      end
      return t
   end })

-- push an element to the end of the list
function list:push(t)
   -- move till last node    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- set the node as first node
      self.first = t
      self.last = t
   end
   -- increment the length of the list
   self.length = self.length + 1
end

-- iterate through the list
local function iterate(self, current)
   if not current then
      current = self.first
   elseif current then
      current = current._next
   end
  
   return current
end

function list:iterate()
   return iterate, self, nil
end

-- define data tables
local mon = { "Mon" }
local tue = { "Tue" }

-- create a new list with two values
local l = list(mon, tue)

-- create more data
local wed = { "Wed" }
local fri = { "Fri" }

-- add a table to the list 
l:push(wed)
-- add a table to the list
l:push({ "Thu" })
-- add a table to the list
l:push(fri)

-- iterate throgh entries
for v in l:iterate() do 
   print(v[1]) 
end

Output

When we run the above code, we will get the following output−

Mon
Tue
Wed
Thu
Fri