Talk:Singly linked list (C Plus Plus)

From LiteratePrograms
Jump to: navigation, search

Hmmm ... how far are you with your implementation? I've got a complete singly linked list C++ article lying around here. It also shows how to make the list fully STL compatible (iterators). I didn't submit it as I thought it was pointless because STL already had a list class though I thought it was nice to show how to make an STL-compatible class as a singly-linked list is quite straightforward ... Ruediger Hanke 14:50, 20 March 2006 (PST)

Only as far as you see. That sounds neat and it'd be great if you'd replace (or merge) my article with it. I have nothing against articles that redundantly replace standard functionality, since they can still be educational and a great takeoff point for specialised data structures, as long as you caution people to prefer the standard implementation unless they have specialised needs. Deco 15:01, 20 March 2006 (PST)
Ok, I've just replaced it (was easiest for me). It should be compiling now. This is the raw code I had written back then, no polishment. There's surely lots to clean up or improve. But for now it's time to go to bed. Ruediger Hanke 15:51, 20 March 2006 (PST)
Excellent! Thanks for the contribution. Leave the polishing to me. :-) Deco 16:04, 20 March 2006 (PST)
Hmmm, I'm currently not very happy with the insert method, which is linear-time. Traditionally, STL operations are almost always constant time, to avoid unpleasant surprises. To allow insertion before an element though, which is what insert() normally does, the iterator will have to keep track of the previous node. Also, since the iterator returned by end() will have to refer to the last node, the list has to keep track of this node. I'll go ahead and make these changes. Deco 17:05, 20 March 2006 (PST)
Follow-up: I found a nicer way to do this that doesn't require a special case for the first element. Still making changes. Deco 17:52, 20 March 2006 (PST)
I've completed my changes. What do you think? Oddly enough, it seemed to work the first time it compiled. Hooray! Deco 19:39, 20 March 2006 (PST)
Great! What I still would like to see is better test code than my original one. I think it would be neater if instead of some arbitrary calls the test code would assert() some properties of the list functions. E.g. that list size grows by one after an insert and the inserted element is in place; that a clear()ed list is equal to the empty list, that lst.erase(lst.insert(it, elmt)) is equal to the original list ... Also, I've noticed something strange. I just downloaded the code and got compilation errors. I noticed that your last change ("Fixed the wrong two methods") was just reflected in the history, but not in the wiki article page and the download archive. As I just added the last change, I redid your last change and now it's ok. Strange. Ruediger Hanke 09:51, 22 March 2006 (PST)
Yeah, my clock was temporarily wrong, which caused weirdness. One problem with my changes is that they've made it so that insertion no longer preserves the node that the passed-in iterator points to. Instead they make it point to the newly inserted node. I don't see any good way around this - one can pass in the iterator by reference and update it, which precludes passing in expressions, one can return the new iterator to either the inserted or the passed-in node, or one can just deal with the fact that insertion invalidates this pointer. Deco 09:54, 22 March 2006 (PST)
I would consider this a rather serious problem. There may be copies of the iterator passed to insert() around which would change as well. Also, push_front(), even though no iterator is passed, will have all head-node iterators pointing to a different list element then. Removing elements has similar problems, as I see it the iterator passed to erase is still valid but points to the next element, but the one thereafter which was on the element past the one deleted (which is still in the list) is now invalid. This is not what anyone would expect.
I would consider it a better way to restore the "proper" iterator behavior, add _after versions of insert and erase, and make a note about the inefficiency of the "regular" insertion/deletion methods or simply remove them. Ruediger Hanke 11:28, 22 March 2006 (PST)
You're right about the invalidation behaviours. Your idea seems simpler, but unfortunately also makes it so that algorithms cannot be generic over both singly-linked and doubly-linked lists, since doubly-linked lists (for no particular reason) don't support insert/erase_after. I'm tempted to just say "insert/erase invalidate all iterators except the one they return", but that isn't very nice. Either way we definitely should not have any linear-time operations. Deco 12:05, 22 March 2006 (PST)
I just noticed that the SGI STL implementation has a singly-linked list extension (I somehow must have missed that before). If you read the performance note, they've done what I just suggested: do some _after methods. They left in the regular (inefficient) insertion/deletion methods. Ruediger Hanke 12:16, 22 March 2006 (PST)
Yeah, I knew about that, sorry for not mentioning it. That sounds good, and I'll clean up the article, but I would still leave out the inefficient insert/erase methods rather than put a big scary warning about them. Deco 12:26, 22 March 2006 (PST)
That's fine with me, although I could rather live with a warning about the inefficiency of two methods than about iterators invalidating or referencing different list elements than before after insert/erase ... Ruediger Hanke 13:35, 22 March 2006 (PST)
I agree. We now do neither of those things. What do you think? Deco 13:38, 22 March 2006 (PST)
Oh, and I agree re making the test code use asserts, and writing some real unit tests. I'm still considering somehow incorporating unit tests into LP, but there are difficult security considerations to overcome. Deco 10:46, 22 March 2006 (PST)