# Homework Help: Reversing the order of nodes in a doubly linked list (Solution provided)

1. Mar 11, 2012

### s3a

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
How a (Doubly) Linked List works.

3. The attempt at a solution
The teacher gave this code:
Code (Text):

public void reverse() {

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
}

[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 tmp;

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

cur = tmp;
}

tmp = trailer.getPrev();

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

Last edited by a moderator: Apr 5, 2012
2. Mar 11, 2012

### rcgldr

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

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

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.

Last edited: Mar 12, 2012
3. Apr 4, 2012

### s3a

Thank you very much. :)