Thread: Reversal of Doubly Linked List using Recursion !!

  1. #1
    Registered User
    Join Date
    Sep 2014
    Posts
    51

    Reversal of Doubly Linked List using Recursion !!

    Hi,

    I am trying to reverse a Linked list using recursion but whenever I try to print it after reversal it prints only the last element of the list.

    Code:
    void reverseRecursive(Node **root, Node *temp)
    {
    	Node *next = temp->next;
    	if(temp->next == NULL)
    		{
    			*root = temp;
    			return;
    		}
    	reverseRecursive(&(*root), temp->next);
    //	printf("%d ", next->data);
    	temp->next = temp->prev;
    	temp->prev = next;	
    }
    Could you help me figure where the mistake lies?

    I have just posted the reverse function to enable easy readability rather than post the entire code

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    > I have just posted the reverse function to enable easy readability rather than post the entire code
    What makes you think the problem is here?
    There is more than a passing chance that the problem could be the list is already broken before this function is called - garbage in, garbage out as they say.

    Construct a simple test program to
    - create a DLL with just 3 nodes
    - a print function to print each node, including the addresses of itself, it's predecessor and it's successor
    - this reverse function
    - a main() to tie it all together.

    Then we can see where the problem really lies.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2014
    Posts
    51
    Sorry, for assuming. I am attaching the smallest possible executable code

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct Node
    {
        int data;
        Node *next;
        Node *prev;
    }Node;
    Node * createNode(int data)
    {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = data;
        newNode->next = NULL;
        newNode->prev = NULL;
        return newNode;
    }
    void BuildList(Node **root, int data)
    {
        Node *temp = *root;
        if(temp ==NULL)
            {
                *root = createNode(data);
            }
        else
        {
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            Node *newNode = createNode(data);
            temp->next = newNode;
            newNode->prev = temp;
        }
    }
    
    
    void printList(Node **root)
    {
        Node *temp = *root;
        while(temp != NULL)
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("\n");
    }
    void reverseRecursive(Node **root, Node *temp)
    {
        Node *next = temp->next;
        if(temp->next == NULL)
            {
                *root = temp;
                return;
            }
        reverseRecursive(&(*root), temp->next);
    //    printf("%d ", next->data);
        temp->next = temp->prev;
        temp->prev = next;    
    }
    
    
    int main()
    {
        Node *root = NULL;
        BuildList(&root, 67);
        BuildList(&root, 68);
        BuildList(&root, 69);
        BuildList(&root, 70);
    //    printList(&root);
    //    reverseIterative(&root);
    //    printList(&root);
        reverseRecursive(&root, root);
        printList(&root);
    //    printRecursive(root);
        return 0;
    }

  4. #4
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    In order to change the values actually at temp, just like for root, you need a pointer to a pointer. Not just a pointer.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Fundamentally, isn't it bad to use recursion in this instance? Maybe you won't encounter it in the wild but it seems like the number of function calls you'd have to make would grow with the size of the list which means you're vulnerable to overflows. Why not an iterative method? I think recursion is best left for when you know the maximum depth ahead of time.

  6. #6
    Registered User
    Join Date
    Sep 2014
    Posts
    51
    Quote Originally Posted by MutantJohn View Post
    Fundamentally, isn't it bad to use recursion in this instance? Maybe you won't encounter it in the wild but it seems like the number of function calls you'd have to make would grow with the size of the list which means you're vulnerable to overflows. Why not an iterative method? I think recursion is best left for when you know the maximum depth ahead of time.
    I know it is better to use iterative method, but I wanted to try it with recursion too. Just to learn

    Thanks.

  7. #7
    Registered User
    Join Date
    Sep 2014
    Posts
    51
    Quote Originally Posted by AndrewHunter View Post
    In order to change the values actually at temp, just like for root, you need a pointer to a pointer. Not just a pointer.
    Okay, I think I get it. temp is just a local variable whose actual values do not get modified. So, I'd have to pass the address of the exact location of the node in the heap. Right?

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Yep, take a look at this good pointer tutorial and linked list tutorial . You are on the right track. Also, you should define main the correct way . Additionally, your printList function does not change, nor should it, the contents of the list so a pointer to a pointer is not needed here, and you should adjust the definition to reflect the lack of intention of the function to change values, ie:
    Code:
    void printList(const Node *root)
    {
         //your adjusted code here
    }
    When you have made those changes repost your code and we can continue to develop from there. Don't get discouraged, you are making good progress.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reversal of a Doubly Linked List !
    By thebenman in forum C Programming
    Replies: 1
    Last Post: 03-10-2015, 08:14 AM
  2. Doubly Linked List
    By Nicholas Mata in forum C Programming
    Replies: 14
    Last Post: 05-16-2013, 07:03 AM
  3. doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 04-26-2007, 03:41 AM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Linked List nodes reversal
    By gkev in forum C++ Programming
    Replies: 3
    Last Post: 02-06-2003, 10:39 AM