Results 1 to 13 of 13
  1. #1
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Question I need Help Using an "AddSorted" method to a Doubly Linked List

    The program reads in a file using the end-line character as a delimiter. The file is assumed to already be sorted. For example:

    Alpha
    Bravo
    Delta

    is read in from alphabet.txt.

    You are supposed to have a doubly linked list that adds a node for each line read-in. Then, you have a method, "addSorted," that asks the user if he or she would like to add another node. They type in what they want to add. Ex: "Charlie".

    Then the addSorted changes the list and outputs in alphabetical order:

    Alpha
    Bravo
    Charlie
    Delta

    and writes to file accordingly.

    I have my code working up until actually having "addSorted" work. I'll post my code here. I'm not going to try to sound like an idiot and speculate as to why my program won't work, because I don't know. I have stated what it's supposed to do and I will post my code. (Do not post condescending remarks, if you are not going to help, don't bother the effort.)

    The addSorted Method is in the DList class--thus, it's where the problem is.

    • Note: It doesn't have any way to add the node yet. I had "test" outputs in the if-statements, and it does not work properly. It says that "Charlie" should come before term 2 /and/ after term 2. I would like any advice, including any pseudo-code that my code should resemble to ultimately serve the purpose of adding a node in such a way that it remains sorted in the list.


    http://www.aswiftlytiltingplanet.net/DLIST.pdf
    http://www.aswiftlytiltingplanet.net/DNODE.pdf
    http://www.aswiftlytiltingplanet.net/DRIVER.pdf

    Those should be all you need to get the program working on your own.

    I will appreciate any help and advice I can get.

    Thank you,
    Aux
    Last edited by Auxilium; 10-09-2010 at 10:20 PM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default

    Do you have any specific questions about writing a java program?
    What are you expecting here? We'll help you fix your code if you post it and ask questions about it. If you're too sensitive for the comments you could get, I'm sorry.

    When you post code, be sure to enclose it in code tags. Info here: http://www.java-forums.org/misc.php?do=bbcode#code

  3. #3
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Default

    Quote Originally Posted by Norm View Post
    Do you have any specific questions about writing a java program?
    What are you expecting here? We'll help you fix your code if you post it and ask questions about it. If you're too sensitive for the comments you could get, I'm sorry.

    When you post code, be sure to enclose it in code tags. Info here: Java Forums - BB Code List
    I'm asking how to add a node (with the element being a String) to a doubly linked list in such a way that the list remains sorted in lexicographical order; sorry for not being clearer.

    I'm expecting pseudo code.

    I did post my code. The code is so long that I did potential helpers a favor and uploaded pdf files of the code rather than "spam" the board.

    I'm not a sensitive person by any means (unless you're a friend, then I am a sensitive caring person. :o ).
    Last edited by Auxilium; 10-09-2010 at 10:28 PM.

  4. #4
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Arrow

    So, I want this block of code to add a node to a doubly linked list in such a way that the list remains sorted in lexicographical order. Possibly using methods addBefore and addAfter. I don't even know where to begin. How do I run through a doubly linked list and determine where the node belongs? I think I would use compareTo, but when I try to, I can't seem to get it to output what I want to see in my "test" outputs.

    Java Code:
     
        /**Adds a node to the list in such a way that it remains sorted.*/
        public void addSorted(DNode v)
    {
           DNode temp = v;
           int tempSize = this.size + 1;
           String test = temp.element;
           DNode h = this.header;
           DNode first = this.header.getNext();
           DNode next = first.getNext();
           DNode next2 = next.getNext();
           DNode t = this.trailer;
           DNode last = this.trailer.getPrev();
           int location = 0;
           
           for (int a = 0; a < tempSize - 2; a++)
           {
                 if(this.size > 0 && first.element.compareTo(test) < 0)
                        {
                           System.out.println("Comes after term 1\n"); //Test output.
                           location = 1;
                        }
                if(this.size > 0 && next.element.compareTo(test) > 0)
                       {
                          System.out.println("Comes before term 2\n"); //Test output.
                          location = 1;
                       }
               if(this.size > 0 && next.element.compareTo(test) < 0)
                      {
                         System.out.println("Comes after term 2\n"); //Test output.
                         location = 2;
                      }
               if(this.size > 0 && next.element.compareTo(test) < 0)
                   {
                         next = next.getNext();
                      
                         if(this.size > 0 && next.element.compareTo(test) < 0)
                            {
                               System.out.println("Comes after term 3\n"); //Test output.
                               location = 3;
                            }
                  }
                 if(this.size > 0 && next.element.compareTo(test) < 0)
                 {
                     next = next.getNext();
                     if(this.size > 0 && next.element.compareTo(test) > 0)
                     {
                       System.out.println("Comes before term 3\n"); //Test output.
                       location = 2;
                     }
                }
        }
    }
    Last edited by Auxilium; 10-09-2010 at 10:35 PM. Reason: Aesthetics.

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default

    What is your design for inserting a node into a doubly linked list?
    Three cases: at the beginning, in the middle, at the end.

    Please change your code to have only one statement per line.
    What you've posted is too dense to read easily.

    Also don't put any code on the same line following a {
    or before a }
    The { and } should be easy to see.
    Last edited by Norm; 10-09-2010 at 10:27 PM.

  6. #6
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Default

    Design for inserting a node: at the beginning.
    It will search through and finds where the node belongs in alphabetical order based off of the String elements of the nodes.

    Changes made.

    I can post the sorting algorithm from my book if you would like, though it's for sorting a list--not inserting a node after finding where the node belongs in the list.

    Java Code:
    /**Insertion-sort for a doubly linked list of class DList L */
    public static void sort(DList L)
    {
        if(L.size <= 1)
           return;
        DNode pivot, ins;
        DNode end = L.getFirst();
        while(end != L.getLast())
        pivot = end.getNext();
        L.remove(pivot);
        ins = end;
        while(L.hasPrev(ins) && ins.getElement().compareTo(pivot.getElement()) > 0)
            ins = ins.getPrev();
        L.addAfter(ins, pivot);
        if(ins == end)
           end = end.getNext();
      }
    }
    Last edited by Auxilium; 10-09-2010 at 10:42 PM.

  7. #7
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default

    Your code is much easier to read now.

    You design needs a lot more details.
    Talk about getting the link to the first node, comparing the node's value, about getting the link to the next node.
    When the place to insert is found, describe how the links will be copied to chain in the new node.

  8. #8
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Default

    Quote Originally Posted by Norm View Post
    Your code is much easier to read now.

    You design needs a lot more details.
    Talk about getting the link to the first node, comparing the node's value, about getting the link to the next node.
    When the place to insert is found, describe how the links will be copied to chain in the new node.
    Thank you, alright.
    Java Code:
    //With...
     public void addSorted(DNode nodeToAdd)
    DNode temp = nodeToAdd;
    
    //To get the first node, I would say..
    DNode first = this.getFirst(); (that would work with my code)
    DNode next = first.getNext();
    String x = first.getElement(); //For possible use in a loop later.
    String y = next.getElement(); // Same as above line.
    
    //To compare the first node with the node to be inserted lexicographically, I would say...
    if(first.getElement().compareTo(temp.getElement()) < 0)
    {
    	this.addBefore(first, temp); //Comes before lexicographically. Adds the node before that one.
    }
    else if(first.getElement().compareTo(temp.getElement()) > 0)
    {
    	this.addAfter(first, temp); //Comes after lexicographically. Adds the node after that one..
    }
    • Where I'm stuck is I don't know how to go from comparing the first node to comparing the next node. I figure I would need a loop. I just can't seem to get a loop working properly, let alone my test outputs (they don't even work when comparing the first two nodes with the node to be inserted).
    • Secondly, even if the element came after the first term lexicographically, I wouldn't know how to add it where it really belongs (lets say it was supposed to be after the node next to the first node, I wouldn't know how to get the program to add it after that node rather than just after the first node).


    If A is the first node and B is the second node and C is the node to be inserted...
    A B D //Between B and D
    ....^C

    Rather than //Between A and B
    A B D
    ..^C

    For example, how my program is right now, it says that C should come after B but also come before B (because it comes after A lexicographically). Both are true technically, just not what I'm trying to do. How would I eliminate coming before B if after B is true?
    Last edited by Auxilium; 10-09-2010 at 11:06 PM.

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default

    Don't write code until you've got a design.
    I don't know how to go from comparing the first node to comparing the next node
    You use a "current node" pointer that starts at the top/first node and then is changed to the next node pointer to move thru the list. Keep going until the node to be inserted's value is less than the node at the 'current node' pointer.
    I wouldn't know how to add it where it really belongs
    The nodes have two pointer each. You need to change these so that the new node is where it belongs in the chain. Take a piece of paper and make a diagram of a short doubly linked list with pointers going to next and last nodes. Draw a node beside and between two nodes in the list and see how you have to change the node pointers so that the new node is logically chained in the list.

  10. #10
    asmodean is offline Member
    Join Date
    Jul 2010
    Posts
    18
    Rep Power
    0

    Default

    Hey OP,

    I think I'm in your class.

    I'm having problems with the addsorted method as well. Mainly I can't get it to insert the last Node.

    We have three (or four) cases that the algorithm has to work with.

    1. the list is empty. In that case you just add the node to be added to the list after the header.

    2. there is one node besides the header and trailer. In that case you would just compare the new node's data to the one already in the list inserting the new node before or after the one already there according to whether its value is larger or smaller than the node already there.

    3. you have more than one node in the list besides the header and trailer and you need to traverse the list until you get to the point where you need to insert the new node.

    One problem you may have is with the last case is traversing too far and hitting the trailer. There's a simple answer to that problem though.

  11. #11
    asmodean is offline Member
    Join Date
    Jul 2010
    Posts
    18
    Rep Power
    0

    Default

    My only problem is mine seems to sort everything as it goes except for the last node (or string in the file).

    Like if my file is: Alpha, Bravo, Delta, Charlie

    The output is: Alpha, Bravo, Delta


    But if my file is: Alpha, Bravo, Delta, Charlie, Omega

    My output is: Alpha, Bravo, Charlie, Delta

    So it seems to be just ignoring the last line in the file. . . I seem to have that problem a lot. . .

  12. #12
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Default

    asmodian,

    That'll be really interesting if we're in the same class. Hopefully the program hasn't been too hard for you so far. If you want, I can help you with your code (in terms of giving advice). If it sorts everything except for the last node, maybe if you change the loop to end at the trailer it would work? Or while this.getNext.getElement() != null?

    Here's the output:
    Java Code:
    Enter the name of the text file to be read.
    If it's not in the same folder, be sure to specify it's location: alphabet.txt
    ‘™ÝAlpha
    // Line #: 1
    Bravo
    // Line #: 2
    Delta
    // Line #: 3
    Would you like to add another node? Please enter a word: 
    Charlie
    *********************
    File Sorting:
    *********************
    
    Node added after first node. Node: ‘™ÝAlpha
    Node added after the last node. Node: Charlie
    Node added before the cursor. Node: Bravo
    Node added after the cursor. Node: Delta
    (I have a toString executed at the end to show the list again, but the loop doesn't end to show that?)

    and here's the code if anyone has advice. I'm this close to getting it working. I'm perplexed on how to get it to stick to one solution rather than saying all four of those scenarios are true. I just need to think it through more.

    Java Code:
    /**Adds a node to the list in such a way that it remains sorted.*/
        public void addSorted(DNode v)
        {
            DNode check = v;
            DNode first = this.getFirst();
            DNode next = first.getNext();
            DNode end = this.getFirst();
            String element;
            
            System.out.println("*********************\nFile Sorting:\n*********************\n");
            //If the list only contains the header and trailer.
            if(this.size == 0)
            {
              System.out.println("List size equals 0.");
              return;
            }
            //If the list contains 1 node besides the header and trailer.
            if(this.size == 1)
            {
                if(first.getElement().compareToIgnoreCase(check.getElement()) < 0)
                {
                    //Point the head to check. Point check back to the head and to first. Point first back to check.
                    this.header.setNext(check);
                    check.setPrev(this.header);
                    check.setNext(first);
                    first.setPrev(check);
                    this.size++;
                    System.out.println("Node added after header.");
                }
                else if(first.getElement().compareToIgnoreCase(check.getElement()) > 0)
                {
                    //Point first to check. Point check back to first and to next node. Point the next node back to check.
                    first.setNext(check);
                    check.setPrev(first);
                    check.setNext(next);
                    next.setPrev(check);
                    this.size++;
                    System.out.println("Node added after first node.");
                }
            }
            //If the list contains more than 1 node besides the header and trailer.
            if(this.size > 1)
            {
                //Checks to see if the node added fits between the header and first node or the first and second node.
                element = first.getElement();
                if(element.compareTo(check.getElement()) < 0)
                {
                    //Add the node before the first node.
                    this.header.setNext(check);
                    check.setPrev(this.header);
                    check.setNext(first);
                    first.setPrev(check);
                    this.size++;
                    System.out.println("Node added after header.");
                }
                  else if(first.getElement().compareToIgnoreCase(check.getElement()) > 0)
                {
                    //Point first to check. Point check back to first and to next node. Point the next node back to check.
                    first.setNext(check);
                    check.setPrev(first);
                    check.setNext(next);
                    next.setPrev(check);
                    this.size++;
                    System.out.println("Node added after first node.");
                }
                //Checks to see if the node added fits between the last node and the trailer or after the second-to-last node and the last node.
                element = this.getLast().getElement();
                if(element.compareTo(check.getElement()) < 0)
                {
                    //Add before the last node.
                    this.getLast().getPrev().setNext(check);
                    this.getLast().setPrev(check);
                    check.setPrev(this.getLast().getPrev());
                    check.setNext(this.getLast());
                    this.size++;
                    System.out.println("Node added before the last node.");
                }
                else if(element.compareTo(check.getElement()) > 0)
                {
                    //Add after the last node.
                    this.getLast().setNext(check);
                    this.trailer.setPrev(check);
                    check.setPrev(this.getLast());
                    check.setNext(this.trailer);
                    this.size++;
                    System.out.println("Node added after the last node.");
                }
                
                //Loops through the nodes for other scenarios.
                while(end != this.trailer)
                {
                    element = next.getElement(); //Sets a string equal to the element of the node "next"
                    if(element.compareTo(check.getElement()) < 0)
                    {
                        //When the node added comes before the cursor.
                        next.setPrev(check);
                        next.getPrev().setNext(check);
                        check.setPrev(next.getPrev());
                        check.setNext(next);
                        this.size++;
                        System.out.println("Node added before the cursor.");
                    }
                    //When the node added comes after the cursor.
                    else if(element.compareTo(check.getElement()) > 0)
                    {
                        next.setNext(check);
                        next.getNext().setPrev(check);
                        check.setPrev(next);
                        check.setNext(next.getNext());
                        this.size++;
                        System.out.println("Node added after the cursor.");
                    }
                //if(next.getNext() != null)
                //{
                    next = next.getNext();
                //}
                end = next;
            
                }
            }
         }
    I'm starting to think that I could even compare unicode values to solve my problem, but there has to be an easier way just to do it with compareTo.
    Last edited by Auxilium; 10-10-2010 at 06:39 PM. Reason: More detail.

  13. #13
    Auxilium's Avatar
    Auxilium is offline Member
    Join Date
    Oct 2010
    Posts
    7
    Rep Power
    0

    Thumbs up

    Good news everyone, thank you for your help. I got the program working.

    Instead of traversing the list from start to trailer, I reversed it. I searched from last node to header. That fixed the problem because the first time you get a "match" (finding where the word belongs) with the alphabet going backwards, it'll be the right place. Going start to finish the computer thinks the first match is the right one.

    I also switched the < > symbols with compareTo and it somehow works. I thought that was odd because I think it contradicted all the online tutorials on compareTo I have read.

    Now I just need to save the new list to the file. :o
    Last edited by Auxilium; 10-10-2010 at 11:19 PM.

Similar Threads

  1. Doubly Linked List
    By matin1234 in forum New To Java
    Replies: 0
    Last Post: 06-02-2010, 05:58 AM
  2. problem with argument list and precedence "(" and ")"
    By helpisontheway in forum Advanced Java
    Replies: 6
    Last Post: 12-24-2009, 07:50 AM
  3. doubly linked list insert
    By ineedhelpwithjava in forum Advanced Java
    Replies: 1
    Last Post: 03-20-2009, 02:05 PM
  4. Help with Doubly linked list
    By Dr Gonzo in forum New To Java
    Replies: 5
    Last Post: 12-06-2008, 07:45 AM
  5. Doubly-linked list with data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:30 PM

Posting Permissions

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