0 Replies - 1238 Views - Last Post: 28 December 2010 - 07:48 AM

#1 KYA  Icon User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3199
  • View blog
  • Posts: 19,230
  • Joined: 14-September 07

[LUA]A More Robust LinkedList

Posted 28 December 2010 - 07:48 AM

Description: Implement when you need a linear list of data. Implement recursive routines, if you want your list to hold tables. A linked list implementation in Lua. Emulates the use of a "class" to provide functionality of a data structure. Sample usage is included.
--LinkedList data structure
--Week 48
-- 12/28/2010

--create an empty table
--assign member functions
--debug tracer statements are commented out
LinkedList = {}
function LinkedList:create(val)
	local root = { value = val,  next = nil}
	--[[
		this allows us to call LinkedList functions
		from our instantiated object [which is really a table]
	]]--
	setmetatable(root, {__index = LinkedList})
	return root
end

--self refers to the object/caller
--in our case, the initial or "root" node
function LinkedList:append(val)
	local node = { value = val, next = nil}
	--empty list
	if(self.value == nil) then
		--print("Head node is nil ")
		self.value = node.value
		self.next = node.next
		return
	end
	local curNode = self
	while curNode.next ~= nil do
		curNode = curNode.next
	end
	curNode.next = node
	return
end

function LinkedList:displayList()
	--print("Root node in displayList(): "..self.value)
	local curNode = self
	if(self.value == nil) then
		print ("List is empty!")
		return
	end
	while curNode ~= nil do
		print(curNode.value)
		curNode = curNode.next
	end
end

function LinkedList:removeNode(val)
	if type(val) == "table" then
		print("Error! Must pass a non-table to search for.")
	end
	local curNode = self
	--head/root node is the value
	if(self.value == val) then
		--print("Removing head node: "..self.value)
		local temp = self.next
		if temp ~= nil then
			self.value = temp.value
			self.next = temp.next
		else
			self.value = nil
			self.next = nil
		end
		--print("New head node: "..self.value)
		return
	end
	lastVisited = curNode
	while curNode ~= nil do
		if curNode.value == val then
			--print(val.." found!")
			--print("last visited: "..lastVisited.value.." curNode: "..curNode.value)
			lastVisited.next = curNode.next
			curNode = nil
			return
		end
		lastVisited = curNode
		curNode = curNode.next
	end
	return
end

--sample usage
test = LinkedList:create("Bob")
test:append("Knowles")
test:append("Julie")
test:displayList()
print()
test:removeNode("Bob")
test:displayList()
print()
test:append("Joy")
test:displayList()
print()
test:removeNode("Joy")
test:displayList()
print()
test:append(5)
test:displayList()
print()


Is This A Good Question/Topic? 0
  • +

Page 1 of 1