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:
There are several issues with your code:
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