Lua - 列表长度

List 是一种动态数据结构，为了跟踪列表的大小，我们可以将长度作为列表的状态。我们可以在向列表添加元素时将长度加 1，在移除元素时减 1。

我们将构建列表，然后添加方法来插入元素、移除元素并获取列表的大小。

步骤 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

修改列表被调用时推入元素的行为。

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

步骤 3：创建 remove() 方法

创建 remove(t) 来移除指定的元素。

-- 移除特定元素 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

步骤 4：获取列表长度

创建一个函数来获取列表长度

function list:size()
   return self.length
end

步骤 5：测试列表长度

在列表中插入和移除对象，并检查列表长度

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

print("原始列表大小:", l:size())

-- 移除一个元素
l:remove({"Wed"})
print("移除一个元素后的列表大小:", l:size())

-- 添加一个元素
l:push({"Sat"})
print("添加一个元素后的列表大小:", l:size())

完整示例 - 列表的大小

以下是在添加/移除元素后检查列表大小的完整示例。

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

-- 移除特定元素 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

function list:size()
   return self.length
end

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

print("Original List Size:", l:size())

-- 移除一个元素
l:remove({"Wed"})
print("List Size after removing one element:", l:size())

-- 添加一个元素
l:push({"Sat"})
print("List Size after adding one element:", l:size())

输出

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

Original List Size:	5
List Size after removing one element:	4
List Size after adding one element:	5