Results 1 to 8 of 8
  1. #1
    CirKuT is offline Member
    Join Date
    Sep 2008
    Posts
    53
    Rep Power
    0

    Default Revised Linked List printing method question

    Hello everyone,

    I posted yesterday regarding a problem with printing a linked list in backwards order. I have gotten a little farther but here is where I am stuck.

    I have a linked list (listA) that holds the following elements; A,B,C,D,E,F,G

    I then used this list to copy and create a second list like so

    Link listB = listA;

    So now I have two linked list objects that are the exact same just named different.

    So for listA I use this method to print in forward order

    public void Print(){
    if ( isEmpty() ){
    System.out.printf("Empty %s\n", name);
    return;
    }
    System.out.printf("The %s is: ", name);
    ListNode current = firstNode;

    while (current != null){
    System.out.printf("%s ",current.data);
    current = current.nextNode;
    }
    System.out.println("\n");
    }
    The output is A,B,C,D,E,F,G exactly what I want. Now for listB I want to just print backwards, So I modified the Print method above as this

    public void PrintBackwards(){
    if ( isEmpty() ){
    System.out.printf("Empty %s\n", name);
    return;
    }
    System.out.printf("The %s is: ", name);
    ListNode current = lastNode;

    while (current != null){
    System.out.printf("%s ",current.data);
    current = current.nextNode;
    }
    System.out.println("\n");
    }

    You can see all I did was change

    ListNode current = firstNode

    to this

    ListNode current = lastNode

    But the output is this

    G instead a G,F,E,D,C,B,A

    I know this has to do with this line of code in the printBackwards method
    current = current.nextNode;

    Im assuming it should something like
    current = current.previousNode, but I get an error,

    What do I need to do in order to print all the elements backwards rather than just the last element in the list??

    Thanks

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    You could add(not sure if this works/is allowed) the nodes/node names to an array and then easily print the array out backwards.

  3. #3
    CirKuT is offline Member
    Join Date
    Sep 2008
    Posts
    53
    Rep Power
    0

    Default

    Ya

    A few people told me to use an array but Im not allowed.

    My rules are this.

    Create a linked list with the following elements A,B,C,D,E,F,G

    then create a physical copy of thi linked list but with the elements in backwards order.

    Print both linked lists so list 1 prints forwards and list b prints backwards

  4. #4
    Sven is offline Member
    Join Date
    Dec 2008
    Location
    Enschede, Overijssel, the Netherlands
    Posts
    19
    Rep Power
    0

    Default

    First, for readability (use code tags!):

    Java Code:
    public void Print() {
        if ( isEmpty() ) {
            System.out.printf("Empty %s\n", name);
            return;
        } 
        System.out.printf("The %s is: ", name);
        ListNode current = firstNode;
    
        while (current != null) {
            System.out.printf("%s ",current.data);
            current = current.nextNode;
        }
        System.out.println("\n");
    }
    Modified version below:

    Java Code:
    public void PrintBackwards() {
        if ( isEmpty() ) {
            System.out.printf("Empty %s\n", name);
            return;
        } 
        System.out.printf("The %s is: ", name);
        ListNode current = lastNode;
        
        while (current != null) {
            System.out.printf("%s ",current.data);
            current = current.nextNode;
        }
        
        System.out.println("\n");
    }
    I still think the best solution for your problem is to modify your list so that it is a doubly-linked list, i.e. each node keeps a reference to it's predecessor as well as it's successor. That way, you can start at your last node and scan backwards through your list. Your list implementation is still a linked list!

    There is an easy alternative solution to your problem, because you're trying to reinvent the wheel here. Of course, I suppose this is for an assignment where you have to learn how linked lists work (which is good actually), so I will not give you the alternative (yet).
    Last edited by Sven; 12-11-2008 at 02:57 AM.

  5. #5
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    6

    Default

    If you don't use an array (actually, I don't see anything from your description that disallows this), then you are left with two options:
    (1) for printing backwards to be efficient, each ListNode needs to have a pointer to the previous node; I think from your post that you grasp this idea -- which is the bit that you're having trouble with in adding this variable to the ListNode class?
    (2) an inefficient way to solve the problem is to break it down: firstly, write a method to retrieve the nth item from the list, by starting at the beginning and skipping forward n links, then secondly call this method in a loop, pulling out item (length-1), item (length-2) etc down to 0.
    Method (2) is inefficient, because you end up having to traverse the list a lot, but is effectively your only option if you can't use arrays and you can't add a previousNode variable to the NodeList class.

  6. #6
    CirKuT is offline Member
    Join Date
    Sep 2008
    Posts
    53
    Rep Power
    0

    Default

    Ok,

    So I got a little farther. I understand the concept but am stuck on the last area. Here are my three classes for this app.

    package LinkedList;

    /**
    *
    * @author Morgan W. Leavitt
    */

    //Represents a single node in the list
    public class ListNode {

    //package access members: List can access these directly
    Object data;

    //Refers to the next node in the list
    ListNode nextNode;

    //Refers to the previous node in the list
    ListNode previousNode;

    //constructor to create a ListNode that refers to an object
    ListNode(Object object){
    this(object, null, null);
    }

    //constructor creates ListNode that refers to the Object, next, and previous
    //ListNode
    ListNode(Object object, ListNode node, ListNode prevNode){
    data = object;
    nextNode = node;
    previousNode = prevNode;
    }

    //return referecne to data in node
    Object getObject(){
    return data;
    }
    //return reference to the next node in the list
    ListNode getNext(){
    return nextNode;
    }
    //return referecne to previous node in the list
    ListNode previousNode(){
    return previousNode;
    }
    }

    package LinkedList;

    /**
    *
    * @author Morgan W. Leavitt
    */
    public class List {

    private ListNode firstNode;
    private ListNode lastNode;
    private String name;


    //constructs empty list with "list" as the name
    public List(){
    this ("list");
    }//end constructor

    //constructor creates an empty list with a name
    public List (String listName){
    name = listName;
    firstNode = lastNode = null;
    }//end constructor


    //Inserts an object at the front of the list
    public void insertAtFront(Object insertItem){

    //Inserts Item at the first node, what do I put for the previous node
    //parameter??????
    firstNode = new ListNode(insertItem, firstNode, null);
    }

    //output the two lists
    public void Print(){

    //begin at first node
    ListNode current = firstNode;

    //while not at the end of the list output the current nodes data
    //in forward order
    while (current != null){
    System.out.printf("%s ",current.data);
    current = current.nextNode;
    }
    System.out.println("\n");
    }

    //output the two lists backwards
    public void printBackwards(){

    //begin at last Node
    ListNode current = lastNode;

    //while not at the beginning of the list output the current
    //nodes data in backwards order
    while (current != null){
    System.out.printf("%s ",current.data);
    current = current.previousNode;
    }
    System.out.println("\n");
    }
    }


    package LinkedList;

    /**
    *
    * @author CirKuT
    */
    public class ListTest {


    public static void main (String args[]){


    //Creates a Linked List
    List listA = new List();

    listA.insertAtFront("J");
    listA.insertAtFront("F");
    listA.insertAtFront("E");
    listA.insertAtFront("D");
    listA.insertAtFront("C");
    listA.insertAtFront("B");
    listA.insertAtFront("A");

    //Prints listA from head to tail
    listA.Print();


    //Create a physcial copy of the first linked list but in backwards order
    //called ListB
    List listB = listA;
    listB.printBackwards();
    }

    }


    So my problem is obviously with the previousNode variable. In my printBackwards() method you can see that I modified it a bit from the printForward method to try and print backwards. My problem of course is the fact that the application does nit understand that the previousNode variable means to go back a node. How do I make this method?

  7. #7
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    6

    Default

    Well, when you add the item to the head of the list, there are two possibilities:
    - if this is the first item (i.e. the list is currently empty), then it's easy -- there's no "previous node" to set on anything (nor "next node");
    - otherwise, the item that is currently the first in list must have it's "previous node" point to the one that you're about to add.

  8. #8
    CirKuT is offline Member
    Join Date
    Sep 2008
    Posts
    53
    Rep Power
    0

    Default

    Correct, I understand the concept but the book I have does not get into linking previous links only next links. It doesnt actually talk about going backwards. My problem is mainly that I do not know how to write out the syntax. Im gonna keep trying though.

Similar Threads

  1. Replies: 9
    Last Post: 11-04-2011, 04:09 AM
  2. Linked List integer list
    By igniteflow in forum Advanced Java
    Replies: 1
    Last Post: 12-10-2008, 09:53 PM
  3. Linked List Question
    By CirKuT in forum New To Java
    Replies: 4
    Last Post: 12-10-2008, 07:56 PM
  4. Linked List help
    By neobie in forum New To Java
    Replies: 8
    Last Post: 12-22-2007, 04:15 AM
  5. Linked List
    By rnavarro9 in forum New To Java
    Replies: 0
    Last Post: 11-29-2007, 04:42 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •