public class LinkedList { private Node front; //private int count; //private Nod

Question

public class LinkedList {
   private Node front;
   //private int count;
   //private Node end;

   public LinkedList(Node f ) {
       front = f;

   }

public LinkedList() {
   front = null;

}

public void addToFront(String d) {
   Node n = new Node(d, front);
   front = n;
}

public boolean isEmpty() {
   if(front == null)
       return true;
   else
       return false;
}

public void clear() {
   front = null;

}

public String getFrontData() {
   return front.getData();

}

public Node getFrontNode() {
   return front;

}

public String toString() {
   String ts = "[";
   Node cur = front;
   while(cur != null) {
       ts += cur;
       cur = cur.getNext();
   }
   return ts + "]";
}

public int size() {
   int count = 0;
   Node cur = front;
   while(cur != null) {
       count++;
       cur = cur.getNext();
   }
   return count;
}

public void removeFront() {
   if(!isEmpty())
       front = front.getNext();
  
   // else
   //   System.out.println(No front to remove!);

}

public void addToEnd(String d) {
   Node n = new Node(d, null);
   if(isEmpty())
       front = n;
   else {
       Node cur = front;
       while(cur.getNext() != null)
           cur = cur.getNext();
       cur.setNext(n);
   }
}

public void removeLast() {
   if(!isEmpty()) {
       if(front.getNext() == null)
           front = null;
       else {
           Node cur = front;
           while(cur.getNext() != null)
               cur = cur.getNext();
           cur.setNext(null);
       }
   //} else { System.out.println(No end to remove!);
   }
}

public int contains(String d) {
   Node cur = front;
   boolean found = false;
   int index = -1;

   while(cur != null && !found) {
       index++;
       if(cur.getData().equals(d))
           found = true;
       cur = cur.getNext();
   }
   if(!found)
       index = -1;
   return index;
}

public void add(int index, String d) {
   if(index >= 0 && index <= size() ) {
       if(index == 0)
           addToFront(d);
       else {
           Node cur = front;
           for(int i=0; i<index-1; i++)
               cur = cur.getNext();
           Node n = new Node(d, cur.getNext());
           cur.setNext(n);
}
   }
   //else { System.out.println(index out of bounds!); }
}

public void remove(int index) {
   if(index >= 0 && index <= size() ) {
       if(index == 0)
           removeFront();
       else if(index == size()-1)
           removeLast();
       else {
           Node cur = front;
           for(int i=0; i<index-1; i++)
               cur = cur.getNext();
           cur.setNext(cur.getNext().getNext());
       }
   }
   //else { System.out.println(index out of bounds!); }
}

public Node getNode(int index) {
   Node cur = null;
   if(index >= 0 && index <= size() ) {
       if(index == 0)
           cur = front;
       else {
           cur = front;
           for(int i=0; i<index; i++)
               cur = cur.getNext();
       }
   } // else { System.out.println(index out of bounds!); }
   return cur;
}

public void addAll(LinkedList other) {
   Node cur = other.getFrontNode();
   while(cur != null) {
       addToEnd(cur.getData());
       cur = cur.getNext();
   }
}

public static LinkedList merge(LinkedList first, LinkedList second) {
   LinkedList result = new LinkedList();

   Node cur = first.getFrontNode();
   while(cur != null) {
       result.addToEnd(cur.getData());
       cur = cur.getNext();
   }

   cur = second.getFrontNode();
   while(cur != null) {
       result.addToEnd(cur.getData());
       cur = cur.getNext();
   }
   return result;
}

public LinkedList subList(int start, int end) {
   LinkedList result = new LinkedList();
   if(!(start >= end || start < 0 || start > size() || end >= size() )) {
       Node cur = getFrontNode();
       for(int i=0; i<start; i++) {
           cur = cur.getNext();
       }
       for(int i=start; i<=end; i++) {
           addToEnd(cur.getData());
           cur = cur.getNext();
       }
   }
   return result;
}

public static LinkedList union(LinkedList first, LinkedList second) {
   LinkedList result = new LinkedList();
   Node cur = first.getFrontNode();
   while(cur != null) {
       result.addToEnd(cur.getData());
       cur = cur.getNext();
   }

   cur = second.getFrontNode();
   while(cur != null) {
       if(result.contains(cur.getData()) == -1)
           result.addToEnd(cur.getData());
       cur = cur.getNext();
   }

   return result;
}

public static LinkedList intersection(LinkedList first, LinkedList second) {
   LinkedList result = new LinkedList();
   Node cur = first.getFrontNode();
   while(cur != null) {
       if(second.contains(cur.getData()) != -1)
           result.addToEnd(cur.getData());
       cur = cur.getNext();
   }

   return result;
}

}

public class Node {
   private String data;
   private Node next;

