Java Only Given a doubly linked list (code provided to you in the lecture note)
ID: 3694939 • Letter: J
Question
Java Only
Given a doubly linked list (code provided to you in the lecture note) implement a Stack and a Queue. You must use the doubly link list class and utilize it as an object in your implementation of the stack and queue. You may edit it and you may also modify it but you must include it as part of your implementation.
Implement a Stack
A Stack is a Last in First Out (LiFO) structure which translates to the processes of outputting the last element which was inputted in the collection. The Stack is based on the process of putting things on top of one another and taking the item on top (think of a stack of papers).
Operations to implement:
push (E): Add an element to the start of the sequence
pop: Remove an element from the start of the sequence
Peek: Return the first element of the sequence without removing it
atIndex(x): Return the element at the given index (x) Or throw an exception if it is out of bound (if you can control the user input then do that instead)
Size: Return the size of the Stack
isEmpty: Boolean, returns true if the Stack is empty
Empty: Empty the Stack
Implement a Queue
A Queue is a First in First Out (FiFO) structure which translates to the processes of outputting the first item inputted into a collection. The Queue is based on the process of waiting in line to get serviced (bank or six flags), where those who arrive first get serviced first.
Operations to implement:
Enqueue/push (E): Add an element to the end of the sequence
Dequeue/pop: Remove an element from the start of the sequence
Front/Peek: Return the first element of the sequence without removing it (what the head is pointing to)
atIndex(x): Return the element at the given index (x) Or throw an exception if it is out of bound (if you can control the user input then do that instead)
Size: Return the size of the Queue
isEmpty: Boolean, returns true if the Queue is empty
Empty: Empty the Queue
Back: Return what the tail is pointing to
DNode.java
public class DNode
{
private Object e; // place holder for the type of object the
//collection is storing
private DNode next; // reference to the next node in the sequence
// of nodes making up the linked list. Remember
// that even though Java passes Objects by value
// an object consisting of reference will behave
// the same as an object passed by reference unless
// a deep copy was made.
private DNode prev;
public DNode (Object e) // Constructor for implementing a single node
{
this.e = e; // The value of the element to be assigned to
// this particular instance of node
this.next = null; // An empty reference since there is no node
// to follow.
this.prev = null;
}
public DNode (Object e, DNode next, DNode prev) // Constructor for implementing a
// node that comes after another
// node
{
this.e = e; // The value of the element to be assigned to
// this particular instance of node
this.next = next; // reference to the subsequent node to follow
this.prev = prev;
}
public void changeNext (DNode next) // Changes the link to the next node
{
this.next = next;
}
public void changePrev (DNode prev) // Changes the link to the next node
{
this.prev = prev;
}
public DNode getNext() // Returns the node next in the sequence
{
return this.next;
}
public Object getValue() // Returns the value a node is holding
{
return this.e;
}
public Boolean hasNext() // Returns a boolean determining regarding
// the status of subsequent nodes after
// the current node
{
return !(this.next.getValue() == null || this.next == null);
}
public Boolean hasprev() // Returns a boolean determining regarding
// the status of subsequent nodes after
// the current node
{
return !(this.prev.getValue() == null || this.prev == null);
}
public void insertAfterNode( Object input)
{
this.changeNext(new DNode (input, this.getNext(), this));
}
public void insertAfterNode (DNode input)
{
this.changeNext(input);
input.changeNext(this.next);
input.changePrev(this);
}
public void insertbeforeNode (DNode input)
{
this.changeNext(input);
}
public void insertBetweenNodes(DNode before, DNode after)
{
this.changeNext(after);
this.changePrev(before);
before.changeNext(this);
after.changePrev(this);
}
public DNode getPrev()
{
return this.prev;
}
}
DoublyLinkedList.java
public class DoublyLinkedList
{
private DNode head;
private DNode tail;
private int size;
public DoublyLinkedList () // construct an empty list
{
this.tail = new DNode (null, null, this.head);
this.head = new DNode (null, this.tail, null);
this.size = 0;
}
public DoublyLinkedList (DNode next) // constructs a list
// out of a single node
{
this.tail = new DNode (null, null, next);
this.head = new DNode (null, next, null);
next.changeNext(this.tail);
next.changePrev(this.head);
this.size = 1;
}
public DoublyLinkedList(Object [] objectArray) // construct a list out of
// an array
{
this.tail = new DNode (null, null, this.head);
this.head = new DNode (null, this.tail, null);
DNode temp = this.head;
for (Object e : objectArray)
{
//Anonomus function
new DNode (e, temp.getNext(),temp).insertBetweenNodes(temp, temp.getNext());
temp = temp.getNext();
this.size += 1;
}
}
public void addToFrontofList (Object toAdd) // Appends the begining
// of the list
{
DNode temp = new DNode (toAdd, this.head.getNext(), this.head);
this.head.getNext().changePrev(temp);
this.head.changeNext(temp);
this.size += 1;
}
public void addToendofList (Object toAdd) // appends the end of the list
// with a node
{
DNode temp = new DNode (toAdd, this.tail, this.tail.getPrev());
this.tail.getPrev().changeNext(temp);
this.tail.changePrev(temp);
this.size += 1;
}
public void insertAfterNode(DNode current, Object input)// Inserts a new
// a new node after
// current node
{
current.insertAfterNode(input);
this.size += 1;
}
public int getSize() // returns the size of the list
{
return this.size;
}
@Override
public String toString()
{
String result = "";
for (DNode temp = this.head.getNext(); temp.hasNext(); temp = temp.getNext())
{
result += temp.getValue();
result += " -> ";
}
result += "End of list";
return result;
}
}
Explanation / Answer
DNode.java
public class DNode
{
private Object e; // place holder for the type of object the
//collection is storing
private DNode next; // reference to the next node in the sequence
// of nodes making up the linked list. Remember
// that even though Java passes Objects by value
// an object consisting of reference will behave
// the same as an object passed by reference unless
// a deep copy was made.
private DNode prev;
public DNode (Object e) // Constructor for implementing a single node
{
this.e = e; // The value of the element to be assigned to
// this particular instance of node
this.next = null; // An empty reference since there is no node
// to follow.
this.prev = null;
}
public DNode (Object e, DNode next, DNode prev) // Constructor for implementing a
// node that comes after another
// node
{
this.e = e; // The value of the element to be assigned to
// this particular instance of node
this.next = next; // reference to the subsequent node to follow
this.prev = prev;
}
public void changeNext (DNode next) // Changes the link to the next node
{
this.next = next;
}
public void changePrev (DNode prev) // Changes the link to the next node
{
this.prev = prev;
}
public DNode getNext() // Returns the node next in the sequence
{
return this.next;
}
public Object getValue() // Returns the value a node is holding
{
return this.e;
}
public Boolean hasNext() // Returns a boolean determining regarding
// the status of subsequent nodes after
// the current node
{
//return !(this.next.getValue() == null || this.next == null);
if(this.next!=null) return true; else return false;
}
public Boolean hasPrev() // Returns a boolean determining regarding
// the status of subsequent nodes after
// the current node
{
//return !(this.prev.getValue() == null || this.prev == null);
if(this.prev!=null) return true; else return false;
}
public void insertAfterNode( Object input)
{
this.changeNext(new DNode (input, this.getNext(), this));
}
public void insertAfterNode (DNode input)
{
this.changeNext(input);
input.changeNext(this.next);
input.changePrev(this);
}
public void insertbeforeNode (DNode input)
{
this.changeNext(input);
}
public void insertBetweenNodes(DNode before, DNode after)
{
this.changeNext(after);
this.changePrev(before);
before.changeNext(this);
after.changePrev(this);
}
public DNode getPrev()
{
return this.prev;
}
}
DoublyLinkedList.java
public class DoublyLinkedList
{
private DNode head;
private DNode tail;
private int size;
public DoublyLinkedList () // construct an empty list
{
this.tail = new DNode (null, null, this.head);
this.head = new DNode (null, this.tail, null);
this.size = 0;
}
public DoublyLinkedList (DNode next) // constructs a list
// out of a single node
{
this.tail = new DNode (null, null, next);
this.head = new DNode (null, next, null);
next.changeNext(this.tail);
next.changePrev(this.head);
this.size = 1;
}
public DoublyLinkedList(Object [] objectArray) // construct a list out of
// an array
{
this.tail = new DNode (null, null, this.head);
this.head = new DNode (null, this.tail, null);
DNode temp = this.head;
for (Object e : objectArray)
{
//Anonomus function
new DNode (e, temp.getNext(),temp).insertBetweenNodes(temp, temp.getNext());
temp = temp.getNext();
this.size += 1;
}
}
public void addToFrontofList (Object toAdd) // Appends the begining
// of the list
{
DNode temp = new DNode (toAdd, this.head.getNext(), this.head);
this.head.getNext().changePrev(temp);
this.head.changeNext(temp);
this.size += 1;
}
public void addToendofList (Object toAdd) // appends the end of the list
// with a node
{
DNode temp = new DNode (toAdd, this.tail, this.tail.getPrev());
if(this.tail.hasPrev())
{
this.tail.getPrev().changeNext(temp);
this.tail.changePrev(temp);
this.size += 1;
}
else addToFrontofList(toAdd);
}
public void insertAfterNode(DNode current, Object input)// Inserts a new
// a new node after
// current node
{
current.insertAfterNode(input);
this.size += 1;
}
public Object getValue(int index)
{
if(size>0)
{
if(index==0)
return head;
else if(index>0 && index < size)
{
DNode t=head;
int i=0;
while(i<index)
{
t=t.getNext();
i++;
}
return t.getValue();
}
else return null;
}
else return null;
}
public void removeFirst()
{
if(this.size>=1)
{
DNode h=head.getNext().getNext();
head.changeNext(h);
this.size -= 1;
}
}
public void removeLast()
{
if(this.size>=1)
{
DNode t=tail;
if(tail.hasPrev())
{
tail.getPrev().getPrev().changeNext(tail);
this.size -= 1;
}
}
}
public int getSize() // returns the size of the list
{
return this.size;
}
public DNode getHead() // returns the head of the list
{
return this.head;
}
@Override
public String toString()
{
String result = "";
for (DNode temp = this.head.getNext(); temp.hasNext(); temp = temp.getNext())
{
result += temp.getValue();
result += " -> ";
}
result += "End of list";
return result;
}
}
Stack.java
class Stack
{
DoublyLinkedList list;
public Stack()
{
list=new DoublyLinkedList();
}
public void push(Object o)
{
list.addToFrontofList(o);
}
public void pop()
{
list.removeFirst();
}
public Object peek()
{
return list.getValue(0);
}
public Object atIndex(int i)
{
return list.getValue(i);
}
public int size()
{
return list.getSize();
}
public String toString()
{
String result = "Top-> ";
for (DNode temp = this.list.getHead().getNext(); temp.hasNext(); temp = temp.getNext())
{
result += temp.getValue();
result += " -> ";
}
result += "Bottom of Stack";
return result;
}
}
Queue.java
class Queue
{
DoublyLinkedList list;
public Queue()
{
list=new DoublyLinkedList();
}
public void enqueue(Object o)
{
list.addToFrontofList(o);
}
public void dequeue()
{
list.removeLast();
}
public Object peek()
{
return list.getValue(0);
}
public Object atIndex(int i)
{
return list.getValue(i);
}
public int size()
{
return list.getSize();
}
public String toString()
{
String result = "End -> ";
for (DNode temp = this.list.getHead().getNext(); temp.hasNext(); temp = temp.getNext())
{
result += temp.getValue();
result += " -> ";
}
result += " Front";
return result;
}
}
MainProgram.java
public class MainProgram
{
public static void main(String a[])
{
Stack s=new Stack();
s.push(10);
s.push(9);
s.push(8);
s.pop();
System.out.println(s);
Queue q=new Queue();
q.enqueue(10);
q.enqueue(12);
q.enqueue(13);
q.dequeue();
System.out.println(q);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.