Reversing the order of nodes in a doubly linked list (Solution provided)

[s3a]

Homework Statement

Write an algorithm for reversing the order of nodes in a doubly 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. You may assume a header or trailer rather than head or tail, if you wish.

Homework Equations

How a (Doubly) Linked List works.

The Attempt at a Solution

The teacher gave this code:

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;
        trailer = header;
        header = trailer;
    }

[U]However, I believe it has flaws, so here is my version, please tell me if mine is 100% correct or not[/U]:
void reverse() {
        DNode cur = header.getNext();
        DNode tmp;

        while (cur != trailer) {
            tmp = cur.getNext();
            cur.setNext(cur.getPrev());
            cur.setPrev(tmp);

            cur = tmp;
        }

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

        tmp = trailer;
        trailer = header;
        header = tmp;
    }

Other question:
Also, what's the difference between a head and a header as well as a between a tail and a trailer? Or, are they the exact same thing?

Any input would be GREATLY appreciated!
Thanks in advance!

 

[rcgldr]

I believe it has flaws ...

looks like you solved the issue of using header.getNext() after having just modified it with header.setNext().

Also, what's the difference between a head and a header as well as a between a tail and a trailer?

I did a web search for link list header, and from this web site:

http://pages.cs.wisc.edu/~vernon/cs367/notes/4.LINKED-LIST.html

a header and a trailer are dummy nodes. An "empty" list would include two nodes, a dummy header node and a dummy trailer node. Considering the example code does not check for NULL after the statement DNode cur = header.getNext(), it's apparently using header and trailer dummy nodes.

head and tail are pointers to the first and last nodes of a list. head and tail pointers would normally be part of a list class as opposed to a node class. A list class could include other information such as the number of nodes on the list (for standard template library, this is list.size()). If a list is empty, then head == tail == NULL. If a list has one node, then head == tail == ptr to node, and node.prev() == node.next() == NULL. These conditions require special handling that having a header node and trailer node somewhat eliminate.

 

[s3a]

Thank you very much. :)