?
Solved

how to print Reverse in single linklist

Posted on 2005-03-14
11
Medium Priority
?
528 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Industry Leaders: 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!

 
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

Independent Software Vendors: 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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses
Course of the Month7 days, 20 hours left to enroll

765 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