1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 11, 2012 #1

    s3a

    User Avatar

    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 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!
     
    Last edited by a moderator: Apr 5, 2012
  2. jcsd
  3. Mar 11, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    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:

    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.
     
    Last edited: Mar 12, 2012
  4. Apr 4, 2012 #3

    s3a

    User Avatar

    Thank you very much. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Reversing the order of nodes in a doubly linked list (Solution provided)
Loading...