How to implement circular linked list in java?

Question

I read the book Data Structures and Algorithms, which has an assignment that asks me to implement a circular linked list. This is a training exercise, and my code may not be of a very high standard.

The main idea of ​​my implementation of a circular linked list is to have a pointer that points to the last item, and every time I add a new item, the "next" field of the last item will be updated to indicate the new item added.

The insert method works fine, I can add an item without any problems, but for some reason I cannot remove the items from the list.

Here is the code for "Link" or "Node":

public class Link { public long data; public Link next; public Link(long val) { data = val; next = null; } public void displayLink() { System.out.print(data + " "); } } // end class 

This is the code for the class that does the work, and the error is obviously somewhere around here:

 public class CircularList { Link first; Link last; public CircularList() { first = null; last = null; } public Link find(long key) { Link current = first; while(current.data != key) { current = current.next; } return current; } // end find public Link delete() { if(first.next == null) last = null; Link temp = first; first = first.next; return temp; } // end delete public boolean isEmpty() { return (first == null); } public void insert(long val) { Link newLink = new Link(val); if(isEmpty()) last = newLink; newLink.next = first; first = newLink; last.next = first; } // end insert public void displayAmount(int n) { Link current = first; while(n>0) { current.displayLink(); current = current.next; n--; } System.out.println(""); } // end displayAmount } // end class 

And the main application code:

 public class App { public static void main(String[] args) { CircularList cl = new CircularList(); cl.insert(10); cl.insert(20); cl.insert(30); cl.insert(40); cl.displayAmount(6); cl.delete(); cl.displayAmount(6); } } // end class 

The display volume looks silly, I just tried to avoid an infinite loop and did something simple that just works.

Answer 1

Add last.next = first before return temp to the delete () function:

 public Link delete() { if(first.next == null) last = null; Link temp = first; first = first.next; if(last != null) last.next = first return temp; } 

Updated:

I cannot find a script that satisfies first.next == null , and we have to account for the delete () call in an empty list.

 public Link delete() { Link temp = first; if(first == null){ ; // or you can throw some exception as a warning } else if(first==last){ // only one element first = null; // reset to initial state last = null; } else{ first = first.next; last.next = first; } return temp; } 

Answer 2

Your delete() method does not handle the roundness of the list. The last element indicates the first element; which also needs updating when deleting the first item.

In other words, you need to set last.next to point to the new first , not the old first .

Another problem is that if you delete the last element (so that it is now empty), you also need to set last to null .

 public Link delete() { if (first.next == null) { first = null; last = null; } Link temp = first; first = first.next; last.next = first; return temp; }