Lua - Iterating over Lists

In order to iterate a list, it is good practice to build an iterator which can return the next element of the list. See the following code of the iterator function on the list.

-- iterate through the list
local function iterate(self, current)
   -- if current is nil
   -- set the current as first node
   if not current then
      current = self.first
   -- if current is present
   -- set current as current next   
   elseif current then
      current = current._next
   end
   -- return current  
   return current
end

-- return the iterator
function list:iterate()
   return iterate, self, nil
end

We can use list:iterate() function to iterate the list which will return the next element when invoked in a for loop.

We'll build the list and then add method to insert an element. Finally, using iterate function in a for loop, we'll iterate 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 current is nil
   -- set the current as first node
   if not current then
      current = self.first
   -- if current is present
   -- set current as current next   
   elseif current then
      current = current._next
   end
   -- return current  
   return current
end

-- return the iterator
function list:iterate()
   return iterate, self, nil
end

Step 4: Test Iterations 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)

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

-- 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 - Iterating elements of 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)

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

-- 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)

print("List with added entries")
-- 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−

Original List
Mon
Tue
List with added entries
Mon
Tue
Wed
Thu
Fri