how do i reverse a circular double linked list

This is a discussion on how do i reverse a circular double linked list within the C Programming forums, part of the General Programming Boards category; Hi everyone! I have a circular double linked list see http://www.openasthra.com/c-tidbits/...-or-tail-node/ for a description of circular double linked list. I ...

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    19

    how do i reverse a circular double linked list

    Hi everyone!
    I have a circular double linked list see
    http://www.openasthra.com/c-tidbits/...-or-tail-node/
    for a description of circular double linked list.
    I want to reverse the list with a function called
    void reverse(list_t** head ); or maybe void reverse(list_t** head, list_t* last);
    where head is the first element and last is the last element.
    My first implementation was to start from last element until i reach the first element and put those element in a new double linked list until. (every element is inserted last in the list)
    However i changed the requirement for me and i do not want to have a new list to move element on it.
    I want to use same list but i always succeed to loose reference to some element.
    Therefore i hope that some of you can help me with that and i appreciate if somebody can help me with this ( it is enough with a pseudo code description)
    To make it shorter i want to use same list and reverse it without using a temporary linked list
    Thanks for all help

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Just move backwards in the list.

    Forward: ele = ele->next;
    Backwards: ele = ele->previous;

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm with Thantos: if it's a circular doubly-linked list, how could you tell it was reversed?

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by tabstop View Post
    I'm with Thantos: if it's a circular doubly-linked list, how could you tell it was reversed?
    Iteration in the "forward" direction would traverse the elements in the opposite order as before.

    Anyway, to reverse a circular list, just step through every element and swap the "prev" and "next" pointers.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    If it's circular, and doubly linked, then how different will it really look after you've reversed it?
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by Salem View Post
    If it's circular, and doubly linked, then how different will it really look after you've reversed it?
    I don't see why it's such a weird request. Maybe some piece of code is set up to always traverse in the "forward" direction by following the "next" pointers, and you want to traverse the opposite direction, and you don't want to change the other piece of code.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I don't think it is weird and there are some very practical applications for reversing directions (I.E. changing motor direction). The problem becomes that going through each element and swapping the pointers is rather expensive compared to changing the direction you transverse.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    That's my whole point. A circular double linked list means it's already set up to start at any point and traverse in either direction.

    Even if it is a student exercise, it's a pretty dumb one since it's not something you'd ever do in real life.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by Salem View Post
    That's my whole point. A circular double linked list means it's already set up to start at any point and traverse in either direction.

    Even if it is a student exercise, it's a pretty dumb one since it's not something you'd ever do in real life.
    How easy it is to make a sweeping generalization. Have you never worked with code that is out of your control or cannot be changed for some reason?


    As far as student exercises comparing with real life. Real life wins hands down, in terms of absolute stupidity I've dealt with. School was not even close. School was nice.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    How easy it is to make a sweeping generalization. Have you never worked with code that is out of your control or cannot be changed for some reason?


    As far as student exercises comparing with real life. Real life wins hands down, in terms of absolute stupidity I've dealt with. School was not even close. School was nice.
    Yeah, almost everything you do at school is easily solvable in a few hundred or thousand lines of code. Not so in real life. And in School, you are almost always in control of ALL the code in the application. In real life that's rarely the case - often the majority of the code is either written by someone else, or belongs to say the OS that you can't modify at all.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jul 2006
    Posts
    19

    hi

    The reason why i asked this question is that i wanted to refresh my knowledge in c. I know the difference beetween the school and industri since i have both studied before and worked since 2,5 years ago. However i have been working with java and ui-application until now and from may i will change profile to hardware/device driver and before i starting the new job i only want to repeat and refresh my not so advanced knowledge in c.
    However i want to thanks people who helps and i also want to give an advice to people who does not have a meaningful life/job and need to give a comment on every thread. Get a life

  12. #12
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    To actually answer the original question, you might do something like this:

    Code:
    void reverse_list(node *head)
    {
        node *curr, *next, *tmp;
        curr = head;
        do
        {
            next = curr->next;
            tmp = curr->prev;
            curr->prev = curr->next;
            curr->next = tmp;
            curr = next;
        } while(curr != head);
    }

  13. #13
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    of course if you do
    Code:
    void reverse_list(node *head)
    {
        node *curr, *tmp;
        curr = head;
        do
        {
            tmp = curr->next;
            curr->next = curr->prev;
            curr->prev = tmp;
            curr = tmp;
        } while(curr != head);
    }
    You save yourself an assignment. If the list is large it might be worth it

    I would still suggest finding a better way if at all possible.

  14. #14
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by Thantos View Post
    You save yourself an assignment. If the list is large it might be worth it
    The compiler's data flow analysis will probably figure that out anyway.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21