Hello, I am taking a Data Structures & Algorithms class in Java this semester an
ID: 3723110 • 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, but I am confused on how to the second part of it which is implementing a stack class based on it. Also, if someone could look over the first part of the assignment (circular linked list) just to make sure I did it correctly that would be great, feel free to modify it if needed. I attached the assignment and the code I have so far.
Thank you!
Assignment
Code that I have done for Part 1:
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);
newLink.next = current.next;
current.next = newLink;
}
nItems++;
}
public CLink find(long value)
{
for (int i = 0; i < nItems; i++)
{
if (current.lData == value)
{
System.out.println("Found " + value);
return current;
}
else
step();
}
System.out.println("Couldn't find " + value + ".");
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;
current.next = current.next.next;
nItems--;
return temp;
}
}
public CLink peek()
{
return current;
}
public void display()
{
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 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.display();
theList.delete();
theList.display();
theList.delete();
theList.display();
}
}
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
your first part is correct, there is no problem in that
I have implemented stack
package chegg;
class LinkedList {
private Node first; // ref to first link on list
/**
* LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position
*/
public void insertFirst(int data) {
Node newNode = new Node(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
/**
* Deletes first Node
*/
public Node deleteFirst()
{
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
first = first.next; // delete first Node (make first point to second node)
return tempNode; // return tempNode (i.e. deleted Node)
}
/**
* Display LinkedList
*/
public void displayLinkedList() {
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don't find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();
}
}
/**
* For implementing stack using using LinkedList- This StackLinkedList
* class internally maintains LinkedList reference in java.
*/
.......................................................................................................................................................................................
package chegg;
class LinkedListEmptyException extends RuntimeException{
public LinkedListEmptyException(){
super();
}
public LinkedListEmptyException(String message){
super(message);
}
}
........................................................................................................................................................................................
package chegg;
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
........................................................................................................................................................................................
package chegg;
class StackEmptyException extends RuntimeException {
public StackEmptyException(){
super();
}
public StackEmptyException(String message){
super(message);
}
}
........................................................................................................................................................................................
package chegg;
class StackLinkedList{
LinkedList linkedList = new LinkedList(); // creation of Linked List
/**
* Push items in stack, it will put items on top of Stack.
*/
public void push(int value){
linkedList.insertFirst(value);
}
/**
* Pop items in stack, it will remove items from top of Stack.
*/
public void pop() throws StackEmptyException {
try{
linkedList.deleteFirst();
}catch(LinkedListEmptyException llee){
throw new StackEmptyException();
}
}
/**
* Display stack.
*/
public void displayStack() {
System.out.print("Displaying Stack > Top to Bottom : ");
linkedList.displayLinkedList();
}
}
/**
* Main class - To test Stack Implementation Using LinkedList in java
*/
.......................................................................................................................................................................................
package chegg;
import java.util.Scanner;
public class StackImplementationUsingLinkedListExample {
public static void main(String[] args) {
int ch;
StackLinkedList stackLinkedList=new StackLinkedList();
Scanner scan=new Scanner(System.in);
do
{
System.out.println("enter choice 1.insert 2.delete 3.display 4.exit ");
ch=scan.nextInt();
switch(ch)
{
case 1:System.out.println("enter element");
int n=scan.nextInt();
stackLinkedList.push(n);
break;
case 2:stackLinkedList.pop();
System.out.println("element deleted");
break;
case 3:stackLinkedList.displayStack();
break;
case 4:System.exit(0);
default:System.out.println("wrong choice");
}
}while(ch!=4);
}
}
if you have problem in any line of code or code is not running in your IDE then kindly comment. i will fix the problem immediately and please thumbs up my answer ;)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.