Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 50

Thread: Sort and Merge Two Linked List

  1. #1
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Sort and Merge Two Linked List

    I am looking for help with a homework assignment that requires us to merge two linked list (integer type) and create a third list that is sorted without destroying the original list. I have created the code to get my first two linked list to display, and have the start of my merger method, but have hit a wall probably because of over thinking. I was hoping there was some easy way to append one linked list to another, but have had no such luck attempting this. A note on any assistance provided, please avoid using structs and pointers as we haven't really gotten into those yet and i don't feel at all confident with using them here especially since I'm still trying to figure out this whole linked list idea. Thank you in advance, and please try and edit my own code so it is easier for me to follow. Thanks.


    package hw3_vinson;
    import javax.xml.*;
     
    public class HW3_Vinson 
    {   
        public static void main(String[] args) 
        {
            //Linked list one holding integers
          HW3_Vinson LL1 = new HW3_Vinson();
          LL1.add(1);
          LL1.add(3);
          LL1.add(2);
     
           //Linked list two holding integers
          HW3_Vinson LL2 = new HW3_Vinson();
          LL2.add(4);
          LL2.add(8);
          LL2.add(5);
     
          //Will hold combination of LL1 and LL2
          HW3_Vinson LL3 = new HW3_Vinson();
     
          //Print each list
         LL1.print();
         LL2.print();
         LL3.print();
        }
     
        //Node Class creation
    private class Node
    {
        int element;
        Node next;
     
        Node(int el, Node n)
        {
            element = el;
            next = n;
        }
     
        Node(int el)
        {
            this(el, null);
        } 
    }
     
    //Set up nodes to store first and last element
    private Node firstElement;
    private Node lastElement;
     
    //Constructor for class
    public HW3_Vinson()
    {
        firstElement = null;
        lastElement = null;
    }
     
    //check to see if list is empty, return null if true
    public boolean isEmpty()
    {
        return firstElement == null;
    }
     
    //add to end of list
    public void add(int e)
    {
        if (isEmpty())
        {
            firstElement = new Node(e);
            lastElement = firstElement;
        }
        else
        {
            lastElement.next = new Node(e);
            lastElement = lastElement.next;
        }
    }
     
     
    //Combine two linked list and return a new linked list NOTE: This code does not work, and I know that I can't
    //use the .add method because it is for adding integers to a linked list.  I had tried to create another addList method
    //but got no where with it.
    /*
    public Node mergeList(Node L1, Node L2)
    {
        Node LL1 = L1;
        Node LL2 = L2;
        Node LL3 = null;
     
        while (LL1 != null)
        {
            LL3.add(LL1);
        }
     
        while (LL2 != null)
        {
            LL3.add(LL2);
        }
     
        return LL3;
    }
    */
    //Print out linked list
    public void print()
    {
        Node ref = firstElement;
        while (ref != null)
        {
            System.out.println(ref.element + " ");
            ref = ref.next;
        }
    }
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    easy way to append one linked list to another
    Set the next pointer at the end of one linked list to the first node in the other linked list.


    please avoid using structs and pointers
    That will be easy. There are none in java.


    The posted code has compiler errors. Do you get compiler errors?
    Please copy and paste the full text of any error messages here.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    I did know there was a compile error, it was on my mergeList method I was tampering with. I have edited the above code and commented it out, should compile now. I was using NetBeans IDE, so you may have to save the file with the name HW3_Vinson before it will run.

    Also in regards to your answer about appending the two list. How would I go about and specify the next pointer from one list to the first node of the other? Wouldn't that eliminate the first node of the second list?

    Good point on the stucts and pointers I wasn't really thinking there haha, been using C++ some today to for other assignments.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    next pointer from one list to the first node
    The node at the end of the first list would be connected to the first node of the second list.
    Take a piece of paper and draw some nodes for two lists. Connect the nodes in each list with a line representing the next pointer. The next pointer in last node of a list would be empty. To connect the lists, draw a line from the end of one to the start of the other.

    You need to think about what the merge() method do before writing the code.
    What class would it be in? Would it be in one of the lists to be merged?
    What would it take as parameters and what it would return?
    Will it create copies of all the nodes from the two lists or will it use the existing nodes and destroy the two lists?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Ideally I would want my merge method to be a standalone not inside one of the already existing lists. I would want it to take in two List arguments and return a list, but I just don't see how it is possible to do it that way. My other option would be to make the merge recreate both list by somehow accepting a two node arguments, and two int values (length of each list being passed), and return a new list containing all the nodes from both list: EX.
    public List mergeList (Node List1, Node List2)
    {
     
    List1Node = List1;
    List2Node = List2;
    Node newList3 = null;
     
    while (List1Node != null)
    {
        newList3.add(List1Node);
    }
     
    while (List2Node != null)
    {
       newList3.add(List2Node);
    }
     
    return newList3;
    }

    I know the above code is no where near right, but that is kind of what I'm envisioning occurring when the merge executes. Basically taking in the nodes of both list running through the first list until it hits the last position. All the while adding to the newList3, and then doing the same thing with List2. Then returning newList3 for sorting.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Are the lists sorted? Does their order matter when the lists are merged?

    Will the old lists be lost when the new list is created or will the nodes in the new list be copied from the old lists?


    Forget about writing any code until you have a design for what the new method is going to do.
    Paper and pencil are useful when working with linked list design.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    The initial list will not be sorted. Once the merged list is created then it will be sorted. The old list will still be available, I want to be able to show the two original list along with the third merged/sorted list, in other words i want the nodes in the new list to be copies of the old lists.

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Ok. Make a list of the steps the merge code needs to do. It needs to include what args it will get when it is called and what it will return.

    It sounds like the merge is just a connecting together of two lists.

    I'm done for tonight. Back tomorrow.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Merge code would need to accept two linked list arguments and return a linked list. If that can't be done i guess it will accept a Node and utilize the .next method built into java for linked list.

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Ok, start with that: the method takes two lists as input and returns a new list. What class defines the list?
    Then what does the method do?
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    I assume by "What class defines the list?" you are asking what in my code is defining/creating the list. They are being made using the private class Node then in the main method by using the add method having elements attached to them. I'm just at a loss for how the method will accept two list arguments, is List variableName, a valid decleration for passing a list argument?

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Sorry, that was poorly worded. What is the name of the linked list class the code will be using?
    You will need that to define a method that takes list objects as arguments.
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Still a bit unsure of what you mean, but i think you are asking what do i use to create my linked list and that would be HW3_Vinson. I have a constructor that initializes the list and then i'm manually filling them using the .add(xxx) method.

    So would it be right then, that after both list are made and filled in the main method, make a call to the merge method ( mergeList(HW3_Vinson list) )?

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Some class defines the methods of the linked list and holds the pointers to the nodes in the list.
    What is the name of that class? Is it HW3_Vinson?

    I'm still not sure what the merge method does with the two lists? Is it: copying the nodes from both lists and making a new list with those copied nodes? If that is what it is supposed to do, have you made a list of the steps the method must do to do it?
    What class would the merge() method be in?
    If the merge() method does something else, please explain.
    If you don't understand my answer, don't ignore it, ask a question.

  15. #15
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    The HW3_Vinson has a constructor for initial set up, then I have a Node class that is used to create pointers.

    Yes the merge method will copy the two list and create a third, all the while leaving the two original list in tact. The merge method i believe would just be in the HW3_Vinson class like the other methods, add(), isEmpty(), etc.

    I believe the merge method will need to accept one argument which would be a linked list and return a linked list.

    Step 1: Send first linked list to merger
    Step 2: Merger runs through the linked list it received and creates a new list (basically copying the list it received as an argument)
    Step 3: Return the new linked list
    Step 4: Call the merger again and send it the second linked list, this time though since our new linked list was created during Step 2 and 3 i would want it to append the items from the argument list to the new list. Question: Would I need two different merge methods to accomplish this?
    Step 5: Return the new list with the items from the second list appended
    Step 6: Run the new list through a sort for integers in ascending order.
    Step 7: Display the two original list as well as the new third list sorted.

  16. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    That design seems a bit awkward. I'd have the method do the merge in one step.

    Step 2 needs some expansion to list the steps required. The way it's worded, it sounds like a clone() method that creates a copy of the list that was passed to it.

    Step 4 is weird. Its a hybrid of Step 2 and the actual merge. ???

    Steps 6 & 7 are not part of the merge() method.


    Basically I'd start over with the design.
    If you don't understand my answer, don't ignore it, ask a question.

  17. #17
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Haha ok, well I would set up a merge method that accepts two linked list arguments. Note List3 would be initialized in the main loop to null before calling the merge(List1, List2)

    Step 1: Take the first linked list and run through it using the .next syntax with a while loop, and adds what it finds to a new linked list.

    EX: while(List1 != null)
    {
    temp = List1.next;
    List3.add(temp);
    }

    Step 2: Takes the second linked list and basically performs the same function as the above example except it would be:

    EX: while(List2 != null)
    {
    temp = List2.next;
    List3.add(temp);
    }

    Step 3: Return List3 (the newly created merged list)

  18. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    The "create a copy" step is missing.

    Why is List3 created outside of the merge() method?
    If you don't understand my answer, don't ignore it, ask a question.

  19. #19
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Would I not need to initialize List3 outside of the method to be able to access it later? I then would use the merge to add to List3.

    Also I assumed the two while loops where theoretically "creating copies" of the two passed linked list arguments and being stored into List3

  20. #20
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    to be able to access it later
    I thought that it was returned by merge(). merge() creates it, fills it and returns it.

    theoretically "creating copies"
    The more details covered in the design, the fewer problems when writing the code.
    If you don't understand my answer, don't ignore it, ask a question.

  21. #21
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Ok so if i return a LinkedList, List3, i will be able to access it like you would during a return of other methods?

    By theoretically i meant it is copying, just not using a copy method instead I am trying to read the list and as it comes to each Node it places it into temp, which is then added to List3, it then repeats until it hits the null pointer.

  22. #22
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    Do you have the steps for making a copy of a node?
    If you don't understand my answer, don't ignore it, ask a question.

  23. #23
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    I only have what i have written above which is:

    Node temp = List1.next(); OR Node temp = List2.next();

    then storing them into the new List3:

    List3.add(temp);

    I think that is what you where asking, i do not however have a separate copy method.

  24. #24
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Sort and Merge Two Linked List

    That doesn't show that a copy of the node is made. It looks like the original node is moved to List3.
    If you don't understand my answer, don't ignore it, ask a question.

  25. #25
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    Question though, wouldn't it still be left in List1 and List2? Therefore it is basically making a copy. It is storing the data of the node in temp then applying it to List3.

Page 1 of 2 12 LastLast

Similar Threads

  1. heap sort vs merge sort
    By IHeartProgramming in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 3rd, 2012, 04:37 AM
  2. [SOLVED] displaying every 1000 comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 6
    Last Post: May 27th, 2012, 07:26 PM
  3. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 26th, 2012, 11:54 PM
  4. Insertion Sort on a Doubly Linked List
    By Kaisshau in forum What's Wrong With My Code?
    Replies: 4
    Last Post: June 7th, 2011, 11:18 PM
  5. Pseudo code of insertion sort linked list
    By sungirl in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 23rd, 2010, 09:25 AM

Tags for this Thread