CODEWITHSUNDEEP
java
jv0006
jv0006

Reputation: 43

Circular Double Linked List Infinite Loop

My CS professor asked us to develop our own Java program using circular linked lists. My project is to add or delete names (of type String) from a circular list. So far, my add methods work perfectly; however, my removeNode() method does not work and does not remove the desired element. It also goes on an infinite loop and I have tried so many pieces of code and neither of them work. My remove method is the following: 

public E removeNode(E nodeToBeDeleted)
{
    Node<E> nodeFound = findNode(nodeToBeDeleted);

    if(nodeFound != null)
    {
        nodeFound.prev.next = nodeFound.next;
        nodeFound.next.prev = nodeFound.prev;
        size--;
        return nodeFound.data;  
    }
    return null;
}

basically, the findNode() searches for the node whose data is equal to the String plugged in as a parameter, but when I call the outputList() method, which returns a String representation of the current nodes on screen, it goes on infinite loop.

The outputList method is:

public void outputList()
{   
    Node<E> position = head;
    do 
    {
        System.out.print(position.data + " ==> ");
        position = position.next;

    } while((position != null) && (position.next != position));
}

Any help would be highly appreciated.. Thanks in advance.

The Node class is:

    static class Node<E> {

    /** The data value. */
    private E data;
    /** The link to the next node. */
    private Node<E> next = null;
    /** The link to the previous node. */
    private Node<E> prev = null;

    private Node(E dataItem) {
        data = dataItem;
    }


    private Node(E newData, Node<E> nodeRef)
    {
        data = newData;
        next = nodeRef;
    }

    private Node(Node<E> prevRef, E newData)
    {
        data = newData;
        prev = prevRef;
    }

   //set next link
    private Node(Node<E> newData, Node<E> nodeRef)
    {
        data = (E) newData;
        next = nodeRef;
    }
} //end class Node

Upvotes: 1

Views: 1114

Answers (2)

Achintya Jha
Achintya Jha

Reputation: 12843

while(position.next != head)

I think checking above condition is enough for Doubly Circular LinkedList.

Upvotes: 0

Makoto
Makoto

Reputation: 106390

while((position != null) && (position.next != position))

This should really be:

while((position != null) && (position.next != head))

Imagine if you have a singleton - the absolute base case for traversal. head and position will both be pointing to it when you start, and when you wish to advance, position will refer to the same place as head once again. This will continue ad infinitum.

The iteration must stop when you've reached your starting point once again.

Upvotes: 4

Related Questions