1. ## What is the use of Double Linked List?

Why do we want to "doubly" link up the elements within the list?
I just wonder because I cannot get any idea about the use of it.

And, furthermore, for a normal singly linked list, when we dump it to screen, we usually do it in the first in last out manner (the easiest way). How can we do the reverse?

That is, how can we dump the elements to the screen in a First in First out manner?

I found it rather difficult, because the pointers in the singly linked list always point to the "next element" rather than the "previous element". How can I do it?

With a singley (spelling) linked list you can only traverse from the start to the finish. making it VERY messy to display the data from the nodes in the reverse order.

Using a doublly linked list, traversing backwards is just as easy at traversing forwards. Basically the advantage of a doublly linked list is the ability to jump forward to the next node, or backwards to the previous node.

I hope this makes some sence..its 2am here.

3. With a singley (spelling) linked list you can only traverse from the start to the finish. making it VERY messy to display the data from the nodes in the reverse order.
How is this messy?

Code:
```typedef struct NodeStruct
{
int iData;
struct NodeStruct* pNext;
} NodeType;

void PrintForward( NodeType* pCurrent )
{
if( pCurrent != NULL )
{
cout << iData << endl;
PrintForward( pCurrent->pNext );
}
}

void PrintReverse( NodeType* pCurrent )
{
if( pCurrent != NULL )
{
PrintReverse( pCurrent->pNext );
cout << iData << endl;
}
}```

4. I like that solution! I never thought of using recursion wioth a linked list, probably because it confuses me. But I see what's going on there... and it's not messy at all.

5. Gawd this has always confused me.. and I haven't personally come across it yet so I've never learned it..

Code:
```typedef struct NodeStruct
{
int iData;
struct NodeStruct* pNext;
} NodeType;```
What's the point of a typedef right there? and what's the NodeType do after the list?
I learned typdef as a useless keyword that does stuff like:

typedef unsigned short int USHORT;

I really wouldn't be suprised if I'm answering my own question.. I can kind of see the resemblance between the two... or maybe the typedef serves a completly different purpose used in this context...

Either way, I want to know

6. Typedef is used for compatibility with C. Thank goodness C++ has gotten rid of that silly keyword.

Also, I would not use recursion with linked lists in the the real world. With long enough lists you could get a stack overflow.

7. Oops, forget what I said about typedef. : )

8. What's the point of a typedef right there? and what's the NodeType do after the list?
Well, I started learning C years ago so maybe its just something I do out of habit. Using C++ you wouldn't have to do this, you could have just said:
Code:
```struct NodeStruct
{
int iData;
NodeStruct* pNext;
};

void PrintForward( NodeStruct* pCurrent );

void PrintReverse( NodeStruct* pCurrent );```
You could not do the above with C however, you would either need to do what I had in the previous post, or do this:
Code:
```struct NodeStruct
{
int iData;
struct NodeStruct* pNext;
};

void PrintForward( struct NodeStruct* pCurrent );

void PrintReverse( struct NodeStruct* pCurrent );```
If you compare this with what I had in the previous post, you can see that the typedef simply saved me a bit of typing in the definition of my functions. It essentially renamed the struct NodeStruct as NodeType so I wouldn't have to type out struct NodeStruct everywhere in the rest of the code.

9. Originally posted by hk_mp5kpdw

How is this messy?

Code:
```typedef struct NodeStruct
{
int iData;
struct NodeStruct* pNext;
} NodeType;

void PrintForward( NodeType* pCurrent )
{
if( pCurrent != NULL )
{
cout << iData << endl;
PrintForward( pCurrent->pNext );
}
}

void PrintReverse( NodeType* pCurrent )
{
if( pCurrent != NULL )
{
PrintReverse( pCurrent->pNext );
cout << iData << endl;
}
}```

Oh... How come my thread appear again? -_-" I thought it was eaten by the server... so strange.

Anyway, back to my point. I didn't understand the above quoted message.

What is the difference between the function PrintForward and PrintReverse? They looks fundamentally the same?! (Only the sequence of the 2 sentences in the content within the functions are swapped.) Both of them will print the elements of a linked list in the Last In First Out manner.

I think we need a pointer pointing to the "previous" element rather then the next element for printing in a First In First Out manner, isn't it?

But I don't know how can we make it, can anyone help? Thanks~

10. What is the difference between the function PrintForward and PrintReverse? They looks fundamentally the same?! (Only the sequence of the 2 sentences in the content within the functions are swapped.) Both of them will print the elements of a linked list in the Last In First Out manner.
As you pointed out, there is a difference in the order of the two statements within the PrintForward and PrintReverse functions. They do not print out the same thing. PrintForward will output the elements in the linked list starting from the head and working towards the tail. The PrintReverse function on the other hand will print out the elements in the list starting from the tail and working backwards towards the head of the list. You should be able to adopt this method to suit your needs.

11. ## also

its easier to delete a node from the list if it is doubly linked

or so my teacher tells me...

12. Originally posted by hk_mp5kpdw

As you pointed out, there is a difference in the order of the two statements within the PrintForward and PrintReverse functions. They do not print out the same thing. PrintForward will output the elements in the linked list starting from the head and working towards the tail. The PrintReverse function on the other hand will print out the elements in the list starting from the tail and working backwards towards the head of the list. You should be able to adopt this method to suit your needs.
Sorry, I dont see how by reversing the sequence of the two sentence can produce the reverse effect. It seems that both of them print elements in a First in Last out manner. But what I want is the First In First out one...

13. in single-linked lists going backwards in
1 2 3 4 5 6 7 8 9
means counting up to 9, printing it, then counting up to 9-1, printing it, etc...
it may not look messier in code but it takes up more time
a double-linked list going backwards in
1 2 3 4 5 6 7 8 9
means finding the end element, printing it, go back one, print, go back one, print, etc...

14. Sorry, I dont see how by reversing the sequence of the two sentence can produce the reverse effect. It seems that both of them print elements in a First in Last out manner. But what I want is the First In First out one...
Trust me, it works. Try it out. It probably wouldn't take more than 2 minutes to copy the code into your program and make the changes needed to suit your struct definition.