Archived

This topic is now archived and is closed to further replies.

AcidJazz

Linked Lists...

Recommended Posts

AcidJazz    122
Grr for some reason i forgot how to load and read from a linked list... Its been awhile ;/ struct LIST { int number; LIST *next; LIST *temp; }; err i understand the concept (well sorta or i''d figure it out ) but i just cant seem to remember Also if you wanna throw in how to do doubly linked lists i''d be ever so appreciative... I know a single linked list looks something like LIST *bah; bah = new LIST; bah->next = new LIST; bah->temp = bah->next; bah->next->next = new LIST; grr BAHHH im done thinking about this, its something like that, help? :0 thanks

Share this post


Link to post
Share on other sites
edotorpedo    198

Well, something like this will do,

class LinkedList {

public:
LinkedList();
~LinkedList();
void add(int n);

private:
int number;
LinkedList *next;

};

LinkedList::LinkedList() {
next = NULL;
}

LinkedList::~LinkedList() {
delete next; // this will call the destructor of the next item
} // and so on and so on...

void LinkedList::add(int n) {
if (next != NULL)
next->add(n);
else
number = n;
}

Edo

edotorpedo

Share this post


Link to post
Share on other sites
edotorpedo    198

Well, something like this will do,

class LinkedList {

public:
LinkedList();
~LinkedList();
void add(int n);

private:
int number;
LinkedList *next;

};

LinkedList::LinkedList() {
next = NULL;
}

LinkedList::~LinkedList() {
delete next; // this will call the destructor of the next item
} // and so on and so on...

void LinkedList::add(int n) {
if (next != NULL)
next->add(n);
else
number = n;
}

Edo

edotorpedo

Share this post


Link to post
Share on other sites
Matt Calabrese    122
Yeah, but with linked lists, etc. it''s lots of times better to not use the STL just because you can make the nodes more integrated with what you''re doing much more easily (IE derive the node from the base class to make lots of method calls simpler). Though you can get the same effect from multiple inheritance from both the STL and your class, but multiple inheritance isn''t exactly a good idea to work with when you don''t have to, especially since linked lists are so easy to make on your own.

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Share this post


Link to post
Share on other sites
scaught    122
quote:
Original post by Matt Calabrese
Yeah, but with linked lists, etc. it''s lots of times better to not use the STL just because you can make the nodes more integrated with what you''re doing much more easily (IE derive the node from the base class to make lots of method calls simpler). Though you can get the same effect from multiple inheritance from both the STL and your class, but multiple inheritance isn''t exactly a good idea to work with when you don''t have to, especially since linked lists are so easy to make on your own.


Dude, this is the second post in row.

STOP SPREADING MISINFORMATION.

Thank you.
-scott

ps. One more and I''m going to have to ask you change the "Programmer" in your sig to "Congrammer".

Share this post


Link to post
Share on other sites
Matt Calabrese    122
Deriving a node from an already created object makes things alot easier to work with -- IE Passing it to a function as a refrence/pointer can be done directly if the parameter is one of the base class. You completely eliminate travering through a pointer on every single use. Sure, the STL is great, but I''ll take the ability to have simpler data to work with anyday, especially since linked lists are so simple to put together.

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Share this post


Link to post
Share on other sites
scaught    122
What the heck are you going on about? Show me one example where STL is just so cumbersome and impossible to use.

I don''t know about you, but I don''t think implementation gets any easier than:
typedef std::list< int > myIntList;

-scott

Share this post


Link to post
Share on other sites
Matt Calabrese    122
Nono, not like that. Thake this example:

class Someclass
{
...
}

class SomeclassNode : public Someclass
{
just with added next node and methods, etc.
}

now, take the funciton/method:

Somefunction( Someclass& thingee );

Then, you can pass either a node or the original class directly, and of course, have all of the other benefits of inheritance and polymorphism.

Sure it''s easier to just use the STL, but I''d rather take the extra 2 minutes to make a the methods for the linked list and derive it from the base object. In the long run, it makes things a lot simpler.





--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Share this post


Link to post
Share on other sites
Taulin    100
By all means, I believe if the solution you are after is already done (like in the STL), then re-use is a good thing.

However, it''s important to understand the fundamentals of a linked list since that theory continues onto the understanding of trees and other data structure implementations.

Share this post


Link to post
Share on other sites
Stoffel    250
True, Taulin. Learning is good. Maybe we can learn by pondering the example Matt gave:

  
class Someclass
{ /* members/methods to do with your object */ };
class SomeclassNode : public Someclass
{ /* linked list-related members/methods */
};

