Linked List in Pure Lua (Apache 2.0)

linked_list.lua

local Node = {}

Node.__index = Node

function Node:new(data)
    self = {}
    self._data = data
    self.prev = nil
    self.next = nil
    setmetatable(self, Node)
    return self
end

function Node:data()
    return self._data
end

local List = {}
package.loaded["List"] = list

List.__index = List

function List:new()
    self = {}
    self._head = nil
    self._tail = nil
    setmetatable(self, List)
    return self
end

function List:len()
    local count = 0
    local current = self._head
    
    while current ~= nil do
        count = count + 1
        current = current.next
    end

    return count
end

function List:at(i)
    local current = self._head
    local count = 0

    while current ~= nil do
        count = count + 1
        
        if count == i then
            return current:data()
        end
        
        current = current.next
    end
    
    return nil
end

function List:push(data)
    local node = Node:new(data)
    
    if self._head == nil then
        self._head = node
        self._tail = node
    else
        self._tail.next = node
        node.prev = self._tail
        self._tail = node
    end
end

function List:pop()
    if self._tail == nil then
        return nil
    elseif self._head == self._tail then
        local out = self._head:data()
        
        self._head = nil
        self._tail = nil
        
        return out
    end
    
    local prev = nil
    local current = self._head
    
    while current ~= self._tail do
        prev = current
        current = current.next
    end
    
    local out = current:data()
    current.prev = nil
    prev.next = nil
    self._tail = prev
    
    return out
end

function List:shift(data)
    local node = Node:new(data)
    
    if self._head == nil then
        self._head = node
        self._tail = node
    else
        node.next = self._head
        self._head.prev = node
        self._head = node
    end
end

function List:unshift()
    if self._head == nil then
        return nil
    elseif self._head == self._tail then
        local out = self._head:data()
        
        self._head = nil
        self._tail = nil
        
        return out
    end
    
    local current = self._head
    
    current.next.prev = nil
    self._head = current.next
    current.next = nil
    
    return current:data()
end

function List:insert(index, data)
    local prev = nil
    local current = self._head
    local count = 0
    
    while current ~= nil do
        count = count + 1
        
        if count >= index then
            break
        end
        
        prev = current
        current = current.next
    end
    
    if index > count then
        error("Invalid index")
    end
    
    if prev == nil then
        self:shift(data)
    elseif current == nil then
        self:push(data)
    end
    
    local node = Node:new(data)
    
    prev.next = node
    node.prev = prev
    node.next = current
    current.prev = node
end

function List:remove(index)
    local prev = nil
    local current = self._head
    local count = 0
    
    while current ~= nil do
        count = count + 1
        
        if count >= index then
            break
        end
        
        prev = current
        current = current.next
    end
    
    if index > count then
        error("Invalid index")
    end
    
    if prev == nil then
        return self:unshift()
    elseif current == nil then
        return self:pop()
    end
    
    prev.next = current.next
    current.next.prev = prev
    
    current.next = nil
    current.prev = nil
    
    return current:data()
end

return List