List.AddLast() and List.AddFirst() Different?

I'm possibly just having a brainfart here, but I'm getting some downright bizarre behaviour with TLists. Namely items being added to lists going walkabouts for no apparent reason. Almost as though TLinks are being reissued, and Removing those TLinks is causing different objects to be removed.

Anyway, I've managed to pinpoint one very clear difference, and that makes no sense either. Specifically, if I add my objects to the list with AddFirst() one particular object remains in that list. If I add all objects to the list with AddLast() that exact same object is not in the list any more. That is the only line of code that changes.

Given that no other code is changing, is there any logical reason why AddLast() and AddFirst() would cause a variance in which objects are and are not on the list?

I'm not using a Compare() method for any of the objects, derived objects or parent objects. I've come across a couple of very obscure bugs when using the Compare method before, but that's not it here.

When you remove/replace a link are you patching the links on both sides of the original to the new link?

I'm not sure what you mean by "both sides of the original".

Essentially I just have a function which is called at various times. It removes the object from the list it's in, and then evaluates a few conditions, before placing it in a new list and storing the link within the object. The conditions should never fail, so it should never fail to be in at least one list, and I have it set to throw a runtime error if this should ever happen, just to be sure that it doesn't.

EDIT: I use the same Link field to store the TLink, regardless of which TList the object is placed in. That shouldn't be a problem, should it? The TLink knows what TList it relates to. I specifically chose TLists over TMaps because I wanted the ability to remove an object from a container without necessarily knowing which container it's in.

Always use AddFirst(). Never use AddLast(). AddLast iterates through the entire list and will cause significant slowdown.

@Leadwerks: That makes no sense, Max lists are looped (don't know the technical term), meaning the head link of the list has the last link as its 'predecessor', so it should just insert the new object between head and head._pred.

Read up on linked lists, or just take a long look at the linked list source.
Each link has a field for the predecessor (previous) and the successor (next) links in the list, a linked list has a link called the head, which has the first link as its successor and the last link as its predecessor (the head is the link of the chain which separates the actual object links).

So to insert a link in another link you have to patch both sides of the link to the two surrounding the insert position (addfirst would be head->newlink->currentfirst->..; AddLast would be currentlast->newlink->head->..)

This may help.

EDIT: Leadwerks, list.AddLast() does not iterate the entire list. It calls InsertBeforeLink() which just patches between the currentlast and the head of the list, go ahead, look at the source yourself.

Well that's total nonsense. AddLast takes as much (or as little, if you wish) time as AddFirst.

It does as Plash says it should, and simply inserts before head - which it already has a reference for.

Edited at the same time you posted, Brucey :P

How long has it been like that?

@Gab, not sure what you mean. Have you got some runnable example code?
<edit> Isn't the TLINK destroyed when you remove from one list and a new one created when adding to another? I thought that was a reason why GC was called so often if this was happening a lot (e.g. in particle systems which had a 'free' and 'in-use' list.)

Oh. No, I'm not inserting a link into another link. I just remove one link and then generate another by adding it into a new list. I always know the new list it's going into. I just don't want to know which one it's already in, for speed reasons.


Not yet, that's why I'm posting, because I don't know what code is affecting it. It's an apparently simple problem, but would have been spotted a long time ago if it really was as simple as it appears. Somehow the TLinks are getting corrupted or being reused, or something.


Yep, I don't keep any other references to the link, so they should all be collected the next time the GC goes into action. Although I don't force the GC to collect immediately.

Whoops.. That was a typo, should've been 'to insert a link into a list (between two other links) ...'

So your just moving an object from one list to another?

You are not saving a TLINK somewhere and using it later are you? I think if you add to or remove from a TLIST, all TLINKS become invalid.

Correct. If you snatch a link out of a list you have to make it 'not exist' anymore, so if I were to take link2 out of link1->link2->link3 I would have to do link1._succ = link3 and link3._pred = link1; then further taking the predecessor and successor of link2 and pointing them to the surrounding links of the new position in a list (which then you would have to do so for the surrounding to the new aswell)..

In c++, when you add objects last to a list, it's the slowest way. According to my books. :)

Yep, pretty much.


Well I'm keeping the TLink that is return'ed when the object is added to the list. There's no other way to remove it.


That surely can't be. I've been using TLists for years, and I've never found that to be true. Are you saying that If I do this :

Global List:TList=New TList
Type Thingy
   Field Link:TLink
End Type
Local A:Thingy=New Thingy
A.Link=List.AddLast(A)
Local B:Thingy=New Thingy
B.Link=List.AddLast(B)

Then A.Link is already invalid because I added B later? If that was the case, there would be no point in AddLast and AddFirst even returning a TLink.

Obviously, it depends on the structure of your list.

TList is a double-linked list, or whatever the proper term is. That means, you can navigate it in either direction. Therefore, when at the head (or first item), you also have access to the tail (or last item).

So, to add AddLast, you get the head, and insert a new link between it and the previously last item.

Since the source is available, it's quite easy to see for yourself how it works :-)

No, the links are both valid. I must have been thinking of something else when I wrote my last post.

I also think I was thinking of something else. I have been doing a lot of php recently and I think I ran into something that had an issue like that and confused the two.

Sorry, don't mean to add to the confusion. :)

If you remove an object from lista the associated tlink is no longer valid and a new one created if the object is added to another list.

Local teststring:String="one"
Local list1:TList=CreateList()
Local list2:TList=CreateList()
Local mylink1:TLink=list1.addlast(teststring)
Print mylink1.tostring()
list1.remove(teststring)
Local mylink2:TLink=list2.addlast(teststring)
Print mylink2.tostring()

By keeping a variable pointer to the old tlink you keep it alive but, I believe, it doesn't point to anything (other than a memory block).

I am pretty sure it didn't used to be this way:
http://blitzmax.com/Community/posts.php?topic=59747#666475

That "advice" was never correct to begin with ;)
TList has allways been doubly-linked.

grable is right leadwerks... it's always been a double linked list. you are confusing AddLast with Remove. you never use Remove or ListRemove for performance. use RemoveLink as suggested in the link you posted.



actually the "double-linked" part just means it points to a previous and next item while the ends are null. taking that and having the ends point to the other ends instead of null make it cyclic. so TList is a double linked cyclic list.