Thread: What is the use of Double Linked List?

  1. #1
    Yin
    Guest

    Question 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?

    Please help~ Thanks very much!

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    2
    You sort of answered your own question.

    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. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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;
        }
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    12
    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. #5
    Registered User Dual-Catfish's Avatar
    Join Date
    Sep 2001
    Posts
    802
    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. #6
    Unregistered
    Guest
    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. #7
    Unregistered
    Guest
    Oops, forget what I said about typedef. : )

  8. #8
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    Last edited by hk_mp5kpdw; 04-16-2002 at 06:34 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  9. #9
    Yin
    Guest

    Question

    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. #10
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  11. #11
    Registered User heat511's Avatar
    Join Date
    Dec 2001
    Posts
    169

    also

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

    or so my teacher tells me...

  12. #12
    Yin
    Guest
    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. #13
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    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. #14
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked List Problem
    By Shiggins in forum C++ Programming
    Replies: 4
    Last Post: 03-10-2009, 07:15 AM
  2. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM