?
Solved

how to print Reverse in single linklist

Posted on 2005-03-14
11
Medium Priority
?
536 Views
Last Modified: 2012-08-14
hello,
i am new to java especially in data structure.  I have a trouble with printReverse in single linklist.
Any algrithm it would help.
thanks
0
Comment
Question by:thayboi3000
  • 2
  • 2
  • 2
  • +4
11 Comments
 
LVL 1

Expert Comment

by:mkandre
ID: 13541854
Based on the accepted answer to a previous question a similar procedure is suggested

import java.util.*;

public class Tester
{
public static void main(String args[])
{
   List list = new LinkedList();
   list.addFirst(new Integer(25));
   list.addLast(new Integer(36));
   list.add(new Integer(75), 1); // the second argument 1 represents the index in the list to insert the new element
   
   // print in reverse
   for(int n=list.size()-1; n>=0; n--)
      System.out.print(n + ": " + list.get(n) + "\n");
}
}


mkandre
0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 13541882
Basically it is not possible to print the objects in reverse using SingleLinked List concept. because it is not possible to traverse from bottom to top.

So we need to save objects while traversing until the last object is reached and once it is completed, print those objects in reverse order.

Here is a sample idea which is not 100% perfect answer for you. but you get idea regarding how we can build linked lists

class MyObject
{
      MyObject next=null;
      Object o=null;
      public void add(Object o)
      {
            this.o=o;
            this.next=null;
      }

}
public class MyObjectTest
{
      public void printReverse(MyObject o)
      {
            Vector v=new Vector();
            while(o.next!=null)
            {
                  v.add(o.o);
                  o=o.next;
            }
            for(int i=v.size()-1;i>=0;i--)
            {
                  System.err.println(v.get(i));
            }
      }
      public void append(MyObject first,MyObject second)
      {
            first.next=second;
      }

      public MyObject moveLast(MyObject o)
      {
                  while(o.next.next!=null)
                  {
                        o=o.next;
                  }
                  return o.next;
      }
      public static void main(String s[])
      {
            MyObject o=new MyObject();
            o.add("Hello World");
            MyObject o1=new MyObject();
            o1.add("Hello World");
            append(o,o1);
            MyObject o2=moveLast(o);
            MyObject o3=new MyObject();
            o3.add("Hello World");
            o2.next=o3;
            printReverse(o);
      }
}
0
 
LVL 7

Expert Comment

by:lhankins
ID: 13541949
If the object implements the List interface (java.util.List), you can simply call Collections.reverse() on it.  For example :

   List myList = new List();
   
   myList.add("apple");
   myList.add("orange");
   // etc...

   Collections.reverse(myList);
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 9

Expert Comment

by:riaancornelius
ID: 13542009
the code by lhankins will reverse the original list though, so make sure you make a copy of your list if you want to keep the original order.
You can also just reverse the list again, but I would imagine that's a bit slower than making a copy.
0
 
LVL 1

Expert Comment

by:mkandre
ID: 13542769
As a previous comment said,

>> Basically it is not possible to print the objects in reverse using SingleLinked List concept. because it is not possible to traverse from bottom to top.

You will either have to copy the list to an array and read the array in reducing subscript, or traverse the list repetitively, going to one less node in the list each time, and retieve the data (which is not an efficient way of doing it).

Additionally you may create a second list and read the data from the first list (in natural order) and each time add that data to the front of the second list. Then the data in the second list will be the reverse of the first and can be read in natural order.

publuc class List
{
   Link head, tail;
   
   // constructor and other methods go here
   public List(){/*implement*/};
   public void append(){/*implement*/}
   public void prepend(){/*implement*/}
   public void printForward(){/*implement*/}
   
   public void printReverse()
   {
      List rev = new List();
      Link temp = head;
     
      // first add the data to the new list
      for(int n=0; n<size; n++, temp = temp.getNext())
         rev.prepend(temp.getData());
     
      // now you can print the rev list
      temp = rev.head;
      for(int n=0; n<size; n++, temp = temp.getNext())
         System.out.print (n + ": " + temp.getData() + "\n" ) ;
   }
}
0
 
LVL 21

Expert Comment

by:MogalManic
ID: 13543269
sudhakar_koundinya is right.  To reverse a singleLinked list, you need to get to the last item of the list 1st and then backtrack the saved objects.  This is EXACTLY what a stack does.  Using recursion, you can use the function call stack to save the objects as you traverse the list.  Here is the recursive implementation:

public void printList(SingleLinkedList list)
{
  printList(list.first());
}

private void printList(LinkedListNode node)
{
  if (node!=null) {
    printList(node.next());
    System.out.println(node.getValue());
  }
}

This assumes that the SingleLinkedList has a
  public LinkedListNode first()
method that returns the 1st item in the linked list and LinkedListNode has a Next() method which returns the NEXT item in the list.

The recursive method will traverse the LinkedList.  Each traversal pushes each node onto the Java call stack.  When it reaches the end, the node will be 'null'.  It will then start returning from the recursive calls and output the values in reverse order.
0
 
LVL 9

Expert Comment

by:riaancornelius
ID: 13543284
Are you implementing your own linkedList? If you are, the previous post is probably the most elegant solution. If not, let us know what linkedList you are referring to.
0
 
LVL 86

Accepted Solution

by:
CEHJ earned 750 total points
ID: 13543326
If you *have* implemented your own list, the simplest thing to do is probably to use the Stack class:


java.util.Stack stack = new java.util.Stack();
YourNodeClass n = <tail of your list>;
// Push list onto the stack
do {
      stack.push(n);
} while ((n = n.next) != null);

// Now print it in reverse
while (stack.empty() == false) {
      System.out.println(stack.pop()); // (Your node class should have a toString() implementation)
}
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13543963
Please refer to: http://www.experts-exchange.com/Programming/Programming_Languages/Java/Q_21349413.html

Actually, this question should not've been opened as discussions are still going on the same topic on that one. And yes, he is making his own linked-list.
0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 13545334
As per my belief, when we are working with our own linked lists. It is not a good Idea to use  predefined Collection objects. Otherwsie we don't get the logic idea of how these linked lists are working.

Best Regards
Sudhakar
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 13545780
:-)

>>t is not a good Idea to use  predefined Collection objects.

My answer was given as a convenient way, using the principle that recursion is to be avoided where possible. But FYI  thayboi3000 , you're not forced to award points to one commenter only
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Suggested Courses
Course of the Month9 days, 21 hours left to enroll

569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question