Thread: Linked List Class Implementation

Whoops, totally missed that it was doubly-linked. Must have been thinking of a different thread.

In my opinion, the exercise of building a linked-list is the best exercise for learning the combination or raw-pointers and manual memory management. Why?

Because it's probably the simplest task where where you cannot possibly get it done without a proper understanding of pointers. And it properly demonstrates the usefulness of pointers AND dynamic memory allocation, unlike examples where the pointer points to a local variable.

I'm honestly asking; why start with the extra complexity?

One could say the same thing about having to learn smart pointers in addition to list building. But point taken.

You said "can't". You said that is simply could not be done.

It seems you took my usage of "can't" too literally, or I used the word when I shouldn't have.

Well this has certainly very much changed my perspective somewhat. It hasn't changed my opinion, but I can certainly see the other perspective very clearly.

Originally Posted by iMalc

No, it's very clearly a case of "you pay for what you use".

I hardly think so. It will be overshadowed by the time it takes for new to return! Unless I can get proof that it really does affect the speed of the list by a significant amount of time, I am going to say you are paranoid in this case.
Pay only for what you use is good attitude, but it has its limits.

Oh I agree with much of that. Lets look at it this way:
This may be the C++ forum, but teaching how to implement a linked-list is really more appropriate to C. In C++ one normally wouldn't write a linked-list by hand anyway. If you're teaching something that one would typically only do if using C, then teach how it would be done in C. Otherwise you're learning how to do something that you wouldn't do anyway.
Don't teach the skills of one language within the context of another. That's where many teachers get it wrong, teaching C/C++ as though it were one language.

Linked lists are great for teaching how pointers work, but that does not imply they are great for teaching how to do manual memory management with dumb pointers. I don't get your "this is a dumb C++ example, this is a good C example." A data structure is language independent. There is always a point in having people learn to implement their own data structures, and it's usually not because they should use them in production code later.

You know, using a doubly linked list for education of pointers, smart pointers and circular references is a good foundation, I think. People will understand 1) how the concept of pointers work (we can easily add and remove nodes everywhere) 2) make_unique* for new dynamic allocations 3) weak_ptr for dealing with circular references, and the knowledge that it's just not point and shoot - even with smart pointers, you have to be careful about circular references or you will get memory leaks.
That seems to me like it teaches a lot of valuable stuff, the C++ way.

* Coming in C++14.

Linked lists are great for teaching how pointers work, but that does not imply they are great for teaching how to do manual memory management with dumb pointers.

Could you expand on that possibly? If linked lists by implication aren't great for teaching how to do manual memory management, then how do they teach how pointers work at all?

I don't get your "this is a dumb C++ example, this is a good C example." A data structure is language independent

I think the point is that C has more implementation options than C++ does. Consider the standard <list> library, what would you change about it? The answer is probably not much. So most alternative interfaces will have funny problems that the standard one doesn't have. And I highly doubt that a student would reproduce the standard interface, unless there was a lot of direction. But that's just what I think about what he's saying. You might want to reread that part.

There is always a point in having people learn to implement their own data structures

What do you think that point is?

You know, using a doubly linked list for education of pointers, smart pointers and circular references is a good foundation, I think. People will understand 1) how the concept of pointers work (we can easily add and remove nodes everywhere)

Well, I agree, but not for the reason that you stated. To be able to add and remove nodes everywhere, a linked list is self-referencing. Pointers are the implementation tool you have for that. The way pointers work is independent from that. But seeing a practical use of indirection helps explain why you need it. People also get practice dealing with indirection, so they learn what is required of them.

In my opinion, although this depends on aptitude, the linked list data structure also helps you establish abstract thinking that you need to understand what pointers do. It's reasonable to assume that you don't understand what a pointer does until you can see pointees and arrows with your mind's eye.

2) make_unique* for new dynamic allocations 3) weak_ptr for dealing with circular references, and the knowledge that it's just not point and shoot - even with smart pointers, you have to be careful about circular references or you will get memory leaks.
That seems to me like it teaches a lot of valuable stuff, the C++ way.

And I agree with you because I think smart pointers can teach all the things I mentioned above. It probably just takes a skilled teacher and the right lessons. I wish I had your optimism. I think that the semantics of all the smart pointers you mention have the potential to create information overload though, and then we end up with people who don't necessarily understand the linked list data structure. It would be a small miracle if they came out of that understanding smart pointers.

[edit] I want to be clear that I don't hold you responsible for the problems with the approach that you advocate (well, maybe I should...) BUT I don't expect you to provide me with the latest and greatest way to run a CS course. [/edit]

You picked the wrong point to argue on...

