Code Moderator
- Joined
- Sep 26, 2009
- Messages
- 9,468
I need a doubly-linked list that creates its own indices for some projects that I'm working on. I've kept the API as simple as possible to allow this resource to serve as a spartan framework for more complex systems.
A system as well-known as this should need little-to-no introduction. The functions and how they work are outlined in the comments below.
One thing I will mention is that you can designate a function that gets called when the list is looped. This will allow functions/anonymous functions to retain their local scope even when looped along with any number of others in the same system.
A system as well-known as this should need little-to-no introduction. The functions and how they work are outlined in the comments below.
One thing I will mention is that you can designate a function that gets called when the list is looped. This will allow functions/anonymous functions to retain their local scope even when looped along with any number of others in the same system.
Lua:
do
--[[--------------------------------------------------------------------------------------
Lightweight Doubly-Linked List v1.2.0.0 by Bribe
DLL basic API:
DLL.create() -> Returns a new table representing a Doubly-Linked List.
DLL.insert(list) -> Adds a new node to the list.
DLL.loop(list, func) -> calls "func(node)" on all nodes in the list. If "func"
returns true, the loop will break. Loop returns the last
node that was called.
DLL.remove(node) -> Removes the node from whichever list it is a part of.
DLL.destroy(list) -> Destroys the list and removes all of its nodes.
Node API:
readonly node.next -> the next node in the list.
readonly node.prev -> the previous node in the list.
readonly node.head -> the doubly-linked list table.
node.func -> function called when DLL.loop(list) is invoked without a second
parameter.
List API:
readonly list.size -> the number of nodes in the list.
----------------------------------------------------------------------------------------]]
DLL = {}
--[[--------------------------------------------------------------------------------------
DLL.create
Args: [head]
Returns: List node pointing to itself.
Desc: Can be used to reset an existing list by passing an existing head, or to create
a list from an existing table. The head is optional and this will create a new
one if you don't already have one.
----------------------------------------------------------------------------------------]]
function DLL.create(head)
head = head or {} --allows a user-specified head or generates a new one.
head.next = head
head.prev = head
head.head = head
head.size = 0
return head
end
--[[--------------------------------------------------------------------------------------
DLL.insert
Args: list[, node, func]
Returns: Node that was added to the list (if addition was successful)
Desc: Node can be an existing table, or a new table will be created to represent the
node. List can either be the head, or any point where you want the node to be
inserted. It will insert *after* the given list/node.
If a func is passed, it will be called with DLL.loop with the node as its
parameter.
----------------------------------------------------------------------------------------]]
function DLL.insert(list, node, func)
if node then
if type(node) == "table" then
if node.head then --A node cannot be added to more than one list and simply
DLL.remove(node) --resetting it will cause errors. Remove it first.
end
else
node, func = {}, node --User passed an func but not a node.
end
end
local head = list.head
if head then
node = node or {}
list.next.prev = node
node.next = list.next
list.next = node
node.prev = list
node.head = head
head.size = head.size + 1
node.func = func
return node
end
end
--[[--------------------------------------------------------------------------------------
DLL.remove
Args: node
Desc: Removes a node from whatever list it is a part of. A node cannot be a part of
more than one list at a time, so there is no need to pass the containing list as
an argument.
----------------------------------------------------------------------------------------]]
function DLL.remove(node)
if node then
local head = node.head
if head then
node.prev.next = node.next
node.next.prev = node.prev
node.head = nil
head.size = head.size - 1
return true
end
end
end
--[[--------------------------------------------------------------------------------------
Internal
Shows how you can inline this to grant you more flexibility or performance.
----------------------------------------------------------------------------------------]]
local function loop(head, func)
local node = head.next
while (node ~= head) do
if func(node) then break end
node = node.next
end
return node
end
local function defaultFunc(node) return node.func and node.func(node) end
--[[--------------------------------------------------------------------------------------
DLL.loop
Args: list[, func]
Desc: Iterates the given list and calls func(node) on each node that is found in the
list. If no "func" is given, it will try to call the dynamic func. If the "func"
returns "true", the loop will break.
Rtrn: The last node that is looped is the node that will be returned at the end.
----------------------------------------------------------------------------------------]]
function DLL.loop(list, func)
if list and list.head then
return loop(list, func or defaultFunc)
end
end
--[[--------------------------------------------------------------------------------------
DLL.destroy
Args: list
Desc: Destroys the given linked list.
----------------------------------------------------------------------------------------]]
function DLL.destroy(list)
if list.head and list.head == list then
loop(list, function(node) node.head = nil end)
list.next = nil
list.prev = nil
list.head = nil
return true
end
end
end
Last edited:
