-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|439|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Misc

Created : 23 August 2009
Edited : 25 August 2009
Language : Monkey

Linked List

C++ Linked List V1.0

After Phoenix's feedback, I'm probably not going to update this. I made this because I was unaware of std::list, so wanted to make a Linked List include for myself. Feel free to use it if you want, but it sounds like std::list is better!

Here's a Doubly-Linked List in C++ I've been working on. I designed it to try to emulate the features of Types in Blitz Basic, since I always found those to be rather useful.

Instructions are in the comments in the top of the file.

This is V1.0. If anyone has any suggestions for additional features, ways of improving the actual code, or any other suggestions, please post them, so I can make this better.

Finally, here's a simple driver program, demonstrating all the features of the Linked List. It seems a little bit convoluted to use, but it allows you to call all the functions of the class, for demonstration purposes.



Monday, 24 August 2009, 09:30
First off, being the standard library aficionado I am, I'd always opt for the std::list unless I needed something very specific. But I'll throw in some thoughts on what I noticed in the code, since I assume that this was a learning experience.

File organization
Conventionally, the .cpp extension is used for files containing only implementations, whereas .h files generally contain declarations (but sometimes also implementations, in the case of inline functions). In other words, you should never use #include with a file ending with the .cpp extension. I also personally find the old style of inclusion guards to be a bit tedious to type up all the time. I expect all modern compilers to support the "#pragma once" directive, which you can place at the top instead, to save yourself some typing.

Dynamic memory
Dynamic memory is usually avoided using raw pointers. Look up smart pointers (here's a popular one), since they handle it much more elegantly. Basically, if you forget to add a "delete xyz" statement somewhere, you have a leak. If a memory allocation fails, and you try to delete it in the destructor, the program will break. Smart pointers do that work for you. I also noticed that you used it in the example ("new LinkedList<Data>"), where automatic memory could have been used just as easily. I might be picky, but when doing other stuff you want to make sure to have leak-free habits.

The SetNext and SetPrev should probably not be exposed in the public interface, since they allow the user to break the list quite easily. I don't see the point of the Data class, as the list could just as well have been used with a regular integer as template argument. And don't forget const-correctness; members functions which don't mutate the class should have a const after the parameter list and before the function body, and pointers should always be returned as const if possible.

Personal moaning
I'm not very fond of the "my" prefix added to members. Prefix-less names work fine for me, at least. The commenting on top is good, but I feel that the comments in the source are excessive. For instance:

It's pretty obvious even without the comments what the code is about. There's also no need to prefix inherited members by the base class's name, as in "Node<T>::myNext".

Overall, it might've sounded like I think the code is crap, but that's not the message I intended to give. In the end, the code works, and that's what counts If you want some more features to add, you could try adding iterator support, as found in the standard library.
Monday, 24 August 2009, 12:45
Actually, that's all really helpful Phoenix! This was something of a learning experience for me, and constructive criticism is the best criticism. In response to your points:

-I was unaware of std::list existing, so I'll probably use that instead!
-Regarding .cpp and .h, I always found it rather annoying having the declaration in one file, and the implementation in another. But if that's convention, I guess I better get used to it.
-#pragma once is another thing I was unaware of. So, if I just put #pragma once at the top of the file, will that ensure it is only included once?
-I'll look into smart pointers. Is the only advantage that you don't have to worry about manual deletion, or are there others?
-All those public functions in Node seems to have been an oversight on my part, as was omitting the const stuff. Oops...
-Regarding prefixing stuff with Node<T>::... I found that this was necessary, because templates and inheriting from base classes don't get along very well (at least not in Dev-C++, which I am now dropping in favour of Code::Blocks, which the internet says is better). The templates refused to acknowledge that the inherited functions existed, and the only way to make it see them was to add Node<T>:: to the front.
-As for 'my', I prefer it for things like this, because it reminds me that the function returns the next node for that object, rather than setting it. But that's just a personal preference.

So yeah, thanks for the feedback. Since std::list exists, I'm probably not going to update this, and just use that instead. But thanks for taking the time to look through my code - it's a real help to me.
Monday, 24 August 2009, 13:21
  • You don't have to separate the declaration and implementation. But even then, the file should be named .h, instead of .cpp.
  • #pragma once does exactly what you think it does, i.e. it ensures that the file is only included once.
  • Smart pointers "only" take care of deleting the memory.
  • I think that it's just Dev-C++'s template support which is lacking, since the code builds over here without the base class prefix.

Monday, 24 August 2009, 13:53
Knowing data structures is important, even if you use the standard library.
Monday, 24 August 2009, 14:35
I had no idea you could just put #pragma once to avoid multiple inclusion!

Tuesday, 25 August 2009, 01:33
OK, thanks for that Phoenix.

@JL: I still plan on looking into how std::list works, to make sure I fully understand it, although I think I have a pretty good idea having learnt about linked lists to make this.
Tuesday, 25 August 2009, 01:51
It also says that this is implemented in Ruby, not C++!

I suspect Jay hasn't fixed that bug yet.
Tuesday, 25 August 2009, 03:41
Nope, my bad! When I went to edit this, it must have changed while I wasn't looking! When I went to change it back to C++, the drop-down list said HTML/CSS! I think it's not remembering correctly...