CODEWITHSUNDEEP
javalinked-list
user508833
user508833

Reputation: 17

Java Programming - Circular LinkedList

I am trying to write a java class CircularList which contains the usual Node inner class and the instance variables:

Upvotes: 0

Views: 3316

Answers (4)

Mohammad Abdel Rahman
Mohammad Abdel Rahman

Reputation: 1

class Node    {
    int value;
    Node next;
    Node prev;
    Node(int initialValue)    {
        value = initialValue;
        next =  null;
        prev = null;
    }
    public int getValue()    {
        return this.value;
    }
}

class NodeList    {
    Node pointer;
    NodeList()    {
        pointer = null;
    }
    public void insertNode(int nodeValue)    {
        Node newNode = new Node(nodeValue);
        if( pointer == null )    {
            newNode.next = newNode;
            newNode.prev = newNode;
        }else if( pointer.next == null && pointer.prev == null && pointer != null )    {
            newNode.next = pointer;
            newNode.prev = pointer;
            pointer.prev = newNode;
            pointer.next = newNode;
        }
        else if( pointer != null )    {
            newNode.next = pointer.next;
            newNode.prev = pointer;
            pointer.next.prev = newNode;
            pointer.next = newNode;
        }
        pointer = newNode;
        System.out.println(“Successfully inserted : ” + pointer.getValue());
    }
    public void printRing( boolean direction )    {
        Node tempNode = pointer;
        do    {
            System.out.println( “Value = ” + tempNode.getValue() );
            tempNode = direction ? tempNode.next : tempNode.prev;
        } while( tempNode.value != pointer.value );    
    }    
}

Upvotes: 0

Zepee
Zepee

Reputation: 1880

I'm not sure what your issue is, you seem to have everything needed. The only difference between that linked list and a normal one would be adding to the end.

In a regular linked list you would create a new node and make the last element point to that node. In this case, you change the pointer in the •Last node to point to the new node, and make the new node point to •First.

Removal works in the same way as a normal linked list. Whenever you want to remove a node, you find which other node points to that one (either previous, or in case of removing the first, check •Last) and make it point to wherever the one being deleted was pointing.

If this does not resolve your issue let me know and I'll try to help.

Just noticed someone has already asked the exact same question: Can I use java.util.LinkedList to construct a circular/cyclic linked list?

Upvotes: 2

David Conde
David Conde

Reputation: 4637

OK, I won't give you the full implementation of the class, but instead I'll give you some advices.

  1. You don't need to hold a reference to the last element. Place a Prev and Next reference to your nodes and your last node will be first.Prev

  2. Besides the fact that circular lists have no end, they are quite the same than regular lists, but where you find the last item like this:

    Node tmp = first;

    while ( tmp.Next != null ) tmp = tmp.Next;

In a circular list the idea is like this:

Node tmp = first;

while ( tmp.Next != first )
   tmp = tmp.Next;

Because you will never find a node pointing to null, unless the list is empty. One final advice, if you need to implement an indexer, remember that in a circular list there is no such thing as index out of range, because 

list[count] = list[0] = list[count * k]

Keep that in mind, so calculating your index for those methods can be quite tricky. For positive indexes, the main idea is:

index = index % count;

For negative ones is slightly different. I hope I can help you with my words. If you want an implementations, I believe that there should be a few if you ask Google politely :)

Best of luck!

Upvotes: 2

Pete
Pete

Reputation: 10871

Hint... circular list should have next and previous instead of first and last. The logic matters

Upvotes: 0

Related Questions