Why is this the wrong thing to do? Some directed points:
- code reuse (already mentioned)
- destructor mayhem
- potential memory overhead
- OO principles (e.g. relationship between Someclass, SomeclassNode and SomeclassList as opposed to the alternate solution of Someclass and a templated List and Node)
- dependencies (related to above)

And what reasons could the solution he gave be better? The only "benefit" listed is the ability to pass a node as an object, but on what metric is that a gain? Speed? Memory? Code maintainability?

Gotta get back to my project, I''ll check back in later. Please, discuss among yourselves.

Share this post


Link to post
Share on other sites
Matt Calabrese    122
quote:
Original post by Stoffel
Why is this the wrong thing to do? Some directed points:
- code reuse (already mentioned)
- destructor mayhem
- potential memory overhead
- OO principles (e.g. relationship between Someclass, SomeclassNode and SomeclassList as opposed to the alternate solution of Someclass and a templated List and Node)
- dependencies (related to above)



The only problem with deriving nodes from the base class that you presented that I truely agree with is the inability to have reusability between different types of lists. You'd have to define the linked list methods, etc. for each class you'd apply it to. This really isn't much of a problem though, and often times you will want slight differences in the way lists of different types of objects are worked with. I am very concerned about reusability with my code, however, in this specific case, I often prefer otherwise. Linked list operations are incredibly simple and to the point. If they weren't I'd always use the STL. However, that's not the case, and I'd much rather take the control of creating my own methods for times that I'd like to work intimately with the code.

Destructor mayhem? I personally have never had any problems with destructors here, and I really don't see why anyone would, especially coming from someone who probably has more experience than me. In fact, it gives you a lot more control as to how the object is destroyed IE should destroying the object destroy the next in the list as well or just that particular entry? It's up to you. Depending on the class, you'd prefer one method over the other. In my model objects I use the former, while with my optimization lists I use the latter.

Passing the node as an object was just one example. In general I was refering to the fact that they all be looked upon with like terms and treated in many ways as one type. Deriving a node from the associated base gives you all the benefits that you'd normally have with inheritance. Why not use that to your advantage?

One of those such advantages is, of course, polymorphism, as I stated before. One reason I use this method of derivation of nodes is for my vector class in my DimensionalValues API. I store nonstatic complex models as a linked list of vectors relating vertices. For the node, I redefine my "scale," "resize," etc. methods through polymorphism for to resize the current vector in the list as well as the next, which in turn, resizes the entire object. That way, I can have a group of vectors, objects, and anything similar, and I can perform all sorts of operations I'd like on them in just one simple loop (like one for scaling, stretching, etc.). That way, not only do I make certain things like this simpler to handle, but I also I have a very strong relationship between my objects and my general vector classes.

OO principles are also IMO much stronger when deriving a node from the base object. Conceptually, and also when programmed, what would you rather have a strong relationship between: Linked lists of datatypes that have nothing to do with each other and are only related through templating; or of linked lists and the datatypes that they link through inhertance with polymorhpism? To me, without a doubt relating the datatypes with their nodes is much more important, and the fact that it allows for polymorphism is a huge bonus. These relationships are strong not just programmatically, but also conceptually.

So sure, at first you'd say making a linked list with the STL is just one lineof code, but if you just take the time to do the above, which isn't much time at all, you can get it down to a level where you can still declare the list in one line, but habe lots of extra little goodies and trinkets (those are the technical terms *cough*) to work with. If you don't agree, that's fine, but this is how I often create linked lists, and after working with them like this, I don't want to go back!

EDIT: I'm not sure I'm getting what you are refering to when you say "dependencies"

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

