Hello, I am taking a Data Structures & Algorithms class in Java this semester an
ID: 3723478 • Letter: H
Question
Hello,
I am taking a Data Structures & Algorithms class in Java this semester and we are currently working on Linked Lists. I was able to get the first part and second parts of the assignment done, but I have an error on the second part where I need to create a stack class based on the circular list. I am getting a message that says problem1.CLink@70dea4e problem1.CLink@70dea4e problem1.CLink@70dea4e null . I do not know what to do and this assignment is due tomorrow so some help would be appreaciated. I have attached the assignment and the code I have so far.
Thank you!
Assignment
Code that I have done so far:
public class CLink {
public long lData;
public CLink next;
public CLink(long value)
{
lData = value;
}
public void displayLink()
{
System.out.print(lData + " ");
}
}
public class CLinkedList {
private CLink current;
private int nItems; // keeps track of length of the list
public CLinkedList()
{
current = null;
nItems = 0;
}
public boolean isEmpty()
{
return current == null;
}
public long getItems()
{
return nItems;
}
public void step()
{
current = current.next;
}
public void insert(long value) // inserts new link after current link
{
if (isEmpty())
{
current = new CLink(value);
current.next = current;
}
else
{
CLink newLink = new CLink(value);
CLink temp = current.next;
while (temp.next != current) {
temp = temp.next;
}
newLink.next = current;
temp.next = newLink;
}
nItems++;
}
public CLink find(long value)
{
for (int i = 0; i < nItems; i++)
{
if (current.lData == value)
{
return current;
}
else
step();
}
return null;
}
public CLink delete()
{
if (isEmpty())
{
System.out.println("List is empty.");
return null;
}
else if (nItems == 1)
{
current = null;
nItems = 0;
return null;
}
else
{
CLink temp = current.next;
while (temp.next != current) {
temp = temp.next;
}
temp.next = current.next;
current = current.next;
nItems--;
return temp;
}
}
public CLink peek()
{
return current;
}
public void displayList()
{
System.out.print("Circular List (from current): ");
CLink index = current;
for (int i = 0; i < nItems; i++)
{
System.out.print(index.lData + " ");
index = index.next;
}
System.out.println("");
}
public boolean deleteKey(long key) {
if (current == null)
return false;
if (current.lData == key) {
delete();
return true;
} else {
CLink temp = current, prev = null;
for (int i = 0; i < nItems; i++) {
if (temp.lData == key) {
prev.next = temp.next;
nItems--;
return true;
}
prev = temp;
temp = temp.next;
}
}
return false;
}
}
public class CircularApp {
public static void main(String[] args) {
CLinkedList theList = new CLinkedList();
theList.insert(1);
theList.insert(2);
theList.insert(3);
theList.insert(4);
theList.displayList();
theList.delete();
theList.displayList();
theList.deleteKey(3);
theList.displayList();
CLink f = theList.find(3);
if (f != null) {
System.out.print("Found ");
f.displayLink();
System.out.println();
}
else
System.out.println("not found");
}
}
public class Cstack {
private CLinkedList cl;
public Cstack () {
cl = new CLinkedList();
}
public void push (long j) {
cl.insert(j);
}
public CLink pop () {
return cl.delete();
}
public CLink peek () {
return cl.peek();
}
public boolean isEmpty() {
return cl.isEmpty();
}
}
public class Cstackapp {
public static void main(String[] args) {
Cstack thestack = new Cstack();
thestack.push(1);
thestack.push(2);
thestack.push(3);
thestack.push(4);
while (!thestack.isEmpty()) {
CLink value = thestack.pop();
System.out.print(value); // display it
System.out.print(" ");
}
}
}
1. 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 "start" of the list. However, this makes the list less like a real circle and more like an ordinary list that has its end attached to its beginning. Define a class for a singly linked circular list that has no end and 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. Your list should handle insertion, searching and deletion. You may find it convenient if these operations take place one link downstream of the link pointed to by current. (Because the list is a singly linked list, you can't get the upstream link without going all the way around the circle.) You should also be able to display the list. A step() method that moves current along to the next link might come in handy too. Write a driver class to test the circular list. Hint: a) 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. b) 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 · 2. Implement a stack class based on the circular list created in the previous question. Write a driver class to test the circular list based stack.Explanation / Answer
//DeleteKey (key) function is also updated
The problem was with your delete function. In your program it was deleting first node and node updating links properly.
But to implement stack using linked list, the node must be removed and added at last of linked list becase stack must satisfy Last In First Out(LIFO) property.
mean element inserted at last must be removed first.
As I saw your insert function in which you are inserting at last so it is working fine.
I modified your delete function , now it is removing from last. I high lighted my modification with the comment.
And this (problem1.CLink@70dea4e problem1.CLink@70dea4e ) is comming because in stack pop call in main function you are printing CLink instead of CLink.lData
I also modified your find method, Please see comment carefully.
One more change in step method.
1. deleteKey(key) method also had bug that i fixed.
Sample Output
4 3 2 1
Sample Output CircularApp:
Circular List (from current): 1 2 3 4
Circular List (from current): 1 2 3
Circular List (from current): 1 2
not found
Please find the updated classed below.
---------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------
----------------------------------------------------------------------------------
---------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
--------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.