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

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

Quote:

---

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

Hmm - perhaps you don't count your size correctly? E.g. push_front() doesn't increment it, perhaps?

--
Mats

is size() calculated through iteration every time it's called? Or is it just a small inline-returner?

Quote:

---

Originally Posted by twomers

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

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?

Quote:

---

Originally Posted by twomers

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

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);
}

---

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.

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

once again, thanx all!