Java Linked list.(PLEASE INCLUDE A TESTER PROGRAM FOR THE OUT PUT and read the q

Question

Java Linked list.(PLEASE INCLUDE A TESTER PROGRAM FOR THE OUT PUT and read the question carefully, Thank you.)

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 + " --> "; }
}

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().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;
}

}

Exercise 1 In class, we wrote an implementation for a Stack class using an ArrayList 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

package com.java2novice.algos;

import java.util.Arrays;

public class MyArrayList {

private Object[] myStore;
private int actSize = 0;

public MyArrayList(){
myStore = new Object[10];
}

public Object get(int index){
if(index < actSize){
return myStore[index];
} else {
throw new ArrayIndexOutOfBoundsException();
}
}

public void add(Object obj){
if(myStore.length-actSize <= 5){
increaseListSize();
}
myStore[actSize++] = obj;
}

public Object remove(int index){
if(index < actSize){
Object obj = myStore[index];
myStore[index] = null;
int tmp = index;
while(tmp < actSize){
myStore[tmp] = myStore[tmp+1];
myStore[tmp+1] = null;
tmp++;
}
actSize--;
return obj;
} else {
throw new ArrayIndexOutOfBoundsException();
}

}

public int size(){
return actSize;
}

private void increaseListSize(){
myStore = Arrays.copyOf(myStore, myStore.length*2);
System.out.println(" New length: "+myStore.length);
}

public static void main(String a[]){
MyArrayList mal = new MyArrayList();
mal.add(new Integer(2));
mal.add(new Integer(5));
mal.add(new Integer(1));
mal.add(new Integer(23));
mal.add(new Integer(14));
for(int i=0;i<mal.size();i++){
System.out.print(mal.get(i)+" ");
}
mal.add(new Integer(29));
System.out.println("Element at Index 5:"+mal.get(5));
System.out.println("List size: "+mal.size());
System.out.println("Removing element at index 2: "+mal.remove(2));
for(int i=0;i<mal.size();i++){
System.out.print(mal.get(i)+" ");
}
}
}

public class StackArray<T> implements Stack<T> {

private T[] arr;

private int total;

public StackArray()
{
arr = (T[]) new Object[2];
}

private void resize(int capacity)
{
T[] tmp = (T[]) new Object[capacity];
System.arraycopy(arr, 0, tmp, 0, total);
arr = tmp;
}

public StackArray<T> push(T ele)
{
if (arr.length == total) resize(arr.length * 2);
arr[total++] = ele;
return this;
}

public T pop()
{
if (total == 0) throw new java.util.NoSuchElementException();
T ele = arr[--total];
arr[total] = null;
if (total > 0 && total == arr.length / 4) resize(arr.length / 2);
return ele;
}

@Override
public String toString()
{
return java.util.Arrays.toString(arr);
}

}
public class StackLinkedList<T> implements Stack<T> {

private int total;

private Node first;

private class Node {
private T ele;
private Node next;
}

public StackLinkedList() { }

public StackLinkedList<T> push(T ele)
{
Node current = first;
first = new Node();
first.ele = ele;
first.next = current;
total++;
return this;
}

public T pop()
{
if (first == null) new java.util.NoSuchElementException();
T ele = first.ele;
first = first.next;
total--;
return ele;
}

@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
Node tmp = first;
while (tmp != null) {
sb.append(tmp.ele).append(", ");
tmp = tmp.next;
}
return sb.toString();
}

}
Stack<String> greeting = new StackArray<>();

greeting.push("!").push("World").push("Hello, ");

System.out.println(greeting.pop() + greeting.pop() + greeting.pop()); // Hello, World!

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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