Implement a class for a singly linked circular list that has no end & no beginni

Question

Implement a class for a singly linked circular list that has no end & no beginning. The only access to the list is a single reference, current, that can point to any link on the list. This reference can move around the list as needed. The list can be numbers of names. The list should handle insertion, searching, and deletion. However, unable to use java built-ins for circular list.

A circular list is a linked list in which the last link points back to the first link. There are many ways to design a circular list. Sometimes there is a pointer to the

Explanation / Answer

public class HelloWorld{
  
public static void main(String []args){
CircularList list = new CircularList("Jon");
list.insert("Hanna");
list.insert("Sean");
list.delete("Jon");
list.delete("Prady");
list.print();
list.insert("Snow");
list.search("Hanna");
list.search("Jon");
list.print();
}
}

class Node{
String name;
Node next;
  
Node(){
name = "";
next = null;
}
  
Node(String name){
this.name = name;
this.next = null;
}
}

class CircularList{
Node current;
  
CircularList(){
current = new Node();
current.next = current;
}
  
CircularList(String name){
current = new Node(name);
current.next = current;
System.out.println("List started with " + name);
}
  
void insert(String name){
if(current.name == ""){
current.name = name;
}
else{
Node node = new Node(name);
node.next = current.next;
current.next = node;
current = node;
}
System.out.println("Inserted " + name + " into the list");
}
  
void delete(String name){
if(current == null){
System.out.println("Can't delete!! List is already empty!!");
return;
}
Node last = current;
Node previous = current;
current = current.next;
do{
if(current == current.next){//Single node case
if(current.name == name){//List becomes empty
current = null;
System.out.println("Deleted " + name + " from the list");
return;
}
}
else{//multiple nodes case
if(current.name == name){
previous.next = current.next;
current = current.next;
System.out.println("Deleted " + name + "from the list");
return;
}
}
previous = current;
current = current.next;
}while(current != last);//Traverse until we reach the starting node again
  
//First node needs to be removed, so we traversed till the end to get its pointee
if(current.name == name){
previous.next = current.next;
current = current.next;
System.out.println("Deleted " + name + " from the list");
}
else{//Element not found in the list
System.out.println(name + " does not exist in the list, hence can't be deleted");
}
}
  
boolean search(String name){
System.out.println("Searching the list for " + name);
Node last = current;
do{
if(current.name == name){
System.out.println(name + " found in the list");
return true;
}
current = current.next;
}while(current != last);
System.out.println(name + " could not be found in the list");
return false;
}
  
void print(){
System.out.println("Contents of the list are : ");
Node last = current;
do{
System.out.print(current.name + " ");
current = current.next;
}while(current != last);
System.out.println();
}
}

//Sample output
Executing the program....
$java -Xmx128M -Xms16M HelloWorld

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.