Linked Lists

BlitzMax Forums/BlitzMax Beginners Area/Linked Lists

JBR	(Posted 2010) [#1]

Hi,

Have a list of objects (many 1000's) and I go through the list with the EachIn method.

I want to use Function RemoveLink( link:TLink ) to remove some of them during the pass.

How do I use this command?
I've to pass it a TLink but all I have is a TList

Jim

vinians

(Posted 2010) [#2]

Hi
You can do this:

local temp:Tobject
local i% = 0
For local ob:Object = EachIn List
   if (some_condition)  
      temp = List.ValueAtIndex(i)
      List.Remove(temp)
      exit 'get out from loop
   endif
   i = i + 1
Next

EOF	(Posted 2010) [#3]

MyList.Remove object if you want to avoid having to use :TLink

You can safely use this in an Eachin loop

Example:

Framework brl.standardio
Import brl.linkedlist

Strict
Global MyList:TList = New TList
MyList.AddLast "Pear"
MyList.AddLast "Apple"
MyList.AddLast "Banana"
MyList.AddLast "Peach"
MyList.AddLast "Lemon"
MyList.AddLast "Strawberry"


Print "--LIST--"
For Local name$ = EachIn MyList
	If name.StartsWith("P")
		MyList.Remove name
		Continue
	EndIf
	Print name
Next

End

A version with :TLink

Framework brl.standardio
Import brl.linkedlist

Global list:TList=New TList
Global link:TLink

list.addlast "I"
list.addlast "have"
list.addlast "eaten"
list.addlast "a frog!"

link=list.FirstLink()

While link<>Null
	Local t$=String(link.Value())
	If t$="eaten" link.Remove
	link=link.NextLink()
Wend

For Local name$=EachIn list
	Print name
Next

JBR	(Posted 2010) [#4]

Thanks Guys, very helpfull.

I'm basically looking for speed and I'm right in thinking that doing the link.remove is the fastest way?

Thanks again
Jim

JBR	(Posted 2010) [#5]

I'm finding this linked list of objects, using TLink is as fast as an array of objects using TLink.

Very happy!

Who was John Galt?

(Posted 2010) [#6]

Yes JBR, link.remove will be faster. You will need to store the relevant link as a field in your objects to get the benefit of this speed if you are removing objects in a 'random' fashion.

JBR	(Posted 2010) [#7]

Thanks

Czar Flavius

(Posted 2010) [#8]

Look at my post here http://blitzbasic.com/Community/posts.php?topic=91355

JBR	(Posted 2010) [#9]

Follow on question. When I remove a link, I want to add 3 more objects to the list.

Framework brl.standardio
Import brl.linkedlist

Global list:TList=New TList
Global link:TLink

list.addlast "I"
list.addlast "have"
list.addlast "eaten"
list.addlast "a frog!"
list.addlast "YUMMY!"


link=list.FirstLink()

While link<>Null
	Local t$=String(link.Value())
	If t$="eaten" Then
		link.Remove
		list.addlast "abc"
		list.addlast "abc"
		list.addlast "abc"
	EndIf
	link=link.NextLink()
Wend

For Local name$=EachIn list
	Print name
Next

It seems to work, but not sure if I'm being lucky!

Is this ok to do?

Jim

Czar Flavius

(Posted 2010) [#10]

We posted at the same time!

Unless I'm mistaken, you are being lucky. Addlast puts it on the end of the list, regardless where your current link was. Try looking up the TLink/TList methods, there might be something such as "insert after link" that you can try. Then remove the link.

Your code gives me this output:

I
have
a frog!
YUMMY!
abc
abc
abc

JBR	(Posted 2010) [#11]

Hi Czar, that is the output I get & want. Just the adding to the end of the list.

Having a look at your link.
Jim

Czar Flavius

(Posted 2010) [#12]

Ok I thought you meant you wanted abc after eaten and before a frog. :)

EOF	(Posted 2010) [#13]

One small tip, if the order is not important, adding an object to the top of the list is supposed to be a bit quicker:

list.AddFirst "Put me on top"

To wrap things up, here is a demo which I put together a long time back, which features everything to do with adding, removing, editing, and inserting items (before and after) into a list:

SuperStrict

Framework BRL.GLMax2D
Import BRL.Random

' Initialise a TList called mylist
' This is used to hold a list of strings
Global mylist:TList=New TList

' add some items to mylist
mylist.AddLast "Apple"
mylist.AddLast "Banana"
mylist.AddLast "Pear"
mylist.AddLast "Blackberry"
mylist.AddLast "Peach"
mylist.AddLast "Mango"

' Initialise a TLink called link
' Set it to point to the first item in mylist
Global link:TLink=mylist.FirstLink()

' store the string from the first item into selected$
Global selected$=String(link.Value())

' open a small graphic window
AppTitle = "Lists - Next/Previous example"
Graphics 400,300,0
SetClsColor $aa,$aa,$aa


Repeat
	
	' if user presses ESCAPE break out of the loop
	If KeyHit(KEY_ESCAPE) Exit
	
	' if user presses DOWN ARROW move to next item in list
	If KeyHit(KEY_DOWN) 
		link=link.NextLink()
		If link=Null link=mylist.FirstLink()
		selected$=String(link.Value())
	EndIf
	
	' if user presses UP ARROW move to previous item in list
	If KeyHit(KEY_UP)
		link=link.PrevLink()
		If link=Null link=mylist.LastLink()
		selected$=String(link.Value())
	EndIf
	
	' If DEL pressed remove selected item
	' Now point to the first item in the remaining list
	' If the list is empty exit from the loop
	If KeyHit(KEY_DELETE)
		mylist.Remove selected$
		link=mylist.FirstLink()
		If link=Null Exit
		selected$=String(link.Value())
	EndIf

	' insert an entry AFTER the currently selected one
	If KeyHit(KEY_A)
		mylist.InsertAfterLink("Lemon_"+Rand(1000,9000),link)
	EndIf
	
	' insert an entry BEFORE the currently selected one
	If KeyHit(KEY_B)
		mylist.InsertBeforeLink("Lemon_"+Rand(1000,9000),link)
	EndIf

	' if user presses RETURN key show item selected
	If KeyHit(KEY_RETURN)
		Notify "Your choice is "+selected$
	EndIf
	
	' change current selection to 'cucumber'
	If KeyHit(KEY_C)
		link=mylist.FindLink(selected$)
		selected$="Cucumber_"+String(Rand(1000,9000))
		link._value=selected$
	EndIf
	
	' show list and highlight the 'selected' item
	Cls
	SetColor $88,$44,$00
	DrawText "UP/DOWN = select item",10,10
	DrawText "RETURN  = confirm selection",10,24
	DrawText "DEL     = Remove selected item",10,38
	DrawText "A       = Insert 'Lemon' AFTER selected item",10,52
	DrawText "B       = Insert 'Lemon' BEFORE selected item",10,66
	DrawText "C       = Change selected item to 'Cucumber'",10,80
	Local y%=100
	For Local l$=EachIn mylist
		SetColor $22,$22,$22
		If l$=selected$	SetColor $ff,$ff,$ff
		DrawText l$,40,y
		y:+16
	Next

	Flip

Forever

End

plash

(Posted 2010) [#14]

One small tip, if the order is not important, adding an object to the top of the list is supposed to be a bit quicker

What makes you think that? BRL's linked list is actually a circular doubly-linked list (in which each link has a reference to its neighbors, and a root link links the first and last links), so that to get the last link you simply need to get the preceding link on the head link (which also has the first link as the next link).

ima747

(Posted 2010) [#15]

I try to stick with adding to the top of the list in speed critical situations not because it matters in bmax (as mentioned by plash it's doubly linked and circular so it doesn't matter), but because if/when I want to port that code to something else that doesn't have quick access to the end of the list I won't have to re-think for performance... but I also refuse to code bmax in anything but superstrict, and I use a lot of languages regularly, so maybe that's just me being anal :0)

JBR	(Posted 2010) [#16]

Hi again,

While link<>Null
     Local t$=String(link.Value())
     If t$="eaten" link.Remove
     link=link.NextLink()
Wend

I've got my particles working using Jim Brown's code. But I'm curious about a few things.

1) How does it work that you link.Remove and then you link.NextLink(). Surely link is gone after the link.Remove?

2) I have a list of objects, jim:MyType = MyType(link.Value()) and after link.Remove I find I can still access the jim fields at the removed link.

I guess what I'm trying to say is how does everything work after the link.Remove command?

Jim

Jesse

(Posted 2010) [#17]

Every object in a Tlink has a reference to the previous object and the next object. When an object is removed from the link chain, the reference from the previous object is change to the next object and the referece from the next object is changed to the previous object skipping the current object all together. the reason you can still access the previous object and the next object from the "current object" is because the reference to the next and previous objects are left in it. The reason that the object can be collected by the garbage collector is because now there is no reference to it any more but sense the current object still has reference to the previous and and next object you can still access the objects in the link chain.

I hope this is clear. if you have time look at the source code for Tlink. It might be easier to understand.

JBR	(Posted 2010) [#18]

Thanks Jesse, I think I understand ... used with B3D doing it all for me.

Garbage collection is 'new' aswell ... if there is a reference to an object then the object is safe.

Thanks
Jim

lesslucid

(Posted 2010) [#19]

Is it OK for me to add a new question here about TLists?

Can I change the members of a list in place? Or do I need to put them in a new list one by one, changing them as I go, and then replace the old list with the new list?

Jesse

(Posted 2010) [#20]

I don' know what you mean by number. objects in a list are not numbered unless you use a field to assign them numbers which in case you would have to number each object.

Gabriel

(Posted 2010) [#21]

Can I change the members of a list in place? Or do I need to put them in a new list one by one, changing them as I go, and then replace the old list with the new list?

You need to put them in a new list. Removing and inserting things from/into a TList while you iterate through it (with EachIn) is a recipe for breaking the TList. If you're not using the iterator, then it's probably fine.

Czar Flavius

(Posted 2010) [#22]

You can use a TLink to manually navigate through a list when you need something a bit out of the ordinary. Look up TLink in the docs.