Latest Uploads
isometric test

realtime

dungeon ma ... litz basic

realtime

Crystal Ca ... een So Far

rychan

Crystal Ca ... Screen V1

rychan

Day 5 Graphic

rychan

Mutanty Mo ... Workfiles.

steve_ancell

Code Snippets > Misc ( Created 23 August 2009 | Last Edited 25 August 2009)

Linked List by shroom_monk | No Votes
C++ Linked List V1.0
Written in
Monkey
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.

-->

Latest Comments

Posted : Monday, 24 August 2009, 08:30
Phoenix


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.

Design
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.

Posted : Monday, 24 August 2009, 11:45
shroom_monk


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.

Posted : Monday, 24 August 2009, 12:21
Phoenix


  • 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.


Posted : Monday, 24 August 2009, 12:53
JL235


Knowing data structures is important, even if you use the standard library.

Homepage : http://www.StudioFortress.com
Posted : Monday, 24 August 2009, 13:35
Afr0


O_O
I had no idea you could just put #pragma once to avoid multiple inclusion!

Noted!

Homepage : http://www.afr0games.com
Posted : Tuesday, 25 August 2009, 00:33
shroom_monk


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.

Posted : Tuesday, 25 August 2009, 00:51
JL235


It also says that this is implemented in Ruby, not C++!

I suspect Jay hasn't fixed that bug yet.

Homepage : http://www.StudioFortress.com
Posted : Tuesday, 25 August 2009, 02:41
shroom_monk


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...

Latest Posts
Joe's Storytime
spinal Thu 13:31
Ramble ramble/finishing stuff
caligula Thu 10:56
Rest Period
Kuron Wed 22:24
RollerCoaster Tycoon 4
rychan Wed 04:44
Password Security Safety
dna Tue 20:48
GameJolt Revenue
Jayenkai Tue 13:04
AGameAWeek Progress Report
Jayenkai Mon 14:41
Evil Mongoose
Mog Mon 12:27
Arachnophobics Beware
steve_ancell Mon 03:36
confirmation form?
steve_ancell Mon 02:08
More

Latest Items
Blog : FInally Some Game Dev Time
rychan Thu 15:35
Family : :c(
steve_ancell Thu 04:58
Showcase : isometric prototype
Jayenkai Thu 04:31
Showcase : dungeon maker algorithm
Jayenkai Wed 01:42
Dev-Diary : More Screens
Kuron Sat 09:01
News : Newsletter #221
Dabz Fri 10:07
Dev-Diary : Crystal Catch Development
rychan Thu 14:38
Link : Sfxr
rychan Thu 04:16
Showcase : SpringySquirrel
Jayenkai Tue 22:58
Dev-Diary : More Planning and Framework Learning
rychan Tue 17:23
Dev-Diary : Another Song
Kuron Tue 09:10
Link : Free 3D characters!
Jayenkai Mon 05:48
Family : Life...
Dabz Mon 04:57
Dev-Diary : New Song
Kuron Sun 17:32
Dev-Diary : Monkey Day 5
rychan Sat 06:53
More

Who's Online
psychicparrot
Thu, at 17:09
therevillsgames
Thu, at 16:54
caligula
Thu, at 16:52
rychan
Thu, at 16:41
Jayenkai
Thu, at 16:16
Cower
Thu, at 15:09
spinal
Thu, at 15:08
blanko1324
Thu, at 13:36
Kuron
Thu, at 12:56
rockford
Thu, at 08:22
Link to this page
Site : Jayenkai 2006-Infinity | MudChat's origins, BBCode's former life, Image Scaler.