Search code examples
javalistlinked-listcircular-list

Circular Linked List of Size K


I have a question on creating a single Circular Linked List without an add method. Just an inner class of Node, and then a constructor outside with a toString method.
I am having a hard time returning the List, I continually return nothing. and I am lost to as why because I cannot implement an add method. I have to create a circular Linked List within my constructor, so that gives me a little insight on it. But how would I assign the values to my Nodes of head and tail

class Number{ 

class Node
{
        public int num=0;           // node's position in line
        public Node next=null;  // Reference to next node
        /**
        * Node constructor, initializes number
        */

        public Node(int number)
        {
               //
            num = number;
            next = null;
        }

        public String toString() {
            return "" + num;
        }

}

private int number;
private Node head = null;   // Linked list of prisoners
private Node tail = null;   // Tracks end of list as it is constructed

/**
 * constructs a circular linked list of
 * @param n Nodes, current is the first Node and tail is the last Node (next of tail is current)
 */

public Number(int n)
{
    //
    number = n;
    LinkedList numb1 = new LinkedList();
    for (int i = 1; i <= number; i++) {
        numb1.add(i) //head I will have 1, 2, 3... n
    }
    head = null; //how would I make this reference head?
    tail = null; //how would I make this reference tail?
 }

/*
 * prints all Numbers starting from head until tail
 */
@Override
 public String toString()
 {
//
     String strVal = "";
     for (Node current = head; current != null; current = head.next) {
         strVal = strVal + current.num;
     }
     return strVal;
 }

I think the reason for this is in the for loop.
By have the current != null, it keeps going because current can never be null as it references endlessly because it is a circular Linked List. However, it would at least return something instead of nothing.

Say I call Number newNum = new Number(6);
System.out.println(newNum);
I should out put
1 2 3 4 5 6


Solution

    1. first you need to fix Number constructor. You should assign head to first node and tail to last node
     public Number(int n) {
            number = n;
            head = new Node(0);
            Node prev = head;
            for (int i = 1; i <=number; i++) {
                Node node = new Node(i);
                prev.next=node; // head I will have 1, 2, 3... n
                prev=node;
            }
            tail=prev;
        }
    

    2 . And in toString method you were always referring head.next which was causing infiinte loop as you never hit null (current != null will never become true in your code)

     public String toString() {
            String strVal = "";
            for (Node current = head; current != null; current = current.next) {
                strVal = strVal +" "+ current.num;
            }
            return strVal;
        }
    

    edit: One thing I would like to add is, your implemetation is of plain linked list and not circular linked list.. To make it circular, you should point tail to head,tail=head