How to make a circular list in Java

Question

I want to make a circular LinkedList in Java. I have a polygon which contains a list of points. The list need to be circular.

I thought to create circular list: CircularList extends LinkedList but I don't know how can I continue.

Thank you for your help.

Answer 1

Here is quick fix for you.

Check following code to make a circular LinkedList in Java.

public static void main(String arg[]) {
        CircularLinkedList cl = new CircularLinkedList();
        cl.add(1);
        cl.add(2);
        cl.add(3);
        cl.add(4);
        cl.display();
    }

    public class Node{
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }
    public Node head = null;
    public Node tail = null;
    public void add(int data){
        Node newNode = new Node(data);
        if(head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head;
        }
        else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head;
        }
    }
    public void display() {
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
        }
        else {
            System.out.println("Nodes of the circular linked list: ");
             do{
                System.out.print(" "+ current.data);
                current = current.next;
            }while(current != head);
            System.out.println();
        }
    }

Hope this example helps you understand the concept of circular LinkedList.

Answer 2

I have polygon which compose of a list of points. I have class Point, Polygon and ListCircular. This is that I've maded :

import java.util.LinkedList;

public class ListCircPoly <Point> extends LinkedList {
    private Node node;
    private Node last;
    private int size;

    public ListCircPoly()
    {
        super();
        node=null;//Création d'une chaine vide
        last=null;
        size=0;
    }
    /**
     * @pre /
     * @post ajoute une valeur en fin de list
     * @param s valeur à stocker
     * @return 
     */

    @Override
    public boolean add(Object s)
    {
        if (size==0)//Si la chaine est vide
        {
            this.node= new Node(s);
            this.node.next=this.node;
            last=node;
            size=1;
        }
        else
        {
            Node addNode= new Node(s);
            addNode.next=last.next;
            last.next=addNode;
            last=addNode;
            size++;
        }
        return true;
    }

    public void print()
    {
        if (size>0)
        {
            System.out.println(this.node.data);
            Node currentNode=this.node.next;
            while (currentNode!=this.node)
            {
                System.out.println(currentNode.data);
                currentNode=currentNode.next;
            }
        }
        else System.out.println("Lise vide");

    }
    private class Node
    {
        private Object data;
        private Node next;

        public Node(Object data)
        {
            this.data=data;
            this.next=null;
        }
    }
 }

I want to use it like a linkedList but I have problems in my class Polygon.

Answer 3

LinkedList has 2 references to the first and the last node in the list.

From LinkedList source code:

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

As you see the first node has it's "prev" member set to null and the last node has the "next" member set to null. Setting first.prev= last and last.next=prev will make a circular list, BUT (careful here) you will have to override most insert, link and delete operations in linkedlist to accomodate for this change. You may need to write some code for the iterator too. It's not trivial because you will need to track where to stop when iterating the list or you may get in an infinite loop. Hope I made myself clear and the answer helps. Regards