Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   reversing doublely linked list (http://www.programmingforums.org/showthread.php?t=13304)

mrynit Jun 8th, 2007 6:53 AM
reversing doublely linked list
 
To reverse the list i need to "flip" the prev next "pointers" for each node and moving the head pointer. i keep doing this until the head pointer is null. the code i have is half give half done by me. the method to reverse reversedList was give. i dont understand what/how the dot notation is doing inside the for loop. I dont have to worry about proper OOP on this one so im guessing that has to do some thing with it.

:
public class TestDLLNode
{
        static DLLNode head, curr, prev, next, trail = null;
       
        public static void main(String[] args)
        {
                //make first node. value with no connections
                curr = new DLLNode("one");
                prev =curr;
                head = curr;
               
                //creat a new node with the value of "two" and stroes it in curr
                //no connections made yet
                //overwrite curr("one") to new object curr("two")
                curr = new DLLNode("two");
               
                //establish the link to prev, connecting two to one
                //set the previous _pointer_ of the current node ("two") to point to the
                //previous node object ("one")
                //(current_obj).setPrevious((last_node_obj));
                //curr here means ("two")
                //prev here means ("one")
                curr.setPrevious(prev);
               
                //link "one" to  "two"
                //prev here means ("one")
                //curr here means ("two")
                prev.setNext(curr);
               
                //copy curr node to prev nod b/c will become the new node
                //prev will hold the "old" node for the next round of assigning
                prev = curr;
               
                /* **third***/
                curr = new DLLNode("three");
                curr.setPrevious(prev);
                prev.setNext(curr);
                prev = curr;
               
                //print list
                printList(head);
               
                //print list
                printList(reversedList(head));               
               
        }//end main
       
        public static void printList(DLLNode head)
        {
                System.out.print("[");
                while(head != null)
                {
                        System.out.print(head.getValue() + " " );
                        head = head.getNext();
                }
                System.out.print("]\n");
        }

        public static DLLNode reversedList(DLLNode head)
        {               
                curr = head;
                prev = null;
               
                while(curr != null)
                {
                        next = curr.next;
                        curr.next = prev;
                        curr.prev = next;
                        prev = curr;
                        curr = next;
                }
                return prev;
        }
}//end class

:
public class DLLNode
{
        private String nodeValue;
        public DLLNode prev;
        public DLLNode next;
       
        public DLLNode(String item)
        {
                nodeValue = item;
                this.prev = null;
                this.next = null;
        }
       
        public void setPrevious(DLLNode prev)
        {
                this.prev = prev;
        }
       
        public void setNext(DLLNode next)
        {
                this.next = next;
        }
       
        public String getValue()
        {
                return nodeValue;
        }
       
        public DLLNode getNext()
        {
                return next;
        }
       
        public DLLNode getPrev()
        {
                return prev;
        }
}

mrynit Jun 11th, 2007 8:05 PM
i figured out how to reverse it myself. i rewrote the method.
:
public static DLLNode reversedList(DLLNode head)
        {               
                DLLNode curr = head;
                DLLNode prev = null;
               
                while(curr != null)
                {                       
                        curr.setPrevious(curr.getNext());
                        curr.setNext(prev);
                        prev = curr;
                        curr = curr.getPrev();
                }
                return prev;
        }

now i need to make it into a recursive function. im not sure how to do this. when the method calls it self it will be passing curr to the next method. but when the recursion stops when the next curr is null what will be pasted back to the other called methods? I dont know how sort out the recursion.

mrynit Jun 11th, 2007 9:50 PM
well i figured it out all by myself. it took about two hours but I understand how to approach problems better now. instead of getting frustrated and asking and waiting for help i got out the old paper and pen and started drawing pictures showing what was happening. so here it is.
:
public class TestDLLNode2
{
        public static void main(String[] args)
        {
                //make first node. value with no connections
                DLLNode curr = new DLLNode("num_1");
                DLLNode prev =curr;
                DLLNode head = curr;
               
                //make all other nodes
                for(int i = 2; i <= 6; i++)
                {       
                        curr = new DLLNode("num_" + i);
                        curr.setPrevious(prev);
                        prev.setNext(curr);
                        prev = curr;
                }
               
                //print list
                printList(head);
               
                //reverse list
                DLLNode reversdHead = reversedListRecursive(head);
               
                //print list
                printList(reversdHead);               
               
        }//end main
       
        public static void printList(DLLNode head)
        {
                System.out.print("[");
                while(head != null)
                {
                        System.out.print(head.getValue() + " " );
                        head = head.getNext();
                }
                System.out.print("]\n");
        }

        public static DLLNode reversedListRecursive(DLLNode curr)
        {               
                DLLNode tmpPrev = curr.getPrev();
                curr.setPrevious(curr.getNext());
                curr.setNext(tmpPrev);
                if (curr.getPrev() == null)
                        return curr;
                curr = curr.getPrev();
                return reversedListRecursive(curr);
        }
}//end class

The Dark Jun 11th, 2007 10:12 PM
Good work, mrynit and good job posting the result for the next person.


All times are GMT -5. The time now is 2:29 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC