Can I use java.util.LinkedList to construct a circular/cyclic linked list?

Question

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.

I just want to play around with making one. No real reason except for myself. I haven't seen many implementations of this online and I just want to give it a try. — Hristo
– Hristo, Commented Sep 18, 2010 at 15:24
@puddingfox: A circular list is useful for round-robin access of a collection (e.g. for load-balancing) — user359996
– user359996, Commented Oct 5, 2010 at 18:53
@user359996: Is using a circular list for round robin just a good programming practise? I understand that 'round' and 'circular' go together, but are there any other reasons for using a circular list over an array list? — Victor
– Victor, Commented Aug 26, 2013 at 1:49
How the circular list is implemented isn't super important. To your point, I personally would use an ArrayList and then wrap it with docs.guava-libraries.googlecode.com/git-history/release/javadoc/…. EDIT: Apparently, that's even one of the answers someone gave... — user359996
– user359996, Commented Sep 13, 2013 at 15:11

Ralph · Accepted Answer · 2014-11-06 03:18:16Z

class ListNode {
    public ListNode next;
    public Object data;

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

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

    public boolean 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 boolean deleteFirst() {
        if (isEmpty())
            return false;
        if (index > 0)
            index--;
        head = head.next;
        numberOfElements--;
        return true;
    }

    public boolean 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();
        }
    }

    public boolean 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;
    }
}

Jack · Accepted Answer · 2020-06-21 00:32:07Z

13

For practical application (e.g. not only playing around or learning) I would personally prefer Guava's Iterables.cycle method - see Iterables.cycle

edited Jun 21, 2020 at 0:32

Jack

5,6422 gold badges34 silver badges56 bronze badges

answered Aug 31, 2011 at 14:37

Tomáš Záluský

12.3k4 gold badges44 silver badges74 bronze badges

Comments

Borealid · Accepted Answer · 2010-09-18 15:10:00Z

3

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.

answered Sep 18, 2010 at 15:10

Borealid

99.4k9 gold badges112 silver badges124 bronze badges

1 Comment

Hristo Over a year ago

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.

MarekM · Accepted Answer · 2022-02-21 12:18:59Z

1

You can use simple solution using Deque. Pool last value from deque and insert it as first. This will cause cyclic roatation of values

Deque<String> circularStructure = new ArrayDeque();
circularStructure.addAll(List.of("Val1","Val2","Val3"));

for(i=0;i<100;i++){
   String value = typeCodeStack.pollLast(); //take and remove last
   typeCodeStack.push(code); //add as first
   //section where to use value 
   someOperationOnValue(value)
});

answered Feb 21, 2022 at 12:18

MarekM

1,49617 silver badges14 bronze badges

Collectives™ on Stack Overflow

Can I use java.util.LinkedList to construct a circular/cyclic linked list?

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related