Linked List Class Implementation

This is a discussion on Linked List Class Implementation within the C++ Programming forums, part of the General Programming Boards category; Whoops, totally missed that it was doubly-linked. Must have been thinking of a different thread. In my opinion, the exercise ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,823
    Quote Originally Posted by iMalc View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #18
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    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]
    Last edited by whiteflags; 04-25-2013 at 11:53 PM.

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You picked the wrong point to argue on...
    Quote Originally Posted by Elysia View Post
    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.
    Last edited by iMalc; 04-26-2013 at 01:48 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,823
    Quote Originally Posted by whiteflags View Post
    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.

    Quote Originally Posted by iMalc View Post
    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.
    Last edited by Elysia; 04-26-2013 at 05:46 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,344
    Shaving one extra cycle is called premature optimization.
    O_o

    Out of curiosity, what's it called when you make the implementation of almost every other interface more complex to save on the implementation of a single one?

    And also, you keep saying things, like using `make_unique', which suggests you don't understand that without a sharing smart pointer to do the work, you are actually making the implementation more difficult. (Sure, it can only be the difference of wrapping the nodes in "RAII" facilities, but if you are going to have to do that anyway, why are you using a smart pointer?) If you don't go that, or similar, route, you wind up having to do a lot of gross, retarded, or dangerous things.

    Let's look again at your suggestion of `make_unique', you can't use a unique smart pointer for a doubly-linked list. (If you aren't implying a forwarding function which returns a unique smart pointer, what are you implying?) Well, you can, but you have to have two unique pointers to the same node which is a gross violation of the interface, and even then, you have to manually unlink or wrap with "RAII" facilities either of which is more complex than just writing a destructor for the dumb pointer approach.

    Let's look at alternative: using dumb pointers backwards and smart pointers forward. Congratulations, you still have to wrap the node in "RAII" facilities, or use a similar mechanism in place, to guarantee consistency in the face of exceptions for certain operations because without them the smart pointer will destroy itself still holding a reference to a node that should not be deleted.

    Using a sharing smart pointer buys you more, but a sharing smart pointer is more costly for walking backwards because you have to acquire a strong reference from a weak reference and then use the strong reference. (Sure, you don't have to use that kind of sharing smart pointer, but without automagic reference counting from value semantics the implementation is far more complex than with smart pointers.) It is an implementation detail, but you'll probably have to chase three pointers every time instead of just one.

    Now, me, I don't care about that small cost. Unfortunately, that isn't the only cost; now, instead of just swapping pointers, almost every method has to deal with this same process; you've made the implementation more complex and more costly for almost every operation.

    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

  7. #22
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,823
    Quote Originally Posted by phantomotap View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #23
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,344
    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.
    O_o

    If you are just sharing a resource as having all the goodies of value semantics, you don't need to know anything about weak/strong references. You just want a reference counting smart pointer; that the smart pointer is implemented over weak/strong reference semantics isn't something you need to care about.

    The case here isn't common; actually, you've gone out of your way to force the requirement, and it certainly isn't something that is natural to this data structure.

    But this is not some extremely high performing, near perfect data structure we're talking about.
    O_o

    Really? You are again displaying this attitude of not even trying to understand or engage an argument. You'd really rather continue to chase your "red herring" than potentially learn something? Your case of "This is how it is done." is the most serious I've ever seen. I've seen mine, so that's saying something. Well, I guess that severs my concern.

    *sigh*

    It is honestly kind of a relief. I was worried that I behaved poorly last time. ^_^

    o_O

    Well, okay, you addressed the performance issue. You win. The purely extra, due to being completely unnecessary, costs associated with sharing smart pointers is something that must be tested. Awesome. It just isn't worth advanced consideration; the costs of completely rewriting a component because you started with a poor assumption is so insignificant as to be laughable. Spectacular. It isn't as if these things could be tested without being in position; reaching for a component without considering and planning for the costs is the right way to go. Fabulous.

    Well, now that we are on the same page, it seems that you didn't respond to the implementation costs I discuss for a third time so I'm left to assume that you still don't understand that you are just trading complexity in one function for complexity in several. Not that it matters of course; the costs of implementation can be as high as they please; we are already willing to rewrite everything later to compensate for a lack of forethought so it isn't as if a couple or three lines of code in a dozen functions is a big deal, and debugging all this extra code? Trivial.

    *shrug*

    I mean, it seems a bit silly considering that your entire argument revolves around it being easier to use smart pointers than bother with dumb pointers and manual memory management, but, hey, at least we are on the same page.

    So, tell me more about these high performance data structures and how they aren't necessarily changed by the inclusion of completely unnecessary reference counts, indirect access, and secondary allocations. Taking the time to consider such things in advance is so ridiculous. I've been wasting so much of my time. Did you know that I haven't written a single line of code I intend to keep in over a week! I totally have, and it is just because I keep writing examples to test theory and performance. Wow. I am such an idiot. Let's face it; having to carefully consider every line of code I write has become a serious chore and all of my work is taking so very long.

    The truth is, I'm just jealous. I too want the skills to simply throw C++11 at my problems until they go away. I'll be a better, happier, and certainly faster programmer. I can't wait.

    Wait. I have an even better Idea. A lot of programming environments don't even let you make such decisions yourself. I don't even need to decide which C++11 feature to use. "RPG Maker", here I come!

    Déjà vu -> Soma -> actually off to play video games.

  9. #24
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,823
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #25
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,344
    O_o

    I'm going to have so much fun with that later. ^_^;

    Soma

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list implementation
    By denisa in forum C Programming
    Replies: 3
    Last Post: 10-04-2011, 09:10 PM
  2. Linked list implementation question
    By somekid413 in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2010, 02:33 AM
  3. One more linked list implementation
    By BlackOps in forum C Programming
    Replies: 17
    Last Post: 07-16-2009, 09:34 PM
  4. Linked List implementation
    By jcarouth in forum C Programming
    Replies: 4
    Last Post: 10-05-2005, 10:47 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21