How to implements circular linked list in Java?

Question

I have a project I am working on which require the implementation of circular likened list without the use of an API. I did most part of the code but for some reasons I cannot get the output I am looking for. I am kindly requesting anyone who can help me out to fix the problem. One specific problem is that I cannot put the pointer to start iterating from the key I found in the find method. e.g. if the array elements are 10 , 9 ,8 ,5,6. if I pass 8 as argument to the find method, if found it, it should display as 8,5,6,10, 9 etc. otherwise leave the elements as it is.

Below is the code I have ready and PLEASE see the output right beneath it, I guess that will help you to figure out what i am looking for specifically. Pay close attention to my insert, find, step method. thank you in advance!`

//LinkFirstLast Classs
class LinkFirstLast {
public long theData;
public LinkFirstLast next;
public LinkFirstLast last;
public LinkFirstLast previous;

public LinkFirstLast() {
}

public LinkFirstLast(int data) {
    theData =data;  
    }

    public void displayLink(){
    System.out.print(theData+ " ");
    }
    }
    // Circular linklist class//////////////////
    class CircList {

    private LinkFirstLast first, last;
    int nItems;
    //Constructor
    public CircList(){
    last = null;
    }
     //Creates a node and inserts new data
    public void insert(int data) {
    LinkFirstLast newLink = new LinkFirstLast(data);

     if(isEmpty()){
        last = newLink;
         // first = newLink;        
     }      
     else{
            first.previous = newLink;           
        }
     newLink.next = first;  
     first = newLink;    
         //last.next = first;
         // first.previous = last;          
     nItems++;
    }

    public void displayList() {
         LinkFirstLast current = first;
    while(current != null){
            current.displayLink();
            current =current.next;
                    }

    System.out.println("");

    }

    public LinkFirstLast find(int key) {
          LinkFirstLast current = first;
    while(current != null && current.theData != key){

          if(current.theData == key){
             first = current;
         first = current.next;
         last.next = first;
          } 
          else{
         current = current.next;

         }
         }

    /*
           first.previous = newLink;            

           newLink.next = first;    
            first = newLink;



    LinkFirstLast current = first;

    while(current != null && current.theData != key  )      

    {

                       current = current.next;

            }
    */
    return current;

    }

    public LinkFirstLast delete() {
    LinkFirstLast current; 
    current = first;
    while(first.next == null){
        last = null;
    }
    first = first.next;

    return current;
    }

    public int getSize() {

        return nItems;

    }

    public void step() {
    System.out.print("List: ");
    if(first != null && first.next !=null){
    first.next= first.next;

    }

}

  //Checks if linkedlist has no item
    public boolean isEmpty() {

    return (nItems==0);
    }

    public LinkFirstLast delete(int key) {
     LinkFirstLast current = first; 
    LinkFirstLast previous = first;
    while(current.theData != key)
    {
    if(current.next == null)
    return null;
    else
    {
    previous = current;
        current = current.next;

    }
    } 
    if(current == first)
    first = first.next;
    else 
    previous.next = current.next; 
    nItems--;
    return current;
    }
    // -------------------------------------------------------------
    }


    // main
    class Pro {
       public static void main(String[] args)
         {
       LinkFirstLast f, d;
         CircList theList = new CircList();  // make list

      theList.insert(10);      // insert items
      theList.insert(20);
      theList.insert(30);
      theList.insert(40);
      theList.insert(50);
      theList.insert(60);
      theList.insert(70);

      theList.displayList();              

      f = theList.find(30);               
      if( f != null){
         System.out.println("Found link with key " + f.theData);
      }
      else{
         System.out.println("Can't find link with key 30");
      }
      theList.displayList();              // display list

      System.out.println("Inserting link with key 80");
      theList.insert(80);
      theList.displayList();              // display list

      d = theList.delete(60);             // delete item
      if( d != null )
         System.out.println("Deleted link with key " + d.theData);
      else
         System.out.println("Can't delete link with key 60");
      theList.displayList();              // display list


      f = theList.find(99);               // find item
      if( f != null){
         System.out.println("Found link with key " + f.theData);}
      else
         System.out.println("Can't find link with key 99" );
      theList.displayList();              // display list

      d = theList.delete(13);             // delete item
      if( d != null )
         System.out.println("Deleted link with key " + d.theData);
      else
         System.out.println("Can't delete link with key 13");
      theList.displayList();              // display list

      System.out.println("Stepping through list");
      for(int j=0; j<theList.getSize(); j++)
        {
         theList.step();
         theList.displayList();
         }


      System.out.println("Will delete and step one by one");
      while(theList.isEmpty() == false)
         {
         theList.delete();
         theList.step();
         theList.displayList();
         }

      }  // end main()
   }  // end class CircApp

The output is:

List: 70 60 50 40 30 20 10 
Found link with key 30
List: 30 20 10 70 60 50 40 
Inserting link with key 80
List: 80 30 20 10 70 60 50 40 
Deleted link with key 60
List: 50 40 80 30 20 10 70 
Can't find link with key 99
List: 50 40 80 30 20 10 70 
Can't delete link with key 13
List: 50 40 80 30 20 10 70 
Stepping through list
List: 40 80 30 20 10 70 50 
List: 80 30 20 10 70 50 40 
List: 30 20 10 70 50 40 80 
List: 20 10 70 50 40 80 30 
List: 10 70 50 40 80 30 20 
List: 70 50 40 80 30 20 10 
List: 50 40 80 30 20 10 70 
Will delete and step one by one
List: 80 30 20 10 70 40 
List: 20 10 70 40 30 
List: 70 40 30 10 
List: 30 10 40 
List: 40 10 
List: 10 
List:

You should locate the key node and assign it the head node.If the key isn't found, just leave the head where it is. I hope that'd work for you. — Am_I_Helpful
– Am_I_Helpful, Commented Nov 15, 2015 at 9:01
I appreciate your attention. I thinks i actually did thatbut it just put the key to head instead of just rotating everything. Also my step() is not giving me the right Out as well it just copying the elements at every iteration instead of just rotating them anti clockwise. — Ali
– Ali, Commented Nov 15, 2015 at 15:07
Nothing needs to get rotated, you only need to shift head to the key location. Rest will follow eventually! — Am_I_Helpful
– Am_I_Helpful, Commented Nov 15, 2015 at 16:24
@Am_I_Helpful by the way my output is not looking like the one up there that is just to show you how i want it — Ali
– Ali, Commented Nov 15, 2015 at 17:04
What code have you mentioned in the 2nd last comment? Please edit that in your question. — Am_I_Helpful
– Am_I_Helpful, Commented Nov 15, 2015 at 17:05

Am_I_Helpful · Accepted Answer · 2015-11-16 20:31:33Z

There are several issues with your code:

Not good definition of class FirstLastLinkedList
The methods are not doing what they should do.
Also, there doesn't exist any place which shows that the list ends here. I have done that in my code.
Your output is also not consistent; I believe my program would better give you insight. I've added output also of my code.

I am leaving the code for you to understand. If you've any difficulty understanding it, please comment below :-

    /**
 *
 * @author ssuman
 */

class FirstLastLinkedList{
    protected long data;
    protected FirstLastLinkedList next;
    protected FirstLastLinkedList() {
    }    
}

class CircularLinkedList {

    private FirstLastLinkedList head = null,temp = null, move = null, prev = null;
    // `temp` is used to store the last node just before the `head` node;
    protected void findInList(int userData){
        if(head==null){
            System.out.println("Can't find link with key "+ userData+"; List is empty!");
            return;
        }
        move = head;
        do{
            if(move.data == userData){
                System.out.println("Found link with key "+ userData);
                return;
            }
            move = move.next;
        }while(move != head);
        System.out.println("Can't find link with key "+ userData);
    }

    protected void deleteFromList(int userData){
        prev = move = head;
        if(head==null){
            System.out.println("Can't delete link with key "+ userData+"; List is empty!");
            return;
        }
        do{
            if(move.data == userData){
                prev = getPreviousNodeInList(move);
                head = move = move.next;
                prev.next = move;
                System.out.println("Deleted link with key "+ userData);
                displayList();
                return;
            }
            prev = move;
            move = move.next;
        }while(move != head);
        System.out.println("Can't delete link with key "+ userData);
    }

    protected FirstLastLinkedList getPreviousNodeInList(FirstLastLinkedList current){
        move = head;
        if(current == null){
            return null;
        }

        do{ 
            if(head == current){
                return temp;
            }
            if(move == current){
                return prev;
            }
            prev = move;
            move = move.next;
        }while(move != head);
        return null;
    }

    protected void insertInList(int userData){
        if(head==null){
            head = new FirstLastLinkedList();
            System.out.println("Inserting Link with key "+userData);
            head.data = userData;
            head.next = null;   
            move = head;
        }
        else{
            temp = new FirstLastLinkedList();
            System.out.println("Inserting Link with key "+userData);
            temp.data = userData;
            move.next = temp;
            move = temp;
        }
    }

    protected void endList(){
        temp.next = head;
    }

    protected void stepThroughList(){
        if(head == null){
            System.out.println("List is empty...");
            return;
        }
        FirstLastLinkedList temporary;
        System.out.println("Stepping through List :- ");
        temporary = head;
        do{
            move = temporary;
                do{          
                    System.out.print(move.next.data+"  ");  
                    move = move.next;
                }while(move != temporary);
            temporary = temporary.next;
            System.out.println("");
        }while(temporary != head);
    }

    protected void deleteInStepsFromList(){
        System.out.println("Will delete and step one by one :- ");
        prev = move = head;
        if(head==null){
            System.out.println("Can't delete links ; List is empty!");
            return;
        }
        do{
            prev = getPreviousNodeInList(move);
            head = move = move.next;
            prev.next = move;
            displayList();
        }while(move != prev);
    }

    protected void displayList(){
        move = head;
        System.out.print("List :  ");
        do{
            System.out.print(move.data+"  ");
            move = move.next;
        }while(move != head);
        System.out.println();
    }
}

public class TestCircularLinkedList{
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.insertInList(10);
        cll.insertInList(20);
        cll.insertInList(30);
        cll.insertInList(40);
        cll.insertInList(50);
        cll.insertInList(60);
        cll.insertInList(70);
        System.out.println("The List ended here...");
        cll.endList();
        cll.stepThroughList();
        cll.findInList(10);
        cll.findInList(33);
        cll.displayList();
        cll.deleteFromList(100);
        cll.deleteInStepsFromList();
    }
}

OUTPUT :-

Inserting Link with key 10
Inserting Link with key 20
Inserting Link with key 30
Inserting Link with key 40
Inserting Link with key 50
Inserting Link with key 60
Inserting Link with key 70
The List ended here...
Stepping through List :- 
20  30  40  50  60  70  10  
30  40  50  60  70  10  20  
40  50  60  70  10  20  30  
50  60  70  10  20  30  40  
60  70  10  20  30  40  50  
70  10  20  30  40  50  60  
10  20  30  40  50  60  70  
Found link with key 10
Can't find link with key 33
List :  10  20  30  40  50  60  70  
Can't delete link with key 100
Will delete and step one by one :- 
List :  20  30  40  50  60  70  
List :  30  40  50  60  70  
List :  40  50  60  70  
List :  50  60  70  
List :  60  70  
List :  70

you are the best thanks for your services. did you have any forum or blog somewhere i would love to follow you there to.
@Ali - No dear, I ain't the best. there are several others better than me, THANKS by the way.
@Ali - Currently, I don't have any blog, or forum, but may start in the future. BTW, did you complete the code which I've left in the answer?
not yet but i have clearly seen my problem :). I have class for next few hours after that i will work on it

Collectives™ on Stack Overflow

How to implements circular linked list in Java?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related