views:

164

answers:

4

I would like to create a circular/cyclic linked list where the tail of the list would point back to the head of the list. So can I use java.util.LinkedList and modify the tail node after creation of the list to make it circular/cyclic? If so, can you show me some code on how that would happen?

If I can't use java.util.LinkedList, how should I create my own circular/cyclic linked list implementation? Can you show me the skeletons of how this implementation would look?

Let me know if you need more details and I'll clear up any confusion.

Thanks, Hristo

+1  A: 

java.util.LinkedList is one of the Collections datatypes. The purpose of Collections is to provide utility structures, not bothering the programmer to worry about their internal implementation. If you must have internals that work in a certain way, and the java.util ones do not guarantee that is how they work, then they are not for you.

To implement a circular linked list, first create a ListNode class:

class ListNode {
    ListNode next;
    ListNode prev;
    Object data;
}

Then store a ListNode head, and make sure prev of head points to the "end" of the list, and next of the "end" points back to head. Honestly, though, there's little difference between a bidirectionally linked list keeping a tail pointer and a circular linked list.

Borealid
I don't need a "bidirectional" linked list, so no need for `ListNode prev`. But thanks for your suggestion. I'll give it a try.
Hristo
A: 

Refer here for a comprehensive implementation of Singly Linked List in Java. Making it circular is just a tweak in that code.

Bragboy
Thanks! This is a great reference. What would it take to make that into a circular linked list?
Hristo
+1  A: 

http://www.cs.princeton.edu/algs4/13stacks/CircularLinkedList.java.html

Romain Hippeau
Thanks! This is what I'm looking for.
Hristo
+2  A: 
class ListNode {
    public ListNode next;
    public Object data;

    public ListNode(ListNode next, Object data)
    {
        this.next = next;
        this.data = data;
    }
}

class CircularLinkedList
{
    private ListNode head = null;
    private int numberOfElements = 0;
    private ListNode actualElement = null;
    private index = 0;

    public bool isEmpty()
    {
        return (numberOfElements == 0);
    }

    public int getNumberOfElements()
    {
        return numberOfElements;
    }

    public void insertFirst(Object data)
    {
        if (!(isEmpty()))
            index++;
        ListNode listNode = new ListNode(data, head);
        head = listNode;
        numberOfElements++;
    }

    public void insertAfterActual(Object data)
    {
        ListNode listNode = new ListNode(data, actualElement.next);
        actualElement.next = listNode;
        numberOfElements++;
    }

    public bool deleteFirst()
    {
        if (isEmpty())
            return false;
        if (index > 0)
            index--;
        head = head.next;
        numberOfElements--;
        return true;
    }

    public bool deleteActualElement()
    {
        if (index > 0)
        {
            numberOfElements--;
            index--;
            ListNode listNode = head;
            while (listNode.next.Equals(actualElement) == false)
                listNode = listNode.next;
            listNode.next = actualElement.next;
            actualElement = listNode;
            return true;
        }
        else
        {
            actualElement = head.next;
            index = 0;
            return deleteFirst();
        }
        return false;
    }

    public bool goToNextElement()
    {
        if (isEmpty())
            return false;
        index = (index + 1) % numberOfElements;
        if (index == 0)
            actualElement = head;
        else
            actualElement = actualElement.next;
        return true;
    }

    public Object getActualElementData()
    {
        return actualElement.data;
    }

    public void setActualElementData(Object data)
    {
        actualElement.data = data;
    }
}
Lajos Arpad
Wow! I already implemented a circular linked list but not all of the methods you provided. Thank you for this.
Hristo
You're welcome, I was happy to help.
Lajos Arpad
There were two minor bugs in the deleteActualElement method, I've corrected them.
Lajos Arpad