Data Structures
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
public class LinkedList<T>
{
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
this.tail = tail; // update tail
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
/**
* Returns if queue is empty
*
* @return boolean if it is empty
*/
public boolean isEmpty() {
return this.head == null;
}
public String toString() {
int count = 0;
String str = "";
for (T e : this) {
str += e + " ";
count++;
}
return "Words count: " + count + ", data: " + str;
}
}
import java.util.*;
/**
* Driver Class
* Tests queue with string, integers, and mixes of Classes and types
*/
class QueueTester {
public static void main(String[] args)
{
// Create iterable Queue of Words
String[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
Queue<String> queue = new Queue<>();
// Enqueuing all words
for (String word: words){
queue.add(word);
System.out.println("Enqueued data: "+ word);
System.out.println(queue);
}
// Dequeuing all words
while (!(queue.isEmpty())){
String del = queue.delete();
System.out.println("Dequeued data: " + del);
System.out.println(queue);
}
}
}
QueueTester.main(null);
/**
* Driver Class
* Tests queue with string, integers, and mixes of Classes and types
*/
class QueueTester2{
public static void main(String[] args)
{
// initializing two queues of ints
int[] set1 = {1, 4, 5, 8};
int[] set2 = {2, 3, 6, 7};
Queue<Integer> Q1 = new Queue<>();
for (int n: set1){
Q1.add(n);
}
Queue<Integer> Q2 = new Queue<>();
for (int n: set2){
Q2.add(n);
}
// printing queues individually
System.out.println("1st Queue");
System.out.println(Q1);
System.out.println("2nd Queue");
System.out.println(Q2);
//initializing new queue for queues to order into one another
Queue<Integer> Q3 = new Queue<>();
while (!(Q1.isEmpty()) || !(Q2.isEmpty())){
// checking if first queue is empty
if (Q1.isEmpty()){
Q3.add(Q2.delete());
}
//checking if second queue is empty
else if(Q2.isEmpty()){
Q3.add(Q1.delete());
}
// checking if the first Q1 val is greater than the first Q2 val
else if (Q1.peek() < Q2.peek()){
Q3.add(Q1.delete());
}
else {
Q3.add(Q2.delete());
}
}
// printing new queue
System.out.println("New Queue");
System.out.println(Q3);
}
}
QueueTester2.main(null);
class ShuffleQ<T> {
public void shuffle(Queue<T> q) {
//initializing a new queue
List<T> newQ = new ArrayList<>();
// Add all elements to newQ
while (!q.isEmpty()) {
newQ.add(q.delete());
}
// Add elements back to q in random order
while (!newQ.isEmpty()) {
// Get random index
int rand = (int) (Math.random() * newQ.size());
q.add(newQ.get(rand));
// Remove element from the new queue
newQ.remove(rand);
}
}
}
/**
* Driver Class
* Tests queue with string, integers, and mixes of Classes and types
*/
class QueueTester3 {
public static void main(String[] args)
{
// Create first queue
int[] set = {1, 2, 3, 4, 5, 6, 7, 8};
Queue<Integer> Q = new Queue<>();
for (int n : set) {
Q.add(n);
}
System.out.println("Sorted Queue: ");
System.out.println(Q);
System.out.println();
// Shuffle queue using shuffleQ
ShuffleQ<Integer> shuffleQ = new ShuffleQ<>();
shuffleQ.shuffle(Q);
System.out.println("Shuffled Queue: ");
System.out.println(Q);
}
}
QueueTester3.main(null);
class Stack<T>{
LinkedList<T> top = null;
public Stack(){
}
public void push(T data){
top = new LinkedList<T>(data, top);
}
public T pop(){
T val = top.getData();
top = top.getPrevious();
return val;
}
public T peek(){
return top.getData();
}
public String toString(){
LinkedList<T> current = top;
String result = "(Head) -> ";
if (current == null){
result += "Null + ->";
}
while(current !=null){
result += current.getData() + " -> ";
current = current.getPrevious();
}
result += "nil";
return result;
}
}
- reversing list
class QueueTester4 {
public static void main(String[] args)
{
Stack stack = new Stack();
// Create first q
int[] set = {1, 2, 3, 4, 5, 6, 7, 8};
for (int n: set){
System.out.print(n + " -> ");
}
System.out.println();
for (int n: set){
stack.push(n);
}
System.out.println("Stack: ");
System.out.println(stack);
}
}
QueueTester4.main(null);