[edited by - Matt Calabrese on March 20, 2002 1:07:22 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I have to defer to an earlier post and say again, don''t spread misinformation. As another poster pointed out, you are breaking several rules of OO design with your proposal. Can you please point out one design pattern that you used to come to your architecture? Here is how you can store anything in an STL vector:


  
class Object {
public:
Object();
virtual ~Object();
};

class SubObject : public Object
{
public:
SubObject();
virtual ~SubObject();

void SomeMethod();
};

class AnotherSubObject : public Object
{
public:
AnotherSubObject();
virtual ~AnotherSubObject();

void SomeOtherMethod();
};

typedef Object* ObjPtr;
// now here is where you can store anthing in the STL linked list

typedef vector<ObjPtr> ObjList;

// here is some code to use it

SubObject * psub() = new SubObject();
AnotherSubObject * psub2() = new AnotherSubObject();

ObjList list;

list.push_back( psub );
list.push_back( psub2 );

// now you can retrieve and use these items as Object(s)

// you can cast them, but be careful about casting to a subclass

// as you could cause access violations if you cast to the wrong

// type, these are all problems inherit with a non-template design


(SubObject *)list[0]->SomeMethod();
(AnotherSubObject *)list[1]->SomeOtherMethod();



Can you design a class that is more effecient and tested as well as the STL classes? Probably not in the time alloted for your project. Remember, you don''t have to reinvent the wheel if it has already been done and you can go down to Goodyear and pick up some Eagle Radials.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Breaking rules of OOP? I''m sorry, I must not have realized that rpoper use of inheritance was breaking the use of OOP. Using a linked list STL is not giving you some incredible efficiency that you can''t make on your own. If you can''t make your own linked list fast and efficiently, then that''s your problem. I''d like to see this "rule" that I''m breaking. Just because you think that one method easier, it doesn''t make it more efficient. I''d rather have more room for customization than being limited to the core design of the STL linked lists. If you don''t agree, then fine, don''t do it this way, but saying that it "breaks the rules of OOP" is just ignorant. Take your bashing elsewere.

Share this post


Link to post
Share on other sites
Waverider    169
I've made my own template linked list class from scratch as well.

I haven't gotten into STL just because I haven't proven to myself just how reliable or fast it is. Had I learned it in college I probably wouldn't have questioned it.

If I decide to go with STL, I will have a lot of references to change, so I'll have to seriously consider whether or not to use it before (if) I start my next big project.

I'm certainly not in a position to say whether or not it's worthwhile because I simply haven't used it.

Just another two cents.

[edited by - Waverider on March 20, 2002 12:13:11 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I tend to use my own linked lists also.. just gives me complete control over every aspect of the list. Like for my GUI program (the windows)... I don''t store the head/tail of the list, but rather the current with a pointer to next... which wraps around... so when I''m working with something, I just use the Current in the list, and traverse from there.. makes everything simpler. This A.) Saves memory as it doesn''t store 2 pointers (prev/next), is just as fast as using STL (if not faster) was VERY simple to write, I now have control over how I add/delete objects from my list. When something gets added, it gets added as the current object right before the old current object, so the old current object is now the second object... and it''s all free because I don''t have to traverse the list to find the current object, nor do I have to worry about storing consecutive objects or worry about adding them in the proper order.

This was just a single example of a custom linked list and why I wouldn''t use stl for this... also, linked lists are so simple to write, it adds an entire 5-10 minutes to you''re project if you know what you''re doing... AND I''m positive my linked list works properly, doesn''t have memory leaks, and won''t crash because I wrote it properly (they really aren''t complicated you know, some people are just lazy). I''m so sick of hearing how STL is so heavily tested, and it''s tried-n-true, and it''s "more efficient" , blah, blah blah, if you know how to program, and have a good grasp on linked lists... you can make one just as stable with little effort, and without any overhead, and with more flexibility (anything you want it to do it can!!). And how can adding extra over-head to something that has very little over-head be more efficient.. especially when it''s full of crap that I don''t need (in most instances).

Billy - BillyB@mrsnj.com

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Now, on to the original question: What exactly do you want to know about linked lists?

Billy

Share this post


Link to post
Share on other sites
Stoffel    250
For the original question, look here:
Google for Linked Lists Tutorial

To my talking points:
- code reuse (already mentioned)
The code given is not reusable. If I have a linked list of Widgets and a linked list of Wodgets, I have two linked list implementations. I believe this is fairly obvious.

- destructor mayhem
The most dangerous part of inheritence. Let's say I'm working on a multi-person team, and I decide to create a Widget class:

      
class Widget
{
char *m_buffer; // because all widgets need buffers

public:
Widget () : m_buffer (new char[WIDGET_BUFFER_SIZE]) { }
~Widget () { delete [] m_buffer; }
// more Widget functions here

};


A decent Widget class by any means. I want ten widgets, so in my program I have the declaration:
static Widget s_widgets[10]; // all I'll ever need is 10 widgets!

Now, a junior member of my team realizes that we may need more than 10 Widgets. In fact, we need to be able to create & delete new Widgets in arbitrary order. A perfect job for linked lists! While scoffing the name of the senior programmer (me) who lacked this foresight, he merrily hacks-out a linked list implementation, following Matt's lead:

  
class WidgetNode : public Widget
{
public:
WidgetNode *pNext;
WidgetNode *pPrev;
WidgetNode (); // does some tracking stuff

~WidgetNode (); // also does some tracking stuff

};

class WidgetList
{
WidgetNode *pHead;
WidgetNode *pTail;
public:
void push_back (WidgetNode *newNode);
WidgetNode* pop_back ();

The junior member chuckles at his ingenuity since he can pass WidgetNodes directly into functions that take a Widget pointer or reference as its input. The static array is now repleaced by a WidgetList, which initially has no nodes. He also chose to have the client of the list own the nodes, e.g. be responsible for creating new WidgetNodes and deleting unused WidgetNodes. So, instead of creating a static array, he creates new widgets himself and puts them on the list.

Of course the junior member doesn't tell anyone about these changes, and figures everything works as planned in the list (linked lists are simple!), so the changes go into the release. The next day customers are complaining that their program's tracking information doesn't work, it keeps crashing!

The reason, of course, is that Widget was never meant to be a base class. It's a Widget, and that's it. There is no reason to derive anything from Widget. I, being the original author, saw no reason to burden each Widget object with a virtual table pointer since I wasn't ever going to have any virtual functions. But the junior member decided to derive from it anyway, even though there was no virtual destructor . If you delete a Widget, it has no way to know what little derived classes (like WidgetNode) might be hanging off of it, so it can't delete them.

The junior member failed to realize the code he added to clean the list accessed things as Widgets, not as widget pointers:

  
void CleanList (WidgetList &list)
{
Widget *pWidget;
while (pWidget = list.pop_back ())
delete pWidget;
}

Of course it's legal to cast the WidgetNode returned from pop_back to Widget--it's automatic. Heck, this is what inheritence is all about! But every time he deletes the node, he deletes it as a Widget, not a WidgetNode. The destructor that performs the tracking tasks in WidgetNode is never called. Destructor Mayhem claims another victim.

There are ways around this. You can make sure that you always create a WidgetNode and always delete a WidgetNode, but the burden for doing things the right way is on the client of the list, not the list. You can hack Widget so that it does have a virtual destructor, adding 4 bytes of overhead to every Widget object--that is if you have the source code for Widget. If you're trying to make a linked list of external objects from another library, this cannot be done. But, if you had done things the right way (e.g. the way STL did it), none of this mayhem would be possible.

- potential memory overhead
An ideal (the way STL does it) implementation would have an iterator that's exposed to clients to traverse nodes, and an internal node class inside the list class that has three members:
pointer to next, pointer to previous, and the object contained (IN SIZE, not a pointer to the object). The overhead for this is 8 bytes per object. If it was done as Matt suggested, and virtual destructors were added, that would be an extra 4 bytes per object for the vtable pointer.

- OO principles (e.g. relationship between Someclass, SomeclassNode and SomeclassList as opposed to the alternate solution of Someclass and a templated List and Node)
Public inheritence should be used when the derived class will be used as its base class object. This is not what's happening. Widget is the base class. WidgetNode just tacks on some members. If you stray from this guideline, you will get horrificly-deep inheritence trees, possibly with gratuitous multiple inheritence (I heard this suggested in this thread once already). Inheritence should NEVER BE USED TO ADD FUNCTIONALITY. It should only be used to specialize existing functions. If a base class does not have virtual functions to override, you probably should not be using public inheritence. For a very good treatment on this, read "Exceptional C++" (by the guy who does the GOTW).

Furthermore, the task of maintaining a linked list is spread between two classes (WidgetList and WidgetNode), both of which casual users have to know about. WidgetNode could have private members for pNext and pLast, and have the list be a friend, but then how do you store a pointer and get to the next? You could have the list do it for you, but the details of WidgetNode are still exposed (though private) to the user. A much better and more object-oriented solution (STL) is to have the nodes be completely internal to the list, and to use iterators to traverse the list.

- dependencies (related to above)
If you've ever been part of a large project, dependencies are a major issue. For those who don't understand, this is a question of "what needs to recompile when I change this file?" Since WidgetNode depends directly on Widget now through public inheritence, the code that contains any implementation details of WidgetNode (which only has list functions) has to recompile whenever ANYTHING in Widget's interface changes. So if I add a knob to my widget (even a private knob), I have to recompile my linked list code. This is wrong.

And at the end of the day, what gain is there to using Matt's methodology? I mean what are we really saving? It certainly isn't "easier", what with all these potential problems and internal details the casual user has to keep track of. I heard mentioned that it "saves a pointer dereference", but here's a nifty fact about inheritence--the static cast is also a pointer dereference! When you pass a WidgetNode* into a function that takes a Widget*, the compiler has to modify that pointer so that it points at the Widget* part of WidgetNode*. It may or may not need to do anything, depending on how inheritence was implemented (either Widget's at the top or WidgetNode is). However, if you have multiple inheritence, odds are much greater there's going to need to be a dereference anyway.

If you had instead decided to implement it STL's way, with your private node class holding the contained object as the first member, there is no cost of dereferencing the object data--the address of the Widget and the address of the PrivateNode are one and the same! So since there's already no dereference cost, what exactly are we saving?

Here's the final point: the STL was written and designed by language engineers and language users who are much, much, much smarter than me or (possibly) you. Any time you think you can do something fundamentally better than they did, take a good, long, hard look at what their implementation is and what their reasonings might be.

[edited by - Stoffel on March 20, 2002 2:51:55 PM]

Share this post


Link to post
Share on other sites
Redemption    122
quote:

Why is this the wrong thing to do? Some directed points:
- code reuse (already mentioned)
- destructor mayhem
- potential memory overhead
- OO principles (e.g. relationship between Someclass, SomeclassNode and SomeclassList as opposed to the alternate solution of Someclass and a templated List and Node)
- dependencies (related to above)

And what reasons could the solution he gave be better? The only "benefit" listed is the ability to pass a node as an object, but on what metric is that a gain? Speed? Memory? Code maintainability?

Gotta get back to my project, I'll check back in later. Please, discuss among yourselves.



I usually code my own linked lists, out of habit I guess. I dont think using the STL gives that much of an advantage over not using it. I have to disagree with some of your points:

1. code reuse
okay you can have this one. very little code is getting reused however.

2. destructor mayhem
If you know a class is going to be inherited from, you make the destructor virtual. Programmer error here, can happen wether you use the STL or not.

3. potential memory overhead
If the memory requirements of pointers are your concern then you can use an array implementation. I wonder how the STL does it?

4. OO principals
I dont see where this comes in to play. I'm sure there are situations where you will want ObjectList to be an Object, that doesn't necessarily mean you should or shouldn't use the STL. That choice is an implementation issue and doesnt affect the design at all.

Now having said all that I cant really think of a reasing why NOT using the STL would be a better choice...




[edited by - Redemption on March 21, 2002 2:56:46 AM]

Share this post


Link to post
Share on other sites
Stoffel    250
quote:
Original post by Redemption
2. destructor mayhem
If you know a class is going to be inherited from, you make the destructor virtual. Programmer error here, can happen wether you use the STL or not.


Except that STL doesn''t use this inheritence hack, so it can''t happen using STL''s list.

What you fail to realize is that you may not be able to change the code. Let''s say I want to make a linked list of WAVEHDR, which I would want to do if I were writing a player using waveOutWrite. These are all WIN32 structures and functions. I can''t make WAVEHDR have a virtual destructor. Surely you must see that having to change a class or struct so that it can be put into a linked list is wrong. I don''t have to do that for arrays.

quote:

3. potential memory overhead
If the memory requirements of pointers are your concern then you can use an array implementation. I wonder how the STL does it?


You can''t use an array, these are fundamentally different types. I suggest your research linked lists.

The overhead I was talking about was not for the next/prev pointers in linked lists--those are part of the inherent overhead. I was referring to the extra vtable pointer, which increases the per-node overhead by 50%. STL''s implementation doesn''t use inheritence, so its node not required to have a vtable pointer.

If you''re curious as to how STL works, the source code is on your computer. Look at the file "list." in your compiler''s include directory.

quote:

4. OO principals
I dont see where this comes in to play. I''m sure there are situations where you will want ObjectList to be an Object, that doesn''t necessarily mean you should or shouldn''t use the STL. That choice is an implementation issue and doesnt affect the design at all.


Having to modify an object so that it will fit into a list, having clients depend on the internal detail of your list so they can use it, that sort of thing.

Share this post


Link to post
Share on other sites
SabreMan    504
quote:
Original post by BeerNutts
That is the ultimate generic list, and (GASP), no C++!

Unfortunately, it doesn't fit any definition of "ultimate" that I'm familiar with. It is both the "old way" and it is inferior to the templated solution. Use of the void* for genericity both bypasses the type-safety system and pushes certain responsibilities onto the client (such as type discovery). Another issue is that your solution only offers reference semantics, and cannot provide the value semantics in a non-invasive manner. Genericity is low, commodity value is low.

Oh, and it's only half a linked-list, if that. Where's its interface?

[edited by - SabreMan on March 21, 2002 3:18:23 PM]

Share this post


Link to post
Share on other sites