   public Node(String d, Node n ) {
       data = d;
       next = n;
   }
   // The usual get/set methods, plus toString()
   public void setData(String d) { data = d; }
   public void setNext(Node n) { next = n; }
   public String getData() { return data; }
   public Node getNext() { return next; }
   public String toString() { return data + " --> "; }
}

In class, we wrote an implementation for a Stack class using an ArayList to store the underlying data. Write your own Stack class (Stack.java) that uses a LinkedList to store the underlying (String) data. Your implementation should have (at least) a constructor, a push method, a pop method, and a peek method. The LinkedList class you use should be based off of the version we wrote in class (i.e., not using a Java standard library version).-

Explanation / Answer

CODE

import java.util.Scanner;

public class Stack_LinkedList {

public static LinkedList s;

public static void main(String[] args) {

s = new LinkedList();

Scanner in = new Scanner(System.in);

while(true)

{

System.out.println("MENU");

System.out.println("1:Push");

System.out.println("2:Pop");

System.out.println("3:Peek");

System.out.println("4:Size");

System.out.println("5:Print");

System.out.println("6:Quit");

System.out.println("Select your option");

int option = in.nextInt();

switch (option) {

case 1:

System.out.println("Enter the string to push");

String t = in.next();

push(t);

break;

case 2:

pop();

break;

case 3:

if(peek() != null)

System.out.println(peek());

break;

case 4:

System.out.println("Size of stack is "+s.size());

break;

case 5:

System.out.println(s.toString());

break;

case 6:

System.out.println("Exiting");

System.exit(0);

break;

}

}

}

public static void pop() {

if (s.isEmpty())

System.out.println("Stack is empty");

else {

System.out.println("Removing " + s.getFrontData());

s.removeFront();

}

}

public static void push(String data) {

System.out.println("Adding " + data);

s.addToFront(data);

}

public static String peek() {

if (s.isEmpty()) {

System.out.println("Stack is empty");

return null;

} else

return s.getFrontData();

}

}

class LinkedList {

private Node front;

// private int count;

// private Node end;

public LinkedList(Node f) {

front = f;

}

public LinkedList() {

front = null;

}

public void addToFront(String d) {

Node n = new Node(d, front);

front = n;

}

public boolean isEmpty() {

if (front == null)

return true;

else

return false;

}

public void clear() {

front = null;

}

public String getFrontData() {

return front.getData();

}

public Node getFrontNode() {

return front;

}

public String toString() {

String ts = "[";

Node cur = front;

while (cur != null) {

ts += cur;

cur = cur.getNext();

}

return ts + "]";

}

public int size() {

int count = 0;

Node cur = front;

while (cur != null) {

count++;

cur = cur.getNext();

}

return count;

}

public void removeFront() {

if (!isEmpty())

front = front.getNext();

// else

// System.out.println(No front to remove!);

}

public void addToEnd(String d) {

Node n = new Node(d, null);

if (isEmpty())

front = n;

else {

Node cur = front;

while (cur.getNext() != null)

cur = cur.getNext();

cur.setNext(n);

}

}

public void removeLast() {

if (!isEmpty()) {

if (front.getNext() == null)

front = null;

else {

Node cur = front;

while (cur.getNext() != null)

cur = cur.getNext();

cur.setNext(null);

}

// } else { System.out.println(No end to remove!);

}

}

public int contains(String d) {

Node cur = front;

boolean found = false;

int index = -1;

while (cur != null && !found) {

index++;

if (cur.getData().equals(d))

found = true;

cur = cur.getNext();

}

if (!found)

index = -1;

return index;

}

public void add(int index, String d) {

if (index >= 0 && index <= size()) {

if (index == 0)

addToFront(d);

else {

Node cur = front;

for (int i = 0; i < index - 1; i++)

cur = cur.getNext();

Node n = new Node(d, cur.getNext());

cur.setNext(n);

}

}

// else { System.out.println(index out of bounds!); }

}

public void remove(int index) {

if (index >= 0 && index <= size()) {

if (index == 0)

removeFront();

else if (index == size() - 1)

removeLast();

else {

Node cur = front;

for (int i = 0; i < index - 1; i++)

cur = cur.getNext();

cur.setNext(cur.getNext().getNext());

}

}

// else { System.out.println(index out of bounds!); }

}

public Node getNode(int index) {

Node cur = null;

if (index >= 0 && index <= size()) {

if (index == 0)

cur = front;

else {

cur = front;

for (int i = 0; i < index; i++)

cur = cur.getNext();

}

} // else { System.out.println(index out of bounds!); }

return cur;

}

public void addAll(LinkedList other) {

Node cur = other.getFrontNode();

while (cur != null) {

addToEnd(cur.getData());

cur = cur.getNext();

}

}

public static LinkedList merge(LinkedList first, LinkedList second) {

LinkedList result = new LinkedList();

Node cur = first.getFrontNode();

while (cur != null) {

result.addToEnd(cur.getData());

cur = cur.getNext();

}

cur = second.getFrontNode();

while (cur != null) {

result.addToEnd(cur.getData());

cur = cur.getNext();

}

return result;

}

public LinkedList subList(int start, int end) {

LinkedList result = new LinkedList();

if (!(start >= end || start < 0 || start > size() || end >= size())) {

Node cur = getFrontNode();

for (int i = 0; i < start; i++) {

cur = cur.getNext();

}

for (int i = start; i <= end; i++) {

addToEnd(cur.getData());

cur = cur.getNext();

}

}

return result;

}

public static LinkedList union(LinkedList first, LinkedList second) {

LinkedList result = new LinkedList();

Node cur = first.getFrontNode();

while (cur != null) {

result.addToEnd(cur.getData());

cur = cur.getNext();

}

cur = second.getFrontNode();

while (cur != null) {

if (result.contains(cur.getData()) == -1)

result.addToEnd(cur.getData());

cur = cur.getNext();

}

return result;

}

public static LinkedList intersection(LinkedList first, LinkedList second) {

LinkedList result = new LinkedList();

Node cur = first.getFrontNode();

while (cur != null) {

if (second.contains(cur.getData()) != -1)

result.addToEnd(cur.getData());

cur = cur.getNext();

}

return result;

}

}

class Node {

private String data;

private Node next;

public Node(String d, Node n) {

data = d;

next = n;

}

// The usual get/set methods, plus toString()

public void setData(String d) {

data = d;

}

public void setNext(Node n) {

next = n;

}

public String getData() {

return data;

}

public Node getNext() {

return next;

}

public String toString() {

return data + " --> ";

}

}

SAmple output

MENU
1:Push
2:Pop
3:Peek
4:Size
5:Print
6:Quit
Select your option
1
Enter the string to push
A
Adding A
MENU
1:Push
2:Pop
3:Peek
4:Size
5:Print
6:Quit
Select your option
5
[A --> ]
MENU
1:Push
2:Pop
3:Peek
4:Size
5:Print
6:Quit
Select your option
2
Removing A
MENU
1:Push
2:Pop
3:Peek
4:Size
5:Print
6:Quit
Select your option
4
Size of stack is 0
MENU
1:Push
2:Pop
3:Peek
4:Size
5:Print
6:Quit
Select your option

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.