Programmers: Need a good example of a doubly linked list (C++)

[-=Germania=-]

I know that this is unrelated, but I really need a good example of a doubly linked list ( I have been programming and didn't realize just how crappy our book is - Seriously, none of the "examples" have even worked correctly).

I just need to see an example that recognizes/can hold information on the node and some element of search to it. The point is to just see some piece of code that works and that I can traverse to better understand the implementation. ( I need to do some odd deletion/add stuff, but that is not a problem).

This is for a lab that I am working on. I did the rest of the work - since it uses multiple data structures to hold data that is being updated and play around with stuff.

*Google search didn't turn up anything useful*

* I would have had more time to dedicate to this if I didn't have to design a microcontroller schematic (pin level) last night along with many other assignments over the weekend.* (I should'nt take so many classes!)

Thanks in advance!

-=Germania=-

 

[Mortalcoil]

Not sure if it helps.

Doubly-Linked List

 

[Clutz]

Crap, I don't have any code on this machine that uses linked lists, but I think I may have some residual code on my desktop using doubly-linked lists. If I find it, and no one else has anything to post, I'll post it here. I'm self taught, so my style is kind of crap, but it works.

 

[Arainach]

The overall concepts are pretty simple:

(This is from memory)

Deletion:
(on node)
Code:

[left]this->prev->next = this->next this->next->prev = this->prev delete this[/left]

Insertion:
(from node)
Code:

[left]temp = this->next this->next = new Node() this->next->prev = this this->next->next = temp[/left]

