I am trying to create a Circular Link list based on the following: The only access to the list is a single reference, current, that can point to any link on the list and can move around the list as needed. The list should handle insertion, searching and deletion: these operations take place one link downstream of the link pointed to by current. Be able to display the list.
1) The data members of class circular linked list should include the reference current and a variable to track the size of links in the circular list.
2) The methods needed to define in the class circular include:
• insert: insert after current link • delete: delete one beyond current • find: find link with given key • deleteKey: delete link with given key • displayList: display the list (all the links in the list) • step: move current to the next link • peek: return the data stored in current • isEmpty: check whether the list is empty
Here is my current code (right now it is linear - haven't made it circular yet):
public class CircularList<T> {
private Link current; // ref to the current link in the list
private int nLinks; //Reference to number of links in the list
//--------------------------------------------------------------
public CircularList() // constructor
{
current = null;
nLinks = 0;
} //End constructor method - CircularList()
// -------------------------------------------------------------
public void insert(long dd)
{
Link newLink = new Link(dd); // make new link
if (nLinks == 0)
{
current = newLink;
nLinks++;
}
if(nLinks != 0)
{
current.next = newLink; // current --> newLink
newLink = current;
nLinks++;
}
} //End insert()
// --------------------------------------------------------------
public Link delete() // delete link after current
{
Link temp = null;
if(nLinks == 0) //first check whether the list is empty
return null;
if(nLinks != 0)
{
temp = current.next; // save reference to link
current = current.next; // delete it: current-->one after current
nLinks--;
}
return temp; // return deleted link
} //End delete()
// -------------------------------------------------------------
public void displayList()
{
System.out.print("List: ");
int tempLinks = nLinks;
while(tempLinks > 0) // until end of list
{
current.displayLink(); // print data
tempLinks--; // decrement nLinks
current = current.next; // move to next link
}
System.out.println("");
} //End displayList()
// -------------------------------------------------------------
public boolean isEmpty() // true if list is empty
{
return (current==null);
} //End isEmpty()
// -------------------------------------------------------------
public void step() //Move current to next Link
{
current = current.next;
} //End step()
} //End CircularList Class
When it runs I get a null pointer exception. (I am thinking there is something wrong with my insert method to cause this issue when I try to call the display method) I am pretty sure it is not inserting all 4 links properly. When I try to display it, it only displays the data 2 and 8, which are the first and last items inserted.
My link class:
public class Link {
public long dData; // data item
public Link next; // next link in list
// -------------------------------------------------------------
public Link(long d) // constructor
{
dData = d;
next = null;
}
// -------------------------------------------------------------
public void displayLink() // display this link
{
System.out.print(dData + " ");
}
// -------------------------------------------------------------
} //End Link Class
My App class:
public class CircularLinkListApp {
public static void main(String[] args) {
CircularList theList = new CircularList(); // make new list
theList.insert(2); // insert four items
theList.insert(4);
theList.insert(6);
theList.insert(8);
theList.displayList(); // display list
while( !theList.isEmpty() ) // until it's empty,
{
Link aLink = theList.delete(); // delete link
System.out.print("Deleted "); // display it
aLink.displayLink();
System.out.println("");
}
theList.displayList(); // display list
} // end of main()
} //End CircularLinkListApp class
It seems that all the problems you are facing are because you did not take the time to think about what you code will have to do on paper. I assure you that if you start drawing your list on paper, with cases for the links and arrows to represent the .next properties it will suddenly become more obvious what behavior you need to code
The first and most obvious problem you will face is your insert method.
this one is fine, even though you could add one more line to make it circular already, it would be better.
This is where problems starts. The exercise ask you to add the link after the current one. It starts well with current.next = newLink; but the next line newLink = current; doesn't do anything for you as it is only assigning the value of current to newLink.
A second problem to take in consideration is that you never check if current don't already have a next link. If it does then your code will effectively detach any and all Links linked to the current link. Find a solution to verify if next is already set and if yes you need to find a way to insert the new link between the two existent links.
I feel that the fact that is it circular scares you. It really shouldn't. Even with only one item you can be circular. In this case current.next will be the same as current that's all. You already have a variable to know how many elements you have so just rely on that to know what to do. In fact, once it will be coded correctly you will never have a .next equal to null. The only exception being when the list is empty current will be equals to null (even though you can avoid this too but it is not necessary)
Here is where you need your list to be circular. You have the right idea but since you are not having a circular list eventually one of the current.next will point at null, hence your original problem. If you fix your circularization and insert the display will work at least the first after the inserts
The assignement is to delete the next item in the list. You start well with storing in a temporary variable the element you are going to delete but you're missing some points :
current = current.next; means that you are loosing your actual current. This is not what you are wanting to do. Firstly your "cursor" should not move. And secondly current.next at this point is the item you want to remove from the list.current.next reference to the item you're removing and attach it to the item appearing after the one you are removing.I hope I've been clear. There are plenty of little quirks that I won't mention primarily because they don't affect functionality, they are just piece of code that could be re-written in a better, clearer way.