Lua - Reversing a List

In order to reverse a list, we can create a iterator which can return the prev element of the list. Then we can start traversing from the last element in order to iterate list in reverse way and store the result in a different list. See the following code of the reverse iterator function on the list.

-- iterate through the list
local function reverseIterate(self, current)
   -- if current is nil
   -- set the current as last node
   if not current then
      current = self.last
   -- if current is present
   -- set current as current prev   
   elseif current then
      current = current._prev
   end
   -- return current  
   return current
end

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

We can use list:reverseIterator() function to reverse iterate the list which will return the prev 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 in reverse order.

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 reverseIterate(self, current)
   -- if current is nil
   -- set the current as last node
   if not current then
      current = self.last
   -- if current is present
   -- set current as current prev   
   elseif current then
      current = current._prev
   end
   -- return current  
   return current
end

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

Step 4: Test Iterations on List

In list, we can insert objects, and test the iteration

l = list({A}, {"B"}, {"C"},"D"},{"E"}, {"F"} )
-- iterate throgh entries
for v in l:reverseIterator() do 
   print(v[1]) 
end

Complete Example - Reversing elements of a List

Following is the complete example of inserting and reversing elements of a list and storing them in a table.

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 reverseIterate(self, current)
   -- if current is nil
   -- set the current as last node
   if not current then
      current = self.last
   -- if current is present
   -- set current as current prev
   elseif current then
      current = current._prev
   end
   -- return current
   return current
end

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

-- create a new list with values
local l = list({ "Mon" }, { "Tue" }, { "Wed" }, { "Thu" }, { "Fri" })

local reversedList = {}

local index = 1

-- iterate throgh entries in reverse order
for v in l:reverseIterator() do
   reversedList[index] = v[1]
   index = index + 1
end

-- print the reversed entries
for _,v in ipairs(reversedList) do
   print(v)
end 

Output

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

Fri
Thu
Wed
Tue
Mon