Linked Lists, Queue, Stack, Generic <T>
Notes
See weekly notes here
Hacks
- Build into this Jupyter Notebook(s) for Bubble Sort, Selection Sort, Insertion Sort and Merge Sort.
- Build into this Jupyter Notebooks Tester methods that runs each Sort
- Commit to GitHub Repository often, try to use GitHub commits to show iterations on work
- Note, build your sorts into Generic T Queue using toString and compareTo to compare keys.
Code
/**
* 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);
}
}
import java.util.Random;
import java.util.stream.IntStream;
/**
* Queue Manager 1. "has a" Queue 2. support management of Queue tasks (aka:
* titling, adding a list, printing)
*/
class QueueManager<T>
{
// queue data
private final String name; // name of queue
private int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
/**
* Queue constructor Title with empty queue
*/
public QueueManager(String name)
{
this.name = name;
}
/**
* Queue constructor Title with series of Arrays of Objects
*/
public QueueManager(String name, T[]... seriesOfObjects)
{
this.name = name;
this.addList(seriesOfObjects);
}
/**
* Add a list of objects to queue
*/
public void addList(T[]... seriesOfObjects)
{ // accepts multiple generic T lists
for (T[] objects : seriesOfObjects)
for (T data : objects)
{
this.queue.add(data);
this.count++;
}
}
public void printAddList(T[]... seriesOfObjects)
{
// accepts multiple generic T lists
for (T[] objects : seriesOfObjects)
for (T data : objects)
{
this.queue.add(data);
this.count++;
printQueue();
}
}
/**
* Add a list of objects to queue
*/
public void deleteList(T[]... seriesOfObjects)
{ // accepts multiple generic T lists
for (T[] objects : seriesOfObjects)
for (T data : objects)
{
this.queue.delete();
this.count--;
printQueue();
}
}
/**
* Print any array objects from queue
*/
public void printQueue()
{
System.out.println(this.name + " count: " + count);
System.out.print(this.name + " data: ");
for (T data : queue)
{
System.out.print(data + " ");
}
System.out.println();
}
public Integer[] mergeSort(Integer[] array1, Integer[] array2)
{
/*
* WHILE NEITHER LOOPS ARE AT END 2 variables, front 1, front 2 look at lowest
* of queue --> copy to new queue increment to next element of the copied queue
*/
Integer[] finalArray = new Integer[array1.length + array2.length];
int front1 = 0; // index of array1
int front2 = 0; // index of array2
int i = 0; // index of finalArray
while ((front1 != array1.length) && (front2 != array2.length)) // while neither loops are at the last element
{
if (array1[front1] <= array2[front2])
{
finalArray[i] = array1[front1];
front1++;
}
else
if (array2[front2] <= array1[front1])
{
finalArray[i] = array2[front2];
front2++;
}
i++;
}
// array1 finished first
if (front1 == array1.length)
{
while (front2 != array2.length)
{
finalArray[i] = array2[front2];
front2++;
i++;
}
}
// array2 finished first
if (front2 == array2.length)
{
while (front1 != array1.length)
{
finalArray[i] = array1[front1];
front1++;
i++;
}
}
return finalArray;
}
public Integer[] shuffle(Integer[] ogArray)
{
for (int i = 0; i < ogArray.length - 1; i++)
{
int temp = 0;
Random random = new Random();
int otherElement = random.nextInt(0, ogArray.length + 1);
temp = ogArray[i];
ogArray[i] = ogArray[otherElement];
ogArray[otherElement] = temp;
}
return ogArray;
}
public String[] shuffle2(String[] ogArray)
{
for (int i = 0; i < ogArray.length - 1; i++)
{
String temp = "";
Random random = new Random();
int otherElement = random.nextInt(0, ogArray.length - 1);
temp = ogArray[i];
ogArray[i] = ogArray[otherElement];
ogArray[otherElement] = temp;
}
return ogArray;
}
public Integer[] reverse(Integer[] array)
{
Integer[] newArray = new Integer[array.length];
int j = 0;
for (int i = array.length - 1; i >= 0; i--)
{
newArray[i] = array[j];
j++;
}
return newArray;
}
}
/**
* Driver Class Tests queue with string, integers, and mixes of Classes and
* types
*/
public class QueueTester
{
public static void main(String[] args)
{
// Create iterable Queue of Words
System.out.printf("CHALLENGE #1\n\n");
Object[] words = new String[]
{ "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward" };
QueueManager qWords = new QueueManager("Word");
System.out.printf("Add:\n");
qWords.printAddList(words);
System.out.printf("\n");
System.out.printf("Delete:\n");
qWords.deleteList(words);
System.out.printf("\n");
System.out.printf("CHALLENGE #2\n\n");
Integer[] queue1 = new Integer[]
{ 0, 2, 4, 6, 8 };
QueueManager qEven = new QueueManager("Even");
qEven.addList(queue1);
qEven.printQueue();
Integer[] queue2 = new Integer[]
{ 1, 3, 5, 7, 9 };
QueueManager qOdd = new QueueManager("Odd");
qOdd.addList(queue2);
qOdd.printQueue();
QueueManager qMerge = new QueueManager("Merge");
Integer[] queue3 = qMerge.mergeSort(queue1, queue2);
qMerge.addList(queue3);
qMerge.printQueue();
System.out.printf("\n");
System.out.printf("CHALLENGE #3\n\n");
Integer[] queue4 = new Integer[]
{ 1, 2, 3, 4, 5 };
QueueManager qOG = new QueueManager("Queue4");
qOG.addList(queue4);
qOG.printQueue();
QueueManager qShuffle = new QueueManager("Shuffle");
queue4 = qShuffle.shuffle(queue4);
qShuffle.addList(queue4);
qShuffle.printQueue();
System.out.printf("\n");
System.out.printf("CHALLENGE #4\n\n");
Integer[] queue5 = new Integer[]
{ 3, 6, 9, 12, 15, 17 };
QueueManager qbefore = new QueueManager("Queue5");
qbefore.addList(queue5);
qbefore.printQueue();
QueueManager qReverse = new QueueManager("Reverse");
queue5 = qReverse.reverse(queue5);
qReverse.addList(queue5);
qReverse.printQueue();
System.out.printf("\n");
System.out.printf("CHALLENGE #5\n\n");
String[] questions = new String[]
{"All elements of an array are of the same type\n",
"Arrays cannot contain strings as elements\n",
"Two-dimensional arrays always have the same number of rows and columns\n",
"Elements of different columns in a 2D array can have different types\n",
"A method cannot return a 2D array\n",
"A method cannot change the length of an array argument\n",
"A method cannot change the number of columns of an argument that is a 2D array\n"};
QueueManager qOG2 = new QueueManager("Questions");
qOG2.addList(questions);
qOG2.printQueue();
QueueManager qShuffle2 = new QueueManager("Shuffled Questions");
questions = qShuffle2.shuffle2(questions);
qShuffle2.addList(questions);
qShuffle2.printQueue();
}
}
QueueTester.main(null);