Tri 2: Tech Talk 8: Linked Lists, Queues, Stacks

Data Structures

• Objective: Visualize and Conceptually Understand key data structures used in Computer Science
• Resources: Linked Lists, Queues, Stacks
• Summary: Often "Data Structures" conversations 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. Data Structures conversation continue with the discussions of Linked Lists. There is an implementation built into Java, but the Teacher is providing an implementation to help you visualize this Data Structure internally. Stacks and Queues can be built on top of Linked Lists and this implementation and code examples show LinkedList used as nodes in these Data Structures.

Linked Lists

• Linked list are a way of keeping and managing a list of Objects
• ABCD have Data and Next pointer
• E is illustrative of inserting a new Object
• tmp illustrates accessing the Data from the D Object

/**
 *  Implementation of a Linked List with an Object;  forward and backward links point to adjacent Nodes.
 *
 */
public class LinkedList
{
    private Object opaqueObject;  // opaqueObject means specific type is not known, as LinkedList are not specific to a data type
    private LinkedList prevNode;
    private LinkedList nextNode;

    /**
     *  Constructs a new element with object objValue,
     *  followed by object address
     *
     * @param  opaqueObject  Address of Object
     */
    public LinkedList(Object opaqueObject, LinkedList node)
    {
        this.setObject(opaqueObject);
        this.setPrevNode(node);
        this.setNextNode(null);
    }

...

/**
     *  Setter for opaqueObjecg in LinkedList object
     *
     * @param  opaqueObject  Address of Object
     */
    public void setObject(Object opaqueObject)
    {
        this.opaqueObject = opaqueObject;
    }

    /**
     *  Setter for prevNode in LinkedList object
     *
     * @param node     A LinkedList object that is prevNode to current Object
     */
    public void setPrevNode(LinkedList node)
    {
        this.prevNode = node;
    }

    /**
     *  Setter for nextNode in LinkedList object
     *
     * @param node     A LinkedList object that is nextNode to current Object
     */
    public void setNextNode(LinkedList node)
    {
        this.nextNode = node;
    }

Queues. This is like a line at the grocery store, First In First Out (FIFO).

• Queues can be built using Linked List Objects
• A Queue requires keeping track of First In for dequeue extraction (head node)
• A Queue requires keeping track of the Back for enqueue entry (tail node)
• A Queue requires keeping track of the Current node for iteration (current node)

/**
 *  Key nodes in a Queue.
 *
 */
public class CircleQueue
{
    private LinkedList headNode;			// 1st element in Queue
    private LinkedList tailNode;			// Last element in Queue
    private LinkedList currentNode;

...

    /**
     *  Add a new object at the end of the Queue,
     *
     * @param  opaqueObject  is the database to be inserted in the Queue object.
     */
    public void add(Object opaqueObject)
    {
        // add new object to end of Queue
        // set opaqueObject
        // build previous link of tail (as current)
        tailNode = new LinkedList(opaqueObject, currentNode);

        // build next link of current (as tail)
        if (currentNode != null)
            currentNode.setNextNode(tailNode);

        // after links are established current eq tail
        currentNode = tailNode;

        // head eq tail on 1st element only
        if (headNode == null) {
            headNode = tailNode;
        }
    }

Stacks. This is like a stack of plates, Last In First Out (LIFO).

• Stacks can be built using Linked List Objects
• A Stack requires keeping track of Last Item inserted to support Push entry and Pop extraction (lifo node)

/**
 *  Implementation of Stack, using LinkedList
 *
 */
public class Stack
{
    private LinkedList lifo;  // last in first out Object of stack

    /**
     *  Constructor for the SinglyLinkedList object
     *  Generates an empty list.
     */
    public Stack()
    {
        lifo = null;
    }

...

/**
     *  Inserts a new object at the top of this Stack,
     *
     * @param  value  is the database to be inserted at the top of the Stack.
     */
    public void push(Object value)
    {
        // note the order that things happen:
        // the new object becomes current and gets a value
        // current lifo is parameter, it is assigned as previous node in lifo
        lifo = new LinkedList(value, lifo);
    }

    /**
     *  Removes the top element in the Stack.  Garbage collection should destroy this element when needed.
     *
     */
    public Object pop()
    {
        Object value = null;

        if (lifo != null) {
            value = lifo.getObject();
            lifo = lifo.getPrevious();
        }

        return value;
    }