(from some central "list" data structure") Code:

[left]this->last->next = new Node() this->last->next->prev = this->last this->last->next->next = this->first this->last = this->last->next[/left]

With a few border cases for inserting the first node and deleting the last one and all that - essentially just checking for null pointers.

Really, you'll get a MUCH better understanding from having to write it yourself than you ever could from looking at code.

 

[-=Germania=-]

Yeah, last night I just went cracking at it and got a large portion of it done. I am not finished though... I just got way too tired and slept for a few hours last night. I am taking a break right now - looks like I am working through a friday night....lame

 

[n_maher]

I think it's about time we started a Homework-Fi forum for threads like this.

 

[ingwe]

Quote:

Originally Posted by n_maher /img/forum/go_quote.gif I think it's about time we started a Homework-Fi forum for threads like this.

And...this really irritates me. A ::huge:: part of the process (in school, when learning elementary data structures) is figuring it out for one's self.

In the real world it is rather easy to discern those who paid their dues from those who didn't.

 

[Clutz]

Quote:

Originally Posted by ingwe /img/forum/go_quote.gif And...this really irritates me. A ::huge:: part of the process (in school, when learning elementary data structures) is figuring it out for one's self. In the real world it is rather easy to discern those who paid their dues from those who didn't.

I think that is a ridiculous position to take. If universities actually considered this to be a reasonable attitude to take towards teaching, they wouldn't have tutorials. The reason that smaller universities do a better job of teaching undergraduates is because they have smaller class sizes and more one-on-one time between teacher and student. The reason that most professors only take on a few graduate students at a time is so that they have the time to spend one-on-one time with their graduate students. No one figures everything out for themselves.

 

[ingwe]

Quote:

Originally Posted by Clutz /img/forum/go_quote.gif I think that is a ridiculous position to take. If universities actually considered this to be a reasonable attitude to take towards teaching, they wouldn't have tutorials. The reason that smaller universities do a better job of teaching undergraduates is because they have smaller class sizes and more one-on-one time between teacher and student. The reason that most professors only take on a few graduate students at a time is so that they have the time to spend one-on-one time with their graduate students. No one figures everything out for themselves.

Oh please. I suggested none of that. What's ridiculous is the extent of your inference with which you obviously pulled out of thin air.

 

[vagarach]

This reminds me of an assignment we had, to write a BigInteger class using only linked lists. The loss of my beloved Strings, Ints, and so on had so upset my way of thinking, I designed a recursive algorithm to increment a BigInteger by stepping through all the nodes in succession and changing their values.

Instead of calling something like add(1)

These assignments are all about reinventing the wheel, and it is only by doing so that any learning takes place. We were doing this all in Java, and well, it comes with a BigInteger class anyway! Talk about frustrating.

 

[Clutz]

Quote:

Originally Posted by ingwe /img/forum/go_quote.gif Oh please. I suggested none of that. What's ridiculous is the extent of your inference with which you obviously pulled out of thin air.

Quote:

And...this really irritates me. A ::huge:: part of the process (in school, when learning elementary data structures) is figuring it out for one's self.

I pulled nothing out of thin air. What I was saying, as it seems you are incapable of inferring, is that it is ridiculous to think that people should have to figure things out for themselves and not depend on others for help. You clearly stated that it bothers you that people are unwilling to figure stuff out for themselves. There is nothing wrong with asking for help. Furthermore, your original post seems like threadcrapping.

 

[fordgtlover]

Quote:

Originally Posted by ingwe /img/forum/go_quote.gif And...this really irritates me. A ::huge:: part of the process (in school, when learning elementary data structures) is figuring it out for one's self. In the real world it is rather easy to discern those who paid their dues from those who didn't.

You feel compelled to tell us this?

 

[ingwe]

Quote:

Originally Posted by vagarach /img/forum/go_quote.gif snip... These assignments are all about reinventing the wheel, and it is only by doing so that any learning takes place. snip...

Yes! Exactly.

Its hard. Its meant to be hard. And, after graduation, it gets harder.


Quote:

Originally Posted by Clutz /img/forum/go_quote.gif I pulled nothing out of thin air. What I was saying, as it seems you are incapable of inferring, is that it is ridiculous to think that people should have to figure things out for themselves and not depend on others for help. You clearly stated that it bothers you that people are unwilling to figure stuff out for themselves. There is nothing wrong with asking for help. Furthermore, your original post seems like threadcrapping.

Woosh! One must make the attempt first. Then, when seeking help, bring something to the table.
Getting code from others because you don't have the time, or fortitude, or temperment, or _______ to suck-it-up is no excuse. The learning one should get will not take place.

If one has a paper to write, you don't ask for example papers. You write the paper, then seek guidance.

I agree, there is nothing wrong asking for help. Just don't expect the answers to be handed on a silver platter.

Quote:

Originally Posted by fordgtlover /img/forum/go_quote.gif You feel compelled to tell us this?

Now, ::that's:: thread crapping.

Listen, bub, as a software engineer with a CS degree (with high honors--means I aced every course) plus 18 years experience in the real world writing very non-trivial commercial systems and application software used by of many thousands of people, I'll say any damn thing I want regarding this topic.

 

[ingwe]

Quote:

Originally Posted by -=Germania=- /img/forum/go_quote.gif Yeah, last night I just went cracking at it and got a large portion of it done. I am not finished though... I just got way too tired and slept for a few hours last night. I am taking a break right now - looks like I am working through a friday night....lame

That's Great!

If you get stuck, please post some code and some questions and I or others would be glad to give hints and pointers (ewww... bad pun), etc.

And, I hear you regarding coding through a Friday night. Its not as if you're a Geek who lives to code--and has no other life.

 

[-=Germania=-]

Well,

I am a Computer Engineering major and my focus as of right now is on embedded systems and design. I really don't mind programming (time actually seems to fly by when I am), it just isn't something that I like better than watching a movie or hanging out with friends.

The courseload I deal with on a daily basis is unreasonable. I should get one hour a day to just relax and not think about everything else. There should be no reason that I get less than 6 hours of sleep a night, but this is not so.

My grades are good and I don't cheat (unlike a very large portion of the student body). It is my conscience which prevents me, and the fact that I cannot lie worth a darn.


I did figure everything out and am just finishing up now. I should be done in about 4 hours - break for lunch.

Also, I wouldnt have been asking online if my professor wasn't out of town and the TA barraded.

I don't object to just cracking at it, but a little help never hurt.