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.

Results 1 to 14 of 14

Thread: Infinite loop on double linked list

  1. #1
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Infinite loop on double linked list

    I've been stuck for the last couple hours trying to understand why the "printInReverse" method is getting into an infinite loop. I have no idea. I was supposed to make a double linked list that you can insert numbers and it orders both ascending and descending; in this case, descending is the "printInReverse" method, which takes the already ordered lists and prints it reversed, like if it was descending, and that's where the problem lives. Here follows the whole code:

    import java.util.Scanner;
     
    public class MyList {
     
    private Scanner userInput;
    private Integer selectedOption;
     
    private MyListElement firstElement = null;
    private boolean exitRequested = false;
     
    public static void main(final String[] args) {
        new MyList(new Scanner(System.in)).run();
    }
     
    private MyList(final Scanner userInput) {
        this.userInput = userInput;
    }
     
    public void run() {
        do {
            promptUserForOption();
            processSelectedOption();
        } while (!exitRequested);
    }
     
    private void promptUserForOption() {
        System.out.println("");
        System.out.println("1 - insert number in the beginning list");
        System.out.println("2 - insert in the end of the list");
        System.out.println("3 - query list");
        System.out.println("4 - remove from list");
        System.out.println("5 - empty list");
        System.out.println("6 - exit");
        System.out.println("7 - sort reverse");
        System.out.print("Please choose option: ");
     
        try {
            selectedOption = Integer.parseInt(userInput.nextLine());
        } catch (final Exception e) {
            printWrongOperationSelected();
            selectedOption = -1;
        }
    }
     
    private void printWrongOperationSelected() {
        System.out.println("Wrong operation selected.");
    }
     
    private void processSelectedOption() {
        switch (selectedOption) {
            case 1:
            case 2: {
                addNewElement();
            }
            break;
            case 3: {
                printList();
            }
            break;
            case 4: {
                removeElement();
            }
            break;
            case 5: {
                clearList();
            }
            break;
            case 6: {
                exit();
            }
            case 7: {
                printInReverse();
            }
            break;
            default: {
                printWrongOperationSelected();
            }
        }
    }
     
    private void addNewElement() {
        System.out.print("Please type the number to be added to the list: ");
     
        Integer newValue = null;
        while (newValue == null) {
            try {
                newValue = Integer.parseInt(userInput.nextLine());
            } catch (final Exception e) {
                System.out.println("Wrong value. Please insert new value.");
            }
        }
     
        MyListElement newElement = new MyListElement(newValue);
     
        if (firstElement != null) {
            placeElementInList(newElement);
        } else {
            firstElement = newElement;
        }
    }
     
    private void placeElementInList(final MyListElement newElement) {
        if (newElement.value < firstElement.value) {
            newElement.nextElement = firstElement;
            firstElement = newElement;
        } else {
            MyListElement previousElement = firstElement;
            MyListElement elementInList = firstElement.nextElement;
            while (elementInList != null) {
                if (newElement.value < elementInList.value) {
                    break;
                }
                previousElement = elementInList;
                elementInList = elementInList.nextElement;
            }
            previousElement.nextElement = newElement;
            newElement.nextElement = elementInList;
        }
    }
     
    private void printList() {
        if (firstElement == null) {
            System.out.println("No elements in the list.");
        } else {
            MyListElement elementInList = firstElement;
            while (elementInList != null) {
                System.out.print(elementInList.value + ", ");
                elementInList = elementInList.nextElement;
            }
            System.out.println("");
        }
    }
     
    private void removeElement() {
        System.out.print("Please type the number to be removed from the list: ");
        Integer valueToRemove = null;
        while (valueToRemove == null) {
            try {
                valueToRemove = Integer.parseInt(userInput.nextLine());
            } catch (final Exception e) {
                System.out.println("Wrong value. Please insert value to remove.");
            }
        }
     
        if (firstElement == null) {
            System.out.println("No elements in the list. None can be removed.");
        } else {
            boolean found = false;
     
            if (firstElement.value.equals(valueToRemove)) {
                firstElement = firstElement.nextElement;
                found = true;
            } else {
                MyListElement previousElement = firstElement;
                MyListElement elementInList = firstElement.nextElement;
                while (elementInList != null) {
                    if (elementInList.value.equals(valueToRemove)) {
                        previousElement.nextElement = elementInList.nextElement;
                        found = true;
                        break;
                    }
                    previousElement = elementInList;
                    elementInList = elementInList.nextElement;
                }
            }
     
            if (!found) {
                System.out.println("Value " + valueToRemove + " is not in the list.");
                return;
            } else {
                System.out.println("Value removed.");
            }
        }
    }
     
    private void clearList() {
        firstElement = null;
    }
     
    private void exit() {
        exitRequested = true;
    }
     
    private void printInReverse() {
        MyListElement tmpElement = firstElement;
        MyListElement previousElement = tmpElement.nextElement;
        while (previousElement != null) {
            previousElement.nextElement = tmpElement;
            tmpElement = previousElement;
            previousElement = previousElement.nextElement;
        }
        MyListElement firstReverseElement = tmpElement;
        MyListElement elementInList = firstReverseElement;
        while (elementInList != null) {
            System.out.print(elementInList.value + ", ");
            elementInList = elementInList.nextElement;
        }
        System.out.println("");
    }
     
    private class MyListElement {
     
        private final Integer value;
        private MyListElement nextElement;
     
        private MyListElement(final Integer value) {
            this.value = value;
        }
    }


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Infinite loop on double linked list

    Your choice of variable names is confusing: previousElement begins by pointing to the next element.
    A quick look at the first loops it seems you are actually reordering the first two elements over and over and over. The position of elements in the list should not change at all.

    All you need to do is place you temp variable at the last element, print it out, move temp to previous element, repeat until you reach the first element.
    Improving the world one idiot at a time!

  3. #3
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    Okay, got it. But how could I declare a variable that points to the last element in the list? Thank you.

  4. #4
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Infinite loop on double linked list

    How do you add a new element to the List?

    --- Update ---

    OK

    Just looked at the code and it seems you are maintaining a Sorted List. Normal List implementations have two instance variable, one points at the first element and one points at the last element.

    Alternatively, have a temp variable point at the first element, while temp.next is not null update temp to be next. At the end of that loop temp will be pointing at the last element.
    Improving the world one idiot at a time!

  5. #5
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    Okay, got it. But how could I get the previousElement from my lastElement? I tried to do create an auxElement variable, storing firstElement and progressing through the list until lastElement is null but it did not work.

  6. #6
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Infinite loop on double linked list

    lastElement.previousElement; // ???

  7. #7
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    Yes I know. I mean, I'm not managing to make my previousElement to effectively point to an element's previous element. I guess you'll understand better if I post the code:

    private void printInReverse() {
            MyListElement tmpElement = firstElement;
            while (tmpElement.nextElement != null) {
                tmpElement = tmpElement.nextElement;
            }
            //tmpElement gets the last value on list
            MyListElement firstReverseElement = tmpElement;
     
            MyListElement elementInList = firstReverseElement;
            while (elementInList != null) {
                System.out.print(elementInList.value + ", ");
                elementInList = elementInList.prevElement;
            }
            System.out.println("");
     
        }

    It's only printing my last element.

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,467
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Infinite loop on double linked list

    Is the list properly chained? The loop stops when the prev link is null.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    It stops when the prev link is null because it's when the first element of the list is reached so the list was percurred.

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,467
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Infinite loop on double linked list

    Ok, then the code is working correctly? I thought you said there was a problem:
    It's only printing my last element.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    It's not. Exactly, it's only printing my last element because I don't know how to get the previousElement pointer to actually point to an element's previous element.

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,467
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Infinite loop on double linked list

    how to get the previousElement pointer to actually point to an element's previous element
    One of the steps in designing a linked list is to use paper and pencil to draw a list.
    Then work out how the links need to be changed for the various changes that can be made to the list:
    add at front
    add in middle
    add at end
    and the same steps for remove

    An important part of getting the code working is debugging it. There should be a print method that will print the list front to end and show the contents of each node and the links for each node.
    Do you have that method? What does it print for the list?
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Junior Member
    Join Date
    Sep 2014
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infinite loop on double linked list

    It prints always the same address for the pointers. Here it is:

    private void printInReverse() {
            MyListElement tmpElement = firstElement;
            while (tmpElement.nextElement != null) {
                tmpElement = tmpElement.nextElement;
            }
     
            MyListElement firstReverseElement = tmpElement;
     
            MyListElement elementInList = firstReverseElement;
            System.out.println("tmpElement => " + tmpElement);
            System.out.println("elementInList => " + elementInList);
            System.out.println("firstReverseElement => " + firstReverseElement);
            System.out.println("prevElement => " + elementInList.prevElement);
            while (elementInList != null) {
                System.out.print(elementInList + " => " + elementInList.value + "\n ");
                elementInList = elementInList.prevElement;
            }
            System.out.println("");
     
        }

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,467
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Infinite loop on double linked list

    Add some debug code to the program that prints out the full list every time it is changed. For each node, print out its value and its links.
    Then as the code is executed you can immediately see when a problem happens.

    After you have added that debug code, execute the program, copy the print out and paste it here.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. loop through linked list of objects and their fields
    By dulitul in forum What's Wrong With My Code?
    Replies: 2
    Last Post: December 2nd, 2013, 07:49 PM
  2. Bubble Sort on double Linked List
    By Wolverine89 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: October 1st, 2013, 12:44 PM
  3. [Linked List] Problems deleting items from a linked list
    By KLVTZ in forum What's Wrong With My Code?
    Replies: 7
    Last Post: March 8th, 2013, 09:21 PM
  4. Please Help: Simple Double Linked List (remove, addBefore, )
    By yeohv in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 30th, 2012, 12:58 PM
  5. Help with using iterator remove on double linked list
    By papated21 in forum Collections and Generics
    Replies: 3
    Last Post: October 18th, 2011, 09:22 PM

Tags for this Thread