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

Question

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() != 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                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                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                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            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

// Below is the linked stack implementation which uses your version of linked list class LinkedStack { public Node top ; public int size ; /* Constructor */ public LinkedStack() { top = null; size = 0; } /* Function to check if stack is empty */ public boolean isEmpty() { return top == null; } /* Function to get the size of the stack */ public int getSize() { return size; } /* Function to push an element to the stack */ public void push(String value) { Node newNode = new Node (value, null); if (top == null) top = newNode; else { newNode.setNext(top); top = newNode; } size++ ; } /* Function to pop an element from the stack */ public String pop() { if (isEmpty() ){ System.out.println("Underflow Exception") ; return "null"; } Node pointer = top; top = pointer.getNext(); size-- ; return pointer.getData(); } /* Function to check the top element of the stack */ public String peek() { if (isEmpty() ) { System.out.println("Underflow Exception"); return "null"; } return top.getData(); } /* Function to display the status of the stack */ public void display() { System.out.print(" Stack = "); if (size == 0) { System.out.print("Empty "); return ; } Node ptr = top; while (ptr != null) { System.out.print(ptr.getData()+" "); ptr = ptr.getNext(); } System.out.println(); } }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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