Question

Is the end of this algorithm correct?

Answer 1

(Check my uppercase comments at the bottom. If I am right please confirm because I am weak in this stuff and it would help a lot to know if I am right and not just if I am wrong.)

public void reverse(){
DNode cur = header.getNext();
DNode tmp;
while (cur != trailer){
// swap the next and prev referneces
tmp = cur.getNext();
cur.setNext(cur.getPrev());
cur.setPrev(tmp);
// advance to the next node in the sequence
cur = tmp;
}
// swap the references of header.next and trailer.prev
header.setNext(trailer.getPrev());
trailer.setPrev(header.getNext());
tmp = header; // SHOULDN'T THIS BE tmp = trailer; ?
trailer = header;
header = trailer; // SHOULDN'T THIS BE header = tmp; ?
}

Answer 2

I forgot to add the question :P.

Here it is (Question #5 - not #4):

4.
Using pseudocode or Java (or a mix), write an algorithm for reversing the order of nodes in
a singly linked list. You may assume a head and tail reference, and you may directly get
and set the next field of any node, but you may not assume any add or remove methods are
defined.
5.
Write an algorithm for reversing the order of nodes in a doubly linked list. The same instruc-
tions as in Question 4 apply, except that you may assume a header or trailer rather than
head or tail, if you wish.

(Also, what is the difference between header and trailer compared to head and tail - is it just a different way of saying the same thing?)

Answer 3

I believe your comments are correct.
When you swap you want to do the following:
first = tmp
first = second
second = tmp

Answer 4

Oh, and I looks like the header and tailer are just variable names. They are no different than head and tail in this case.

Answer 5

Thank you very much! It also feels great that I was right :)

Answer 6

Also, can you confirm if I am right for the following because I think that:

header.setNext(trailer.getPrev());
trailer.setPrev(header.getNext());

should be

tmp = header.getNext();
header.setNext(trailer.getPrev());
trailer.setPrev(tmp);

(for the stuff above the stuff I initially commented on with uppercase comments).