Thread: Linked List

A weak_ptr is not a direct replacement for a plain pointer, because it has to be associated with some shared_ptr that actually manages the memory.

You can't just drop in shared_ptr's because nodes refer to each other.

With a plain pointer it is trivial to establish who owns the nodes: the list class itself.

With smart pointers it's making my head hurt. So each node owns the following node, but doesn't own the previous node?

Originally Posted by anon

With smart pointers it's making my head hurt. So each node owns the following node, but doesn't own the previous node?

Sounds logical to me.
Node A owns node B; thus node B cannot own node A.
A linked list is a trivial example where you have to think a little and not just throw in shared pointers. Which is a good exercise.

Good point, I've exposed a hole in my knowledge here. What I intended though was to make a pointer wrapper class emulating a pointer and use that.

I think something like auto_ptr or unique_ptr should have virtually no overhead. I guess a linked list would be possible where the next pointer is stored in a unique_ptr and the previous pointer in a unique_ptr with a do-nothing deleter.

But then again, I don't quite see the usefulness of smart pointers when implementing basic data types. The hardest part, IMO, about writing a linked list is hooking up the nodes correctly (which using an assortment of smart pointers can only make more difficult) and managing memory is trivial compared to that.

Originally Posted by anon

...The hardest part, IMO, about writing a linked list is hooking up the nodes correctly (which using an assortment of smart pointers can only make more difficult) and managing memory is trivial compared to that.

Not difficult at all, if you just think about it. And a little experience. Which is why it's such a good exercise.
In a single linked list, it's super easy. Put in shared_ptr or unique_ptr and you're done.
With double linked lists, you must make sure no node is owned by more than one. If you think about it, since the linked list class itself has a pointer to the first node, the node after the first node cannot have a shared_ptr to its previous node since it's owned by the class. Thus, all previous pointers should be weak_ptr and you're done.
Great exercise to learn about the problems with smart pointers which you really have to deal with in real code anyway.

Originally Posted by Mozza314

Don't implement operator[] - linked list are not for random access, it's inefficient to have to traverse an average of half the list to get an element out.

Finally, someone else who points out this kind of thing! I wholeheartedly agree.

You should keep track of the size of the list as you add and remove elements so that when you call length() you can return a number straight away. Traversing the list just for this is extremely inefficient!

GCC actually walks the list to get the size. The reason that some implementations do and some don't is that there is a trade off between constant time size() and linear time splice() vs linear time size() and constant time splice(). Can't do both in constant time.


C++ has the notion that you only pay for what you use. If you don't need a smart pointer in there then you should not be forced to. Simply allow the user of the class to use a smart pointer as their templated type.

Or you mean as the links themselves? That's actually not a good idea. If you utilised that to automatically delete the whole list by deleting just the first node say, then you end up with a recursive delete and could blow the stack, for example.
In a list, nodes don't own subsequent nodes. It's just a sequence. Enforcing some kind of ownership semantics where it doesn't belong is just wrong.

Originally Posted by Mozza314

I actually learned about this complication just the other day flicking through Scott Meyers' "Effective STL". Really makes the point that you should never do

Code:

someList.size() == 0

since that can be linear time and you have the perfectly appropriate empty() function you can use instead.

I find myself reasonably often bringing this up in code reviews or running into it in older code. Other's at work only use Microsoft's compilers, and simply don't know that the difference can be quite important if you're writing portable code.