Lua - 从 List 中移除元素

从链表中移除一个元素需要更新要移除元素的 prev node 和 next node 的引用。

最后一个元素的情况

我们可以将 prev node 的 next 设置为 nil，并将 last 设置为 prev node，如以下伪代码所示——

-- 获取最后一个节点
local removedElement = self.last
  
-- 如果存在 prev
-- 则将 prev 节点设置为最后一个节点  
if removedElement._prev then
  removedElement._prev._next = nil
  self.last = removedElement._prev
  removedElement._prev = nil
else
  -- 最后一个节点是链表中唯一的节点
  self.first = nil
  self.last = nil
end

其他元素的情况，t

如果 t 同时具有 next 和 prev 节点，则更新 t.next 和 t.prev 的 prev 和 next 引用。如果 t 是第一个节点，则将 first 设置为 t.next。

查看以下伪代码——

if t._next then
   if t._prev then
      t._next._prev = t._prev
      t._prev._next = t._next
   else
      -- 这是第一个节点
      t._next._prev = nil
      self._first = t._next
   end
elseif t._prev then  -- 如果节点只有 prev 节点
   -- 这是最后一个节点
   t._prev._next = nil
   self._last = t._prev
else
   -- 这是唯一的节点
   self._first = nil
   self._last = nil
end

现在我们将逐步构建链表，添加从链表末尾移除元素的方法以及从链表中移除特定元素的方法，如下所示：

步骤 1: 创建 List

创建一个带有 push 方法的 List，用于向链表末尾添加元素。

-- List 实现
list = {}
list.__index = list

-- 将元素推入链表末尾
function list:push(t)
   -- 移动到最后一个节点    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- 将节点设置为第一个节点
      self.first = t
      self.last = t
   end
   -- 递增链表长度
   self.length = self.length + 1
end

步骤 2: 使用 setmetatable

修改 list 的行为，当调用 list 来推送元素时。

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

步骤 3: 创建链表迭代器

创建一个迭代器来遍历链表中的元素。

-- 遍历链表
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

步骤 4：创建 removeLast() 和 remove() 方法

创建 removeLast() 以从列表末尾移除元素，以及 remove(t) 以移除指定的元素。

-- 从列表中移除最后一个元素
function list:removeLast()
   -- 如果 last 为 nil 则返回
   if not self.last then
      return 
   end
   local removedElement = self.last
  
   -- 如果存在 prev
   -- 则将 prev 节点设置为最后一个节点  
   if removedElement._prev then
      removedElement._prev._next = nil
      self.last = removedElement._prev
      removedElement._prev = nil
   else
      -- 最后一个节点是列表中唯一的节点
      self.first = nil
      self.last = nil
   end
  
   -- 减少长度
   self.length = self.length - 1
  
   return removedElement
end

-- 移除指定的元素 t
function list:remove(t)
   -- 如果要删除的节点有下一个节点
   -- 更新前一个和后一个节点的指针
   if t._next then
      if t._prev then
         t._next._prev = t._prev
         t._prev._next = t._next
      else
         -- 这是第一个节点
         t._next._prev = nil
         self._first = t._next
       end
   elseif t._prev then  -- 如果节点只有前一个节点
      -- 这是最后一个节点
      t._prev._next = nil
      self._last = t._prev
   else
      -- 这是唯一的节点
      self._first = nil
      self._last = nil
   end

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

步骤 5：在 List 上测试移除操作

首先用几个值初始化一个列表，然后移除几个元素。

-- 创建一个带有值的新列表
local l = list({ "Mon" }, { "Tue" }, wed, { "Thu" }, { "Fri" })

print("原始列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

l:removeLast()
print("更新后的列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

l:remove (wed)
print("更新后的列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

完整示例 - 从列表中移除元素

以下是插入和遍历列表元素的完整示例。

main.lua

-- 列表实现
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 })

-- 将元素推入列表末尾
function list:push(t)
   -- 移动到最后一个节点    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- 将节点设置为第一个节点
      self.first = t
      self.last = t
   end
   -- 增加列表长度
   self.length = self.length + 1
end

-- 遍历列表
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

-- 从列表中移除最后一个元素
function list:removeLast()
   -- 如果最后一个节点为 nil 则返回
   if not self.last then
      return 
   end
   local removedElement = self.last
  
   -- 如果存在前一个节点
   -- 则将前一个节点设置为最后一个节点  
   if removedElement._prev then
      removedElement._prev._next = nil
      self.last = removedElement._prev
      removedElement._prev = nil
   else
      -- 最后一个节点是列表中唯一的节点
      self.first = nil
      self.last = nil
   end
  
   -- 减少长度
   self.length = self.length - 1
  
   return removedElement
end

-- 移除特定元素 t
function list:remove(t)
   -- 如果要删除的节点有下一个节点
   -- 更新前一个和下一个节点的指针
   if t._next then
      if t._prev then
         t._next._prev = t._prev
         t._prev._next = t._next
      else
         -- 这是第一个节点
         t._next._prev = nil
         self.first = t._next
      end
   elseif t._prev then  -- 如果节点只有前一个节点
      -- 这是最后一个节点
      t._prev._next = nil
      self.last = t._prev
   else
      -- 这是唯一的节点
      self.first = nil
      self.last = nil
   end

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

local wed = { "Wed" }
-- 使用值创建新列表
local l = list({ "Mon" }, { "Tue" }, wed, { "Thu" }, { "Fri" })

print("原始列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

l:removeLast()
print("移除最后一个元素后的更新列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

l:remove(wed)
print("同时移除 Wed 后的更新列表")
-- 遍历条目
for v in l:iterate() do 
   print(v[1]) 
end

输出

运行上述代码时，将得到以下输出−

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