Hello, I am taking a Data Structures & Algorithms class in Java this semester an
ID: 3723674 • 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 of the assignment done which dealt with creating a Circular List, but I am confused on how to do the second part of it which is implementing a stack class based on it. If someone could help with creating a stack class based on the circular list that I defined in the first part, that would be great! I have attached the assignment and the code I have so far.
Thank you!
Assignment
Code that I have done so far:
//CList.java
public class CLink {
public long lData;
public CLink next;
public CLink(long value)
{
lData = value;
}
public void displayLink()
{
System.out.print(lData + " ");
}
}
//CLinkedList.java
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;
}
}
//CircularApp.java
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");
}
}
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 e 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
public class Stack {
private Node EOS;
private int count = 0;
public Stack() {
EOS = new Node(0);
EOS.next = EOS;
}
public void push(long j) {
Node newNode = new Node(j);
Node tmp = EOS.next;
EOS.next = newNode;
newNode.next = tmp;
count++;
}
public Long pop() {
if (isEmpty()) {
return null;
} else {
count--;
Node node = EOS.next;
EOS.next = node.next;
return node.iData;
}
}
public Long peek() {
if (isEmpty()) {
return null;
} else {
Node node = EOS.next;
return node.iData;
}
}
public boolean isEmpty() {
return (count == 0);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node p = EOS.next;
while (p != EOS) {
sb.append(p).append(" ");
p = p.next;
}
return sb.toString();
}
private static class Node {
public long iData;
public Node next;
public Node(long id) {
iData = id;
}
@Override
public String toString() {
return "<" + iData + ">";
}
}
}
The second part basically asks to implement a stack using a circular linked list.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.