--The 'head' of the list (start at nil)
local head = nil

-- Each entry becomes a new head, with a 'next' member pointing to the old head
head = {next = head, value = "d"}	
head = {next = head, value = "c"}	
head = {next head, value = "b"}	
head = {next head, value = "a"}	

--Pick an entry to start iterating from
local entry = head

-- While there is another node to move to...
while entry do
	-- ...output the value of the current node...
	print(entry.value)

	-- ... then move to next node
	entry = entry.next
end

-- Last entry in the list
local tail = {value = "d"}

-- Add remaining entries
local head = tail
head = {next = head, value = "c"}
head = {next = head, value = "b"}
head = {next = head, value = "a"}

-- Link the last node back to the first node
tail.next = head

-- Pick an entry to start iterating from
local entry = head

-- Iterate over the list 3 times
for i = 1, 12 do
	-- Back at the start
	if entry == head then
		print("Starting at the beginning!")
	end

	-- Output the value of the current node
	print(entry.value)

	-- Move to next node
	entry = entry.next
end

local function insert(a)
	return {
		-- Add node 'a' after node 'b', and return 'a' for convenience
		after = function(b)
			if b.next then
				a.next = b.next
				b.next.prev = a
			end
			a.prev = b
			b.next = a
			return a
		end,
		-- Add node 'a' before node 'b', and return 'a' for convenience
		before = function(b)
			if b.prev then
				a.prev = b.prev
				b.prev.next = a
			end
			a.next = b
			b.prev = a
			return a
		end
	}
end

local head = {value = "a"}
local current = head
current = insert({value = "b"}).after(current)
current = insert({value = "c"}).after(current)
current = insert({value = "d"}).after(current)
local tail = current

-- Traverse list
print("Forward iteration")
current = head
repeat
	print(current.value)
	current = current.next
until not current

print("Reverse iteration")
current = tail
repeat
	print(current.value)
	current = current.prev
until not current