Originally Posted by Elysia

I hardly think so. It will be overshadowed by the time it takes for new to return!

I don't even need to argue the truth value of that because it's irrelevant. It is not about relatives, it is about absolutes. There is either a cost, or there is zero cost.

Unless I can get proof that it really does affect the speed of the list by a significant amount of time, I am going to say you are paranoid in this case.

Until you come to understand that the "pay what you use for" statement is valid regardless of how little time you think it takes, I am going to say that you are outright wrong in this case.

Pay only for what you use is good attitude, but it has its limits.

No actually, it very clearly doesn't; most certainly not in the way you are suggesting.

So many of the things C++ provides only have a small overhead, and one could make a case for most of them to pay the cost regardless of using it or not. Then what would happen is that you suddenly have a program that is horribly slow because the language is allowing for 100+ features that you are not using, and you would understand why the "pay for what you use" philosophy exists, and that it is absolute.

Originally Posted by whiteflags

Could you expand on that possibly? If linked lists by implication aren't great for teaching how to do manual memory management, then how do they teach how pointers work at all?

The point isn't to avoid pointers, but to avoid manual memory management with new and delete. Smart pointers emulate pointers, so they're different from stack objects in how you use them, so obviously one must understand how to do so. So essentially, what I am saying is that you will get to learn about pointers and how they work, but you don't have to understand how to allocate with new and delete with delete. The smart pointers will take care of the deallocation.

What do you think that point is?

Possibly understanding the data structure better and learning how construct good interfaces. There are probably more...

Well, I agree, but not for the reason that you stated. To be able to add and remove nodes everywhere, a linked list is self-referencing. Pointers are the implementation tool you have for that. The way pointers work is independent from that. But seeing a practical use of indirection helps explain why you need it. People also get practice dealing with indirection, so they learn what is required of them.

In my opinion, although this depends on aptitude, the linked list data structure also helps you establish abstract thinking that you need to understand what pointers do. It's reasonable to assume that you don't understand what a pointer does until you can see pointees and arrows with your mind's eye.

That is an important part and is there regardless of whether you use dumb pointers or smart pointers, so yeah, I agree with you there. It is good practice and they're going to have to learn it regardless.

And I agree with you because I think smart pointers can teach all the things I mentioned above. It probably just takes a skilled teacher and the right lessons. I wish I had your optimism. I think that the semantics of all the smart pointers you mention have the potential to create information overload though, and then we end up with people who don't necessarily understand the linked list data structure. It would be a small miracle if they came out of that understanding smart pointers.

I don't know about that. Considering they will get memory leaks unless they did it right, I would think that they should a little better understanding of smart pointers afterwards.
There is always the potential for information overload. I can't deny that. I'm also not a teacher and to my knowledge, this approach hasn't been used before (heck, it's extremely rare to find a course that teaches C++11 top-down), so I can't really say how it turns out.

Originally Posted by iMalc

So many of the things C++ provides only have a small overhead, and one could make a case for most of them to pay the cost regardless of using it or not. Then what would happen is that you suddenly have a program that is horribly slow because the language is allowing for 100+ features that you are not using, and you would understand why the "pay for what you use" philosophy exists, and that it is absolute.

Oh nooez! Using if instructions causes pipeline stalls! They're evil! They have too much overhead! They must not be used!
On nooez! Accessing that next node in a linked list causes cache misses! They're evil! They have too much overhead! They must not be used!
On nooez! Virtual functions causes an extra indirection and cache misses! They're evil! They have too much overhead! They must not be used under any circumstances!

And in this case, you are paranoid. Shaving one extra cycle is called premature optimization.

Originally Posted by phantomotap

How do you not understand that while you are willing to make that "trade off" most people aren't willing to because it only buys you one thing: a simple destructor. (No. it does not buy you freedom from memory management; dealing with weak/strong references is just as complex.)

Soma

I understand that there is always a tradeoff. But this is not some extremely high performing, near perfect data structure we're talking about. To do that, you'd have to probe it, test it, profile it, and so on all throughout the implementation to see that if fits your needs. Overkill for a newbie, I think.
Dealing with strong/weak references is something you are going to have to learn sooner or later, and I argue, is more important than learning raw new and delete.

You are simply jumping to too many conclusions... many of which I have never said anything about.
I don't know the costs of smart pointers. Perhaps your experience has taught you a little more? Does it truly have such a high cost that it could potentially derail the performance of the list [I don't know; this is not some counter argument]? If it truly does, then I am willing to concede that this is case of where one necessarily has to use dumb pointers to improve performance. But still, I have not found an argument against using it as an exercise for smart pointers, especially circular references.