Deleting efficiently from a linked list

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
Yell0w
Prole
Posts: 28
Joined: Wed Nov 21, 2012 7:40 am
Location: Norway
Contact:

Deleting efficiently from a linked list

Post by Yell0w »

Hi lövers,
i experimented with linked lists today and its quite a strange concept, but i think im getting the hang of it.
One thing that i have a problem with is iterating over the correct data and deleting the ones that should be deleted (in the PerformCleanup function)
Id be very happy for some input on this.
Attachments
Linked List.love
(2.43 KiB) Downloaded 46 times
You can learn anything, but you cannot learn everything!
User avatar
Boolsheet
Inner party member
Posts: 780
Joined: Wed Dec 29, 2010 4:57 am
Location: Switzerland

Re: Deleting efficiently from a linked list

Post by Boolsheet »

It looks like your llDelete does unnecessary work. The main advantage of a linked list is that you don't have to reorder the array if you want to delete one item, just update the references to the next item or the head. You only have to call this once to remove all items marked for deletion.

Code: Select all

function llDelete(source)
	local current = source
	local previous
	
	while current do
		if current.delete == true then
			if current == linkedlist then
				-- If the current head of the list has to be removed,
				-- just let the head point to the next item.
				linkedlist = current.next
			elseif previous then
				-- If it wasn't the head, then the previous item should point
				-- to the one after the current.
				previous.next = current.next
			end
		else
			-- Nothing got changed, we move on to the next item.
			previous = current
		end
		current = current.next
	end
end
Shallow indentations.
User avatar
Yell0w
Prole
Posts: 28
Joined: Wed Nov 21, 2012 7:40 am
Location: Norway
Contact:

Re: Deleting efficiently from a linked list

Post by Yell0w »

Danke Boolsheet for simplifying it for me and cleaning up my code. Its easier to read now and hopefully performs better ;)
You can learn anything, but you cannot learn everything!
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 48 guests