Thread: list reversal question

  1. #1
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127

    list reversal question

    My current reverse() for my doubly-linked list looks like this:
    Code:
    template <typename T> void
    List<T>::reverse(){
        
        if(!empty()){
        
            for(List<int>::Iterator i = begin(); i != end(); i++){
            
                push_front(*i);
            }
        
            for(int j = 0; j < size(); j++){
            
                pop_back();
            }
            
          
        }
    }
    At first glance it seems fine, but after a bit of testing I ran into this particularity:

    It doesn't swap the head and tail pointers. This causes a bit of confusion when you look-up a value or return a specific position.

    So SHOULD I swap head and tail or not?

    (head ^ tail) v (!head ^ !tail) << my awful discrete math class...

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Surely that code won't work - it removes "size()" number of elements, which would be the total number of elements in your list.

    Not sure on the head/tail, but yes, I think you should swap those.

    --
    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.

  3. #3
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    Surely that code won't work - it removes "size()" number of elements, which would be the total number of elements in your list.

    funny you should say that, i've looked at it before and thought the same thing. it does work however. No no seriously, it does, even though I'm not sure why

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Hmm - perhaps you don't count your size correctly? E.g. push_front() doesn't increment it, perhaps?

    --
    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.

  5. #5
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    is size() calculated through iteration every time it's called? Or is it just a small inline-returner?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by twomers View Post
    is size() calculated through iteration every time it's called? Or is it just a small inline-returner?
    Ah, yes, of course, if it's calculated each time by counting the number of elements, then it would work, because j == size() when you have removed half the list. But it terribly time-wasiting to count every element each time you do that - imagine you have 1000 elements in the list, it will count more than a million elements by the time you are back to 1000 elements after adding them in reverse order.

    --
    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.

  7. #7
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    Well when reversing what you're doing is putting heads where heels go and heels where heads go... so why not swap. You have a move function? You could simply move each element to the end for size() .
    Why do you need to reverse it? Can't you just begin at end() and reverse-iterate to the start of the list?

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by twomers View Post
    Well when reversing what you're doing is putting heads where heels go and heels where heads go... so why not swap. You have a move function? You could simply move each element to the end for size() .
    Why do you need to reverse it? Can't you just begin at end() and reverse-iterate to the start of the list?
    Yeah, that makes sense to me.

    --
    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.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you think that the reverse function makes sense, then surely you would do this by swapping pointers in the nodes, and not pushing and popping data (which is more expensive). Just traverse the list and swap each nodes next and previous pointer. And finally swap pointers pointing to head and tail.

    [Edit]
    It is actually pretty cool to advance using the prev pointer (never implemented a doubly linked list before):
    Code:
    void List::reverse()
    {
        Node* it = head;
        while (it) {
            std::swap(it->next, it->prev);
            it = it->prev;
        }
        std::swap(head, tail);
    }
    Last edited by anon; 10-17-2007 at 04:27 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    I've been trying to follow the STL List. It has a reverse function. So I guess the easier way is to just swap head and tail.

    I do have iterators rbegin and rend (like STL List).


    Yea, size() was NOT private list data. It was caluclated each time, guess it's better to do something like:

    Code:
    class List{
    private:
    int size;
    ...
    };
    and just increment and decrement size in my pop/push/insert/remove functions.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, using an internal size to keep track of the size is much better - just make sure you count it right at all times!!!

    --
    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.

  12. #12
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    once again, thanx all!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  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. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM