Lua - Removing an element from a List

Previous
Quiz
Next

Removing an element from a linked list requires updates in the references of prev node and next node of the element to be removed.

Case of Last element

We can set the next of prev node as nil, set the last as prev node as shown in psuedo code below−

-- get the last node
local removedElement = self.last
  
-- if prev is present
-- then set prev node as last node  
if removedElement._prev then
  removedElement._prev._next = nil
  self.last = removedElement._prev
  removedElement._prev = nil
else
  -- last node was only node in the list
  self.first = nil
  self.last = nil
end

Case of Other element, t

If t has both next and prev nodes, then update prev and next references of t.next and t.prev. If t is the first node, set first as t.next.

See the pseudo code below−

if t._next then
   if t._prev then
      t._next._prev = t._prev
      t._prev._next = t._next
   else
      -- this was the first node
      t._next._prev = nil
      self._first = t._next
   end
elseif t._prev then  -- if node has prev node only
   -- this was the last node
   t._prev._next = nil
   self._last = t._prev
else
   -- this was the only node
   self._first = nil
   self._last = nil
end

Now We'll build the list, add method to remove an element from the end of the list and to remove a specific element from the list step by step as shown below:

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: Create removeLast() and remove() methods

Create removeLast() to remove element from the end of the list and remove(t) to remove a given element.

-- remove last element from the list
function list:removeLast()
   -- if last is nil then return
   if not self.last then
      return 
   end
   local removedElement = self.last
  
   -- if prev is present
   -- then set prev node as last node  
   if removedElement._prev then
      removedElement._prev._next = nil
      self.last = removedElement._prev
      removedElement._prev = nil
   else
      -- last node was only node in the list
      self.first = nil
      self.last = nil
   end
  
   -- decrement the length
   self.length = self.length - 1
  
   return removedElement
end

-- remove a specific element, t
function list:remove(t)
   -- if node to delete has next node
   -- update the pointers of prev and next nodes
   if t._next then
      if t._prev then
         t._next._prev = t._prev
         t._prev._next = t._next
      else
         -- this was the first node
         t._next._prev = nil
         self._first = t._next
       end
   elseif t._prev then  -- if node has prev node only
      -- this was the last node
      t._prev._next = nil
      self._last = t._prev
   else
      -- this was the only node
      self._first = nil
      self._last = nil
   end

   t._next = nil
   t._prev = nil
   self.length = self.length - 1
end

Step 5: Test remove operations on List

First initialize a list with few values and then remove few elements. 

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

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

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

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

Complete Example - Removal of Elements from 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

-- remove last element from the list
function list:removeLast()
   -- if last is nil then return
   if not self.last then
      return 
   end
   local removedElement = self.last
  
   -- if prev is present
   -- then set prev node as last node  
   if removedElement._prev then
      removedElement._prev._next = nil
      self.last = removedElement._prev
      removedElement._prev = nil
   else
      -- last node was only node in the list
      self.first = nil
      self.last = nil
   end
  
   -- decrement the length
   self.length = self.length - 1
  
   return removedElement
end

-- remove a specific element, t
function list:remove(t)
   -- if node to delete has next node
   -- update the pointers of prev and next nodes
   if t._next then
      if t._prev then
         t._next._prev = t._prev
         t._prev._next = t._next
      else
         -- this was the first node
         t._next._prev = nil
         self._first = t._next
      end
   elseif t._prev then  -- if node has prev node only
      -- this was the last node
      t._prev._next = nil
      self._last = t._prev
   else
      -- this was the only node
      self._first = nil
      self._last = nil
   end

   t._next = nil
   t._prev = nil
   self.length = self.length - 1
end

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

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

l:removeLast()
print("Updated List after removing last element")
-- iterate throgh entries
for v in l:iterate() do 
   print(v[1]) 
end

l:remove (wed)
print("Updated List after removing Wed as well")
-- 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
Wed
Thu
Fri
Updated List after removing last element
Mon
Tue
Wed
Thu
Updated List after removing Wed as well
Mon
Tue
Thu
Print Page
Previous
Next
Advertisements