Tri 3: Tech Talk week 1: Linked Lists Part 2

Data Structures

Linked Lists

Formerly, in class we have held hands and discussed Linked Lists (LL). We went over concepts in a Tri 2 Linked Lists TT. Please use this as a review.

As stated, most "Data Structures" conversations usually begin with Arrays, which are built into most Computer Programming Languages. College Board has Units 6-8 which discuss Arrays, ArrayLists, and 2-Dimensional Arrays. Most Data Structures conversations continue with the discussions of Linked Lists which are the foundation for Stacks and Queues. This TT is about building your own data structures.

Challenges

• Key learning 1: Become familiar with Linked List, Circle Queues, and Stacks.
• Key learning 2: Become familiar with managing data (aka nodes) in these structures.
• Advanced Key learning 3: Implement Generic data and ForEach loop support, similar to Arrays and ArrayLists. Here is sample Java Generic T and the Java Iterable interface by Geeks4Geeks. FYI, Linked List and Queue implementations provided below.

1. Challenge #1, Add and Delete elements from Queue. Working with the code that is given, you will need to adjust Add and write Delete, to output from the Queue as follows.

Enqueued data: seven
Words count: 1, data: seven 
Enqueued data: slimy
Words count: 2, data: seven slimy 
Enqueued data: snakes
Words count: 3, data: seven slimy snakes 
Enqueued data: sallying
Words count: 4, data: seven slimy snakes sallying 
Enqueued data: slowly
Words count: 5, data: seven slimy snakes sallying slowly 
Enqueued data: slithered
Words count: 6, data: seven slimy snakes sallying slowly slithered 
Enqueued data: southward
Words count: 7, data: seven slimy snakes sallying slowly slithered southward 
Dequeued data: seven
Words count: 6, data: slimy snakes sallying slowly slithered southward 
Dequeued data: slimy
Words count: 5, data: snakes sallying slowly slithered southward 
Dequeued data: snakes
Words count: 4, data: sallying slowly slithered southward 
Dequeued data: sallying
Words count: 3, data: slowly slithered southward 
Dequeued data: slowly
Words count: 2, data: slithered southward 
Dequeued data: slithered
Words count: 1, data: southward 
Dequeued data: southward
Words count: 0, data: null

2. Challenge #2, perform a merge or combination of 2 Queue's that are ordered. This is a foundation step for future Merge sorting. IMO, this algorithm is easier if you "peek" at data at the head of the queue, prior to performing dequeue action.

// Start with two ordered Queue's
(1st Queue) 1 -> 4 -> 5 -> 8 -> nil
(2nd Queue) 2 -> 3 -> 6 -> 7 -> nil

// Finish with a 3rd Queue 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 nil

3. Challenge #3, Build a stack and use it to reverse the order of a Queue. FYI, here is an implementation of Stack without Generic T and Iterable.

// Place elements into Queue
(Head) 1 -> 2 -> 3 -> nil
// Print out the following:
1 2 3

// Place elements from Queue to Stack
(Top) 3 -> 2 -> 1 -> nil

// Print out the following:
3 2 1

Below is a starter Queue and a Linked List implementation. Unlike former code shared this contains implementation of a REAL Java Generic type and implements Iterable to support Java ForEach (enhanced For) loops.

package com.nighthawk.csa.utility.LinkedLists2;

import com.nighthawk.csa.mvc.DataOps.genericDataModel.Alphabet;
import com.nighthawk.csa.mvc.DataOps.genericDataModel.Animal;
import com.nighthawk.csa.mvc.DataOps.genericDataModel.Cupcakes;

import java.util.Iterator;

/**
 * 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, tail;

    /**
     *  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 (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 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);
    }
}

/**
 * Queue Iterator
 *
 * 1. "has a" current reference in Queue
 * 2. supports iterable required methods for next that returns a data object
 */
class QueueIterator<T> implements Iterator<T> {
    LinkedList<T> current;  // current element in iteration

    // QueueIterator is intended to the head of the list for iteration
    public QueueIterator(Queue<T> q) {
        current = q.getHead();
    }

    // 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 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) {
        for (T[] objects: seriesOfObjects)
            for (T data : objects) {
                this.queue.add(data);
                this.count++;
            }
    }

    /**
     * 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();
    }
}

/**
 * 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
        Object[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
        QueueManager qWords = new QueueManager("Words", words );
        qWords.printQueue();

        // Create iterable Queue of Integers
        Object[] numbers = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        QueueManager qNums = new QueueManager("Integers", numbers );
        qNums.printQueue();

        // Create iterable Queue of NCS Generics
        Animal.setOrder(Animal.KeyType.name);
        Alphabet.setOrder(Alphabet.KeyType.letter);
        Cupcakes.setOrder(Cupcakes.KeyType.flavor);
        // Illustrates use of a series of repeating arguments
        QueueManager qGenerics = new QueueManager("My Generics",
                Alphabet.alphabetData(),
                Animal.animalData(),
                Cupcakes.cupCakeData()
        );
        qGenerics.printQueue();

        // Create iterable Queue of Mixed types of data
        QueueManager qMix = new QueueManager("Mixed");
        qMix.queue.add("Start");
        qMix.addList(
                words,
                numbers,
                Alphabet.alphabetData(),
                Animal.animalData(),
                Cupcakes.cupCakeData()
        );
        qMix.queue.add("End");
        qMix.printQueue();
    }
}

package com.nighthawk.csa.utility.LinkedLists2;
/**
 *  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;
    }

}