In this assignment, we’ll build three classes that will implement a List, a Stac
ID: 3838481 • Letter: I
Question
In this assignment, we’ll build three classes that will implement a List, a Stack, and a Queue using Nodes and references rather than arrays. The Stack and Queue will inherit from the List (a linked list) class, and so these subclasses will be rather short. Then, build a simple LinkedListException class that will be thrown in place of RuntimeExceptions whenever exceptional or error situations occur. The inheritance hierarchy we are going to implement is depicted below.
Note: Throughout this document, we will usually refer to the List implementation using Nodes and references (i.e., as a linked list) as “List”. However, you should not confuse this with the Java built-in interface List, which has the same name. At this point, it won’t be an issue; it’s just something to keep in mind in the future.
The List Class
In this section, we describe the List data structure in detail. Once we've built a List superclass, building two new classes that extend list will be trivial in comparison.
Data
Node head = null; //the start of the linked list
Use no other instance variables here in the List class (the phrase "use no other instance variables" does not refer to the inner class Node, which is structured as we saw in Savitch): No int size or Node tail, etc.
You probably will implement Node as an inner class (it's a really good idea to).
Methods
public void insert(Object next, int index) (15-30 LOC):
Make a new node that holds the Object “next”, and insert this at the position specified by index
Divide this method into sections/cases using an if:
If adding to an empty list (changes head) { }
else if adding to a single element list (changes head) {}
else if adding to a populated list (n>=2)
In each case above, note that the following subcases exist:
Adding to the head of the list (changes head)
Adding to the body or the tail of the list (not head)
The cases above exist because of the increased complexity involved when implementing a linked list, but essentially reduce to determining “do I change head? Or a node indirectly attached to head?” Note that not all subcases apply to each outer case; for example, you don’t worry about adding to the body or tail of a list if your adding to an empty list (the first outer case). Read chapter 15 for more details on this.
public Object remove(int index) (15-30 LOC):Find and delete the node at the position specified by indexNote that this method, like add() above, has the following cases:
Deleting on an empty list
Deleting on a single element list (head only)
Deleting on a populated list (n>=2)
And, just like above, there are the following subcases:
Deleting the head of the list (changes head)
Deleting from the body or tail of the list (no changes to head)
The cases above exist due to the complexity of correctly managing a list of nodes and a head pointer. Note your software will not provide for all (3*2==6) cases, since some subcases don’t apply to their enclosing (outer) case. For example, if you’re deleting from a single element list (head only), then you don’t have to worry about deleting from the body or tail (as this subcase doesn’t exist).
public void append(Object next): Adds next to the end of the list.
public void delete(int index): Note that delete is the same as remove but has no return value.
public int size(): A standard accessor
public String toString(): Enumerate your list and return this enumeration as a String.
public boolean isEmpty(): Returns true if empty, false otherwise
public int indexOf(Object target): A sequential search that returns the index if found or -1 if not found
The Stack Subclass
In this section, we’ll build a structure that functions like a Stack externally, but is built on top of nodes and pointers internally. Since we’ll be extending the List superclass, we only have to provide a few functions (push, pop) that redirect to superclass functions(add, remove) and so this class will be quite short. When you’ve finished this class, test it using driver software.
Data
None when inheriting from List.
Methods
public boolean isEmpty(): Returns true if empty, false otherwise
public void push(Object next):
Inserts to the beginning of the list
Consider using your superclass methods here rather than implementing push
public Object pop():
Removes from the beginning of the list
Consider using your superclass methods here rather than building pop by hand
public static void main(String[] args): A driver to test your stack – see below for more information.
The Queue Subclass
Now, we’ll turn our attention to building a Queue. Remember when we used to cut and paste code and logic, then make subtle changes to it to build our new class? Instead, we’ll use inheritance here, automate the copy-and-paste, and just focus on implementing the few methods that differ in our subclass (enqueue(), dequeue()). When you’re done with this class, test it using driver software.
Data
None when inheriting from List.
Methods
public boolean isEmpty(): Returns true if empty, false otherwise
public void enqueue(Object next): Inserts to the beginning of the list
public Object dequeue(): Removes from the end of the list
public static void main(String[] args): A driver to test your stack – see below for more information.
Stack and Queue Methods to Override
What happens when you inherit from a class, but you only want 70% of the parent class functionality? Sometimes you can inherit and override to address this, which we will do here, but do note that this is a warning flag and should make you investigate other design options instead. Its known that our use of inheritance here is somewhat hackneyed - the “is a” relationship is being stretched almost to a breaking point with our use of Stacks and Queues which are Lists. Even conceptually, we can all agree that a Stack is not a List and then some (complete inheritance), but rather a List with limitations (partial inheritance). We’ll address this with an industry grade solution (Collections in Java) later in this class, but for today, we need to add some “hacks” to our code to block the client from using our Stacks & Queues incorrectly. Whenever you’re hacking rather than adding, you’re violating a major Object-Oriented design principle, but we’ll accept these limitations for today and notice how quickly one can build a Stack or Queue given a List to start from. This reuse can be accomplished using Composition here; another strong alternative to overfitting inheritance. To “fix” our subclasses, we must:
Override insert() from the superclass to simply call push() or enqueue() without using the index.
Override remove() from the superclass to call pop() or dequeue() without using the index.
Do we need to override isEmpty()? indexOf()? Anything else?
In cases where parent methods cannot or should not work in the child class and cannot be redirected to a child class' analogue (e.g., delete() in Stack, insert() in Stack and Queue, size() in Stack and Queue), you should override the parent method to make it throw an exception. (You may have to go back and change the List class so it declares the exception class.) This will prevent the user of the child class from improperly using a parent-class method that shouldn't exist for the child class' ADT.
The LinkedListException Class
This class should be under 15 lines of executable code and is an exercise in inheriting from classes provided to you by the Java API. Your class should have only two methods (both constructors) and no data items; see the slides on exceptions for an example of such a class. Throw this exception when an error or exceptional situation occurs in your code, such as a pop() on an empty stack.
Explanation / Answer
--------------------------------------
Node.java
class Node
{
protected int data;
protected Node link;
public Node()
{
link = null;
data = 0;
}
public Node(int d,Node n)
{
data = d;
link = n;
}
public void setLink(Node n)
{
link = n;
}
public void setData(int d)
{
data = d;
}
public Node getLink()
{
return link;
}
public int getData()
{
return data;
}
}
-------------------------------
LinkedList.java
import java.util.*;
class LinkedList
{
protected Node start;
public LinkedList()
{
start = null;
}
public boolean isEmpty()
{
return start == null;
}
public void insert(int val , int index) // d
{
Node nptr = new Node(val, null);
if (isEmpty())
{
start = nptr;
return;
} else if(index == 1) {
nptr.setLink(start);
start = nptr;
return;
}
Node ptr = start;
index = index - 1 ;
int i=1;
while (ptr != null)
{
if (i == index)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
i++;
}
}
public void remove(int index)
{
if (index == 1)
{
start = start.getLink();
return ;
}
Node ptr = start;
index = index - 1 ;
int i=1;
while (ptr != null)
{
if (i == index)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
i++;
}
}
public int getSize()
{
int total = 0;
if(isEmpty()) {
return total;
}
Node ptr = start;
total++;
while (ptr != null)
{
total++;
ptr = ptr.getLink();
}
return total;
}
public int getFromPos(int index)
{
if (isEmpty())
{
return -1;
} else if(index == 1) {
return start.getData();
}
Node ptr = start;
int i=1;
while (ptr != null)
{
if (i == index)
{
return ptr.getData();
}
ptr = ptr.getLink();
i++;
}
return -1;
}
public void display()
{
System.out.print(" Linked List = ");
if (isEmpty())
{
System.out.print("empty ");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}
----------------------------------
Stack.java
import java.util.*;
class Stack extends LinkedList
{
public Stack()
{
start = null;
}
public void push(int val)
{
insert(val, getSize());
}
public void pop()
{
if (isEmpty() )
throw new NoSuchElementException("Empty stack is there") ;
remove(getSize() - 1);
}
}
---------------------------------------
Queue.java
import java.util.*;
class Queue extends LinkedList
{
public Queue()
{
start = null;
}
public void push(int val)
{
insert(val, getSize());
}
public void pop()
{
if (isEmpty() )
throw new NoSuchElementException("Empty stack is there") ;
remove(1);
}
}