First and Last Nodes

[HybridM]

Hey all,

Very quick question, I'm writing a Doubly Linked List, and when it came time to code the Append() function, I found I didn't know if the First Node should have its Prev Node set to the Last Node in the list, and visa versa for the Next Node of the Last Node.

Can someone enlighten me?

Wow that looks confusing, hope it's not too bad.

[Cat]

It depends on if it should be circularly linked or not.

[HybridM]

Well, in a strange way that's kind of the question I was asking. It just sounds like it would be more efficient when seeking/inserting etc. if I could go quickly from the front to the end, rather than going a long way through.
But then again also it would probably be just as quick to have a small if statement to check whether it's quicker to go from the First or Last.

I'm not sure which way to go.

[Cat]

Well, you SHOULD have pointers to first and last anyway, and searching would usually go from first to last; why write an algorithm that wrapped around?

Circularly linked lists are good for circular queues, but if it's just a normal list, I wouldn't.

[HybridM]

I do have pointers for first and last.
The thing is if the list was quite large and the user wanted to access the third last node or something it doesn't make sense to go all the way from the first element to the one they want, so I would want to go backwards from the last.

what I was torn by was whether I should have it check to see which way would be quicker, or if the overhead from that would make it useless, unless the list was REALLY big.

[Cat]

If you want to be able to specify "third to the last node" or such, use a std::vector or std::deque, not a doubly linked list.

In general, linked lists should be used when your only operations are going to be sequential accesses -- "third to the last" works much better with random access structures.

[HybridM]

Yeah, sorry cat, I just realised while reading my book about List that what I was really doing was a vector, not a list.

I'm concerned Cat, I can't think of anything decent to program.

[elad]

HybridM:
what's wrong with doing what you were doing? In this case, who cares if using a vector is "easier". Try to get to where you wanted to go (third node from the back) using the doubly linked list. That's not an unreasonable project. True, it's not the next blockbuster program, but it provides a learning experience, and that's what most of us are after.

if you really want a project, here's one for you. I thought it was fun and provided me with a valuable learning experience, expecially when alternate source code solutions were posted.

Assume there is a cube of cheese that consists of 27 cheese cubies, each cubie of size 1 stacked in three layers of 9 cubies each, like a Rubiks cube. You're a mouse trying to eat as much of the cheese as you can by trying eating one cubie at a time starting at any given, arbitrary cubie and going to any adjacent cubie from there, etc. Once you've eaten a cubie you can't go back there again, it's just open space. Eventually you will have eaten all the cubies or end up in a position where there are no more adjacent cubies to eat next even though you haven't eaten all 27 cubies. The solution will be to determine what's the maximum number of cubies you can eat and describe one route to take to reach that number of cubies? Assume you have to start from the exterior of the cube, but you can start at any cubie you wish. Use standard C++ in your program as much as possible.

[HybridM]

Thanks elad, I might try something like that.