Lists, Stacks, Queues, and Dictionaries¶

4.1 Lists ¹¶

Lists implement the mathematical concept of a sequence.
Each element has a position in the sequence.
List is a finite,, ordered sequence of elements.
Each list has a data type for its elements, but it can contain elements of different types if application requires it.
Lists have length, head, tail, and position.
Sorted lists are lists in which the elements are in ascending order of value.
List Specifications:
- List should grow or shrink as items are inserted or removed.
- List should allow for inserting and removing items at any position.
- Create/initialize and clear (reinitialize) a list.
- Access element at a given position.
- Access previous and next element from a given position.

/** List ADT */
public interface List<E> {
    /**
     * Remove all contents from the list, so it is once again empty.
     * Client is responsible for reclaiming storage used by the list elements.
     */
    public void clear();

    /**
     *  Insert an element at the current location.
     *  The client must ensure that the list’s capacity is not exceeded.
     * @param item The element to be inserted.
     */
    public void insert(E item);

    /**
     * Append an element at the end of the list.
     * The client must ensure that the list’s capacity is not exceeded.
     * @param item The element to be appended.
     */
    public void append(E item);

    /**
     * Remove and return the current element.
     * @return The element that was removed.
     */
    public E remove();

    /** Set the current position to the start of the list */
    public void moveToStart();

    /** Set the current position to the end of the list */
    public void moveToEnd();

    /** Move the current position one step left. No change if already at beginning. */
    public void prev();

    /** Move the current position one step right. No change if already at end. */
    public void next();

    /** @return The number of elements in the list. */
    public int length();

    /** @return The position of the current element. */
    public int currPos();

    /**
     * Set current position.
     * @param pos The position to make current.
     */
    public void moveToPos(int pos);

    /** @return The current element. */
    public E getValue();
}

Example of using a List:

List<String> l = new List<String>(); // assuming List is implemented

for (l.moveToStart(); l.currPos() < l.length(); l.next()) {
   item = l.getValue();
    // do something with item
    System.out.println(item);
}

4.1.1 Array-Based List Implementation¶

The classAList implements theList interface using an array-based implementation.
Getting a value stored at a given position requires 2 stepsmoveToPos(pos); getValue(); and it has a time complexity ofΘ(1).
append() = insert(tail) orremove(tail) is easy and has a time complexity ofΘ(1).
insert(pos) andremove(pos) are not easy and have a time complexity ofΘ(n) since we need to shift all the elements after the position to the left or right.
Time complexities:

Operation	Complexity	Comment
insert	Θ(n)	elements must be shifted right
remove	Θ(n)	elements must be shifted left
append	Θ(1)
next	Θ(1)
prev	Θ(1)
moveToPos	Θ(1)

/** Array-based list implementation */
class AList<E> implements List<E> {
    private static final int defaultSize = 10; // Default size
    private int maxSize; // Maximum size of list
    private int listSize; // Current # of list items
    private int curr; // Position of current element
    private E[] listArray; // Array holding list elements

    /** Constructors */ /** Create a list with the default capacity. */
    AList() { this(defaultSize); }

    /**
     * Create a new list object.
     * @param size Max # of elements list can contain
     */
    @SuppressWarnings("unchecked") // Generic array allocation
    AList(int size) {
        maxSize = size;
        listSize = curr = 0;
        listArray = (E[])new Object[size]; // Create listArray
    }


    // Reinitialize the list
    public void clear(){
        listSize = curr = 0; // Simply reinitialize values
    }

    /** Insert "it" at current position */
    public void insert(E it) {
        assert listSize < maxSize : "List capacity exceeded";

        // Shift elements up
        for (int i=listSize; i>curr; i--) {
            listArray[i] = listArray[i-1]; // to make room
        }

        listArray[curr] = it;
        listSize++; // Increment list size

    }

    /** Append "it" to list */
    public void append(E it) {
        assert listSize < maxSize : "List capacity exceeded";
        listArray[listSize++] = it;
    }

    /** Remove and return the current element */
    public E remove() {
        // No current element
        if ((curr<0) || (curr>=listSize)) return null;

        E it = listArray[curr]; // Copy the element

        // Shift them down
        for(int i=curr; i<listSize-1; i++) {
            listArray[i] = listArray[i+1];
        }

        listSize--; // Decrement size
        return it;
    }

    public void moveToStart() { curr = 0; } // Set to front
    public void moveToEnd() { curr = listSize; } // Set at end
    public void prev() { if (curr != 0) curr--; } // Back up
    public void next() { if (curr < listSize) curr++; }

    /** @return List size */
    public int length() { return listSize; }

    /** @return Current position */
    public int currPos() { return curr; }

    /** Set current list position to "pos" */
    public void moveToPos(int pos) {
        assert (pos>=0) && (pos<=listSize) : "Pos out of range";
        curr = pos;
    }

    /** @return Current element */
    public E getValue() {
        assert (curr>=0) && (curr<listSize) : "No current element";
        return listArray[curr];
    }
}

Inserting in a list requires shifting elements as shown in the following figure.

4.1.2 Linked List Implementation¶

Linked lists use dynamic memory allocation to store the elements, that is, allocates memory for new elements as needed.
Linked lists has a series of objects called nodes.

/** Singly linked list node */
class Link<E> { // a.k.a. Node
    private E element; // Value for this node
    private Link<E> next; // Pointer to next node in list

    // Constructors
    Link(E it, Link<E> nextval){
        element = it;
        next = nextval;
    }

    Link(Link<E> nextval) {
        next = nextval;
    }

    Link<E> next() { return next; } // Return next field
    Link<E> setNext(Link<E> nextval) { return next = nextval; } // Set next field
    E element() { return element; } // Return element field
    E setElement(E it) { return element = it; } // Set element field
}

Linked List has:
- head: pointer to the first node in the list.
- tail: pointer to the last node in the list; to speed up theappend() operation.
- curr:
  - A pointer to the current node in the list.
  - The current position usually points to the node before the current node.
- length:
  - cnt stores the length of the list; it must be updated at every insert/remove operation (since there is no other way to track the length of the list).
  - The Linked List constructor still have the optional default size parameter (as we saw in the array-based list implementation) but it is not used in the linked list implementation. It just kept to make the interface consistent with the array-based list implementation.
Linked list current position usually points to the node before the current node, why?
- When inserting a new need, we need to update thenext field of theprevious node to point to theinserted node.
- There is no way to access the previous node in a singly linked list.
Linked List must be initialized with empty node; this is useful for:
- Handling the edge case when the list is empty: no previous element for the first element.
- When the list is empty,head,tail andcurr point to the same node.
Inserting an element in a Linked List requires 3 steps:
1. Create a new node.
2. Thenext field of the new node should point to the current node (thenext field of thecurrent node, since thecurr points anone node before the current node).
3. Thenext field of theprevious node should point to the new node.
When removing a node, we just update the pointers, no worries about the deleted node since it will be garbage collected.

Time complexities:

operation	Time Complexity	comment
insert	Θ(1)
remove	Θ(1)
append	Θ(1)
next	Θ(1)
prev	Θ(n)	traverse the node from head till current
moveToPos	Θ(n)	traverse the node from head till current

/** Linked list implementation */
class LList<E> implements List<E> {
    private Link<E> head; // Pointer to list header
    private Link<E> tail; // Pointer to last element
    protected Link<E> curr; // Access to current element
    private int cnt; // Size of list

    /** Constructors */
    LList(int size) { this(); } // Constructor -- Ignore size
    LList() {
        curr = tail = head = new Link<E>(null); // Create header
        cnt = 0;
    }

    /** Remove all elements */
    public void clear() {
        head.setNext(null); // Drop access to links
        curr = tail = head = new Link<E>(null); // Create header
        cnt = 0;
    }

    /** Insert "it" at current position */
    public void insert(E it) {
        /**
         * 1. create a new node.
         * 2. set the next node of the new node to the current node (currentNode.next()).
         * 3. set the next node of the previous node to the new node.
        */
        Link<E> nodeBefore = curr; // hold the node before the current node (the previous node): curr pointer.
        Link<E> currentNode = nodeBefore.next(); // holds the current node: curr.next() pointer.
        Link<E> newNode = new Link<E>(it, currentNode); // create a new node and set its next node to the current node.
        nodeBefore.setNext(newNode); // update the previous node to point to the new node.

        /**
         * The three steps can be simplified using:
         * curr.setNext(new Link<E>(it, curr.next()));
        */
        if (tail == curr) tail = curr.next(); // New tail
        cnt++;
    }

    /** Append "it" to list */
    public void append(E it) {
        tail = tail.setNext(new Link<E>(it, null));
        cnt++;
    }

    /** Remove and return current element */
    public E remove() {
        if (curr.next() == null) return null; // Nothing to remove
        E it = curr.next().element(); // Remember value

        prevNode = curr; // 1. hold the previous node
        currentNode = prevNode.next(); // 2. hold the current node
        if (tail == currentNode) tail = prevNode; // 3. update the tail if  we are removing the last node.
        prevNode.setNext(currentNode.next()); // 4. update the previous node to ignore the current node.

        /**
         * The four steps can be simplified using:
         * if (tail == curr.next()) tail = curr; // Removed last
         * curr.setNext(curr.next().next()); // Remove from list
        */

       cnt--; // Decrement count
        return it; // Return value
    }

    /** Set curr at list start */
    public void moveToStart() { curr = head; }

    /** Set curr at list end */
    public void moveToEnd() { curr = tail; }

   /** Move curr one step left; no change if now at front */
    public void prev() {
        if (curr == head) return; // No previous element
        Link<E> temp = head;
        // March down list until we find the previous element
        while (temp.next() != curr) temp = temp.next();
        curr = temp;
    }

    /** Move curr one step right; no change if now at end */
    public void next() {
         if (curr == tail) return; // No next element, we are at the end.
         curr = curr.next();
         /**
          * The two steps can be simplified using:
          *  if (curr != tail) curr = curr.next();
         */
    }

    /** @return List length */
    public int length() { return cnt; }

    /** @return The position of the current element */
    public int currPos() {
        Link<E> temp = head;
        int i;
        for (i=0; curr != temp; i++) {
            temp = temp.next();
            return i;
        }
    }

    /** Move down list to "pos" position */
    public void moveToPos(int pos) {
        assert (pos>=0) && (pos<=cnt) : "Position out of range";
        curr = head;
        for(int i=0; i<pos; i++) curr = curr.next();
    }

    /** @return Current element value */
    public E getValue() {
        if(curr.next() == null) return null;
        return curr.next().element();
    }
}

Insert in a Linked List:
Remove from a linked List:

FreeList¶

Using thenew keyword (a free-store routine) to allocate memory for a new object is expensive since it allocates memory (requests memory from the memory manager) of different sizes.
The garbage collector is also expansive since it frees memory unpredictably.
The idea of theFreeList is to keep a list of free nodes that can be reused without having to make a system call to the memory manager (using the new operator).
When a node is removed from the list, it is added to theFreeList and when a new node is needed, it is taken from theFreeList if it is not empty.
If theFreeList is empty, then a new node is allocated using thenew operator.
TheFreeList is implemented asstatic member of theNode (Link) class.
all FreeList operation have a time complexity of Θ(1).

/** Singly linked list node with freelist support */
class Link<E> {
    // ... Link class as before
    /** Extensions to support freelists */
    static Link freelist = null; // Freelist for the class

    /** @return A new link */
    static <E> Link<E> get(E it, Link<E> nextval) {
        if (freelist == null){
            return new Link<E>(it, nextval); // if no free nodes, call the `new` operator.
        }

        Link<E> temp = freelist; // Get from freelist
        freelist = freelist.next();
        temp.setElement(it);
        temp.setNext(nextval);
        return temp;
    }

    /** Return a link to the freelist */
    void release() {
        element = null; // Drop reference to the element
        next = freelist;
        freelist = this;
    }
}

Using theFreeList within theLList class:

public void insert(E it) {
    curr.setNext(Link.get(it, curr.next())); // using `Link.get` instead of `new Link<E>(it, curr.next())`
    if (tail == curr) tail = curr.next(); // New tail
    cnt++;
}

public void append(E it) {
    tail = tail.setNext(Link.get(it, null)); // using `Link.get` instead of `new Link<E>(it, null)`
    cnt++;
}/** Remove and return current element */

public E remove() {
    if (curr.next() == null) return null; // Nothing to remove
    E it = curr.next().element(); // Remember value
    if (tail == curr.next()) tail = curr; // Removed last
    Link<E> tempptr = curr.next(); // Remember link
    curr.setNext(curr.next().next()); // Remove from list
    tempptr.release(); // Release link and add it to the `FreeList`
    cnt--; // Decrement count
    return it; // Return removed
}

4.1.3 Comparing Linked Lists and Arrays¶

Aspect	Array	Linked List	Comments
size	must be known in advance	not Fixed
grow	can not grow beyond the initial size	grow as needed
memory allocation	contiguous block; all elements get their memory allocated at once	memory is allocated as needed, each element separately.
memory waste	memory pre-allocated for empty elements is wasted	memory is allocated as needed
total space needed	Ω(n), as it can go greater than n	Θ(n)	LL is more space efficient when the number elements is small and the array is nearly empty (more space wasted). LL are more space efficient when the number of element is variable or unknown. Arrays are more space efficient when the size in known in advance.
space for individual element	only the space required for the element.	needs extra space for each element to store the reference for the next element.	If individual element size is small (say int), arrays are better since the references in the linked list will take more storage than the element itself.
speed of random access (moveToPos)	faster.	slower.
navigating elements (using next(), prev())	next: same. prev: faster.	next: same. prev: slower, as it is Θ(n).
inserting and removing	slower as elements must be shifted after operation.	faster as they are of Θ(1).	for many applications, inserting/removing time is critical that’s why LL is preferred.

Comparing complexities of arrays and linked lists operations:

Operation	Array	Linked List (singly linked)	Linked List (doubly linked)	Comments
clear	Θ(1)	Θ(1)	Θ(1)
insert	Θ(n)	Θ(1)	Θ(1)	array shifts elements
append	Θ(1)	Θ(1)	Θ(1)
remove	Θ(n)	Θ(1)	Θ(1)	array shifts elements
moveToStart	Θ(1)	Θ(1)	Θ(1)
moveToEnd	Θ(1)	Θ(1)	Θ(1)
prev	Θ(1)	Θ(n)	Θ(1)	no reference to prev element in LL (SL) node
next	Θ(1)	Θ(1)	Θ(1)
length	Θ(1)	Θ(1)	Θ(1)
currentPos	Θ(1)	Θ(n)	Θ(n)	LL (SL) must traverse the nodes to find the pos of the current element
moveToPos	Θ(1)	Θ(n)	Θ(n)	LL (SL) must traverse the node to track indexes
getValue	Θ(1)	Θ(1)	Θ(1)

Dynamic arrays¶

Dynamic arrays are array-based link implantation that allows the array to grow and shrink as needed.
Rules:
- Double the size of the array when it is full: copy the elements to a new array of double the size.
- Cut the size of the array in half when it is one-quarter full:
  - when array is ¼ full, copy the elements to a new array of half the size.
  - e.g. if size=100, set the new size to 50, when only 25 elements are left in the array.

4.1.4 Element Implementations¶

In theLink class, if the element is small (say int), it may be more efficient to store the element directly in the node rather than storing a reference to the element.
Homogeneity: all elements in the list must be of the same type.
For programming languages that have no automatic garbage collection:
- The clear operation must release all the nodes in the list.
- The list must includedestructor that releases all the nodes in the list and the list itself.
- This becomes more complicated, if the list contains reference to objects that are used elsewhere in the program or if the list itself is used.
- The safest way is just to remove the references (since we can not tell if object is used elsewhere) and keep the objects themselves (which is wasteful of memory if objects actually not used elsewhere).
- In those languages, it is the responsibility of the programmer to release the memory used by the list.

4.1.5 Doubly Linked Lists¶

Each node contains two references: one to the next node and one to the previous node.
The LL must be initialized with 2 empty nodes: head and tail (both always exist).
Thecurr pointer is used to point to the actual current node.
The only disadvantage of Doubly Linked Lists is that they use more memory than singly linked lists (because of the extra reference to the previous node).

4.2 Stacks ¹¶

Stack is a list-like structure in which elements are added and removed from only one end, called the top.
The restrictions of stacks makes them less flexible than lists, but they are more efficient and easy to implement.
TheFreeList is a stack.
Stacks are LIFO (Last In First Out) data structures that removes items in the reverse order from which they were added.
Stacks have Push and Pop operations.
Stack can be array-based or linked-based.

4.2.1 Array-Based Stacks¶

The top element maps to n-1 index in the array (where n is the number of occupied elements in the array) aka. the first free position in the array.
The time complexity of push and pop operations is Θ(1).

/** Stack ADT */
public interface Stack<E> {
/** Reinitialize the stack. The user is responsible for reclaiming the storage used by the stack elements. */
public void clear();

/** Push an element onto the top of the stack. */
public void push(E it);

/** Remove and return the element at the top of the stack. */
public E pop();

/** @return A copy of the top element. */
public E topValue();

/** @return The number of elements in the stack. */
public int length();
}

Array-based stack implementation:

/** Array-based stack implementation */
class AStack<E> implements Stack<E> {
    private static final int defaultSize = 10;
    private int maxSize; // Maximum size of stack
    private int top; // Index for top Object
    private E [] listArray; // Array holding stack

    /** Constructors */
    AStack() { this(defaultSize); }
    @SuppressWarnings("unchecked") // Generic array allocation
    AStack(int size) {
    maxSize = size;
    top = 0;
    listArray = (E[])new Object[size]; // Create listArray
    }

    /** Reinitialize stack */
    public void clear() { top = 0; }

    /** Push "it" onto stack */
    public void push(E it) {
        assert top != maxSize : "Stack is full";
        listArray[top++] = it;
    }

    /** Remove and top element */
    public E pop() {
        assert top != 0 : "Stack is empty";
        return listArray[--top];
    }

    /** @return Top element */
    public E topValue() {
        assert top != 0 : "Stack is empty";
        return listArray[top-1];
    }

    /** @return Stack size */
    public int length() { return top; }
}

4.2.2 Linked Stacks¶

Elements are pushed/popped from the head of the list.
Push: create a new node that its next node is the current head and set the new node as the new head; increase the size.
Pop: set the head to be the next node of the current head; decrease the size.
Linked stacks implementation:

/** Linked stack implementation */
class LStack<E> implements Stack<E> {
    private Link<E> top; // Pointer to first element
    private int size; // Number of elements

    /** Constructors */
    public LStack() { top = null; size = 0; }
    public LStack(int size) { top = null; size = 0; } // size is ignored, added for compatibility

    /** Reinitialize stack */
    public void clear() { top = null; size = 0; }

    /** Put "it" on stack */
    public void push(E it) {
        top = new Link<E>(it, top);
        size++;
    }

    /** Remove "it" from stack */
    public E pop() {
        assert top != null : "Stack is empty";
        E it = top.element();
        top = top.next();
        size--;
        return it;
    }

    /** @return Top value */
    public E topValue() {
        assert top != null : "Stack is empty";
        return top.element();
    }

    /** @return Stack length */
    public int length() { return size; }
}

4.2.3 Comparison of Array-Based and Linked Stacks¶

Aspect	Array-Based Stacks	Linked Stacks	Comments
Efficiency	All operations are Θ(1)	All operations are Θ(1)	No difference
Total size required	Ω(n), as it can go greater than n	Θ(1)	Arrays have the advantage only when the size is known in advance

A single array can be used to store two stacks:
- By using the first half of the array for the first stack and the second half for the second stack.
- The first stack grows from the left to the right and the second stack grows from the right to the left.
- We keep track of the top of each stack separately.
- It is not efficient if both stacks grow and shrink frequently.

4.2.4 Implementing Recursion¶

Implementing recursion using stacks (the factorial function):

/** @return n! */
static long fact(int n) {
    // To fit n! in a long variable, require n < 21
    assert (n >= 0) && (n <= 20) : "n out of range";

    // Make a stack just big enough
    Stack<Integer> S = new AStack<Integer>(n);

    while (n > 1) S.push(n--); // push items n, n-1, ..., 2, 1 onto S

    long result = 1;
    while (S.length() > 0) {
        result = result * S.pop(); // pop the stack and multiply the result
    }

    return result;
}

4.3 Queues¶

Queues are FIFO (First In First Out) data structures that removes items in the same order from which they were added.
Queues have Enqueue (at the back) and Dequeue (from the front) operations.
Queue ADT:

/** Queue ADT */
public interface Queue<E> {
    /** Reinitialize the queue. The user is responsible for reclaiming the storage used by the queue elements. */
    public void clear();

    /** Place an element at the rear of the queue. */
    public void enqueue(E it);

    /** Remove and return element at the front of the queue. */
    public E dequeue();

    /** @return The front element. */
    public E frontValue();

    /** @return The number of elements in the queue. */
    public int length();
}

4.3.1 Array-Based Queues¶

Array-based queues are not efficient as they require shifting all the elements to the left after each dequeue operation and shifting all the elements to the right after each enqueue operation.
Items are enqueued to the rear of the queue and dequeued from the front of the queue.
If we choose therear to Array[0]: dequeue requiresΘ(1) and enqueue requiresΘ(n) since we need to shift all the elements to the right upon enqueue.
If we choose therear to Array[n-1]: dequeue requiresΘ(n) and enqueue requiresΘ(1) since we need to shift all the elements to the left upon dequeue.
One solution is:
- To track both thefront and therear of the queue relaxing the requirement that the queue must be stored in a contiguous block of memory starting at Array[0].
- This raises the queue drifting issue.
- Queue drifting: the queue can drift to the right and the left of the array where you run out of positions to enqueue or dequeue while there are still empty positions in the array at the other end.
- The Queue drifting issue is solved by circular queues.
- In circular queues, the case of empty queue and full queue are indistinguishable.
Array-based queues implementation:

/** Array-based queue implementation */
class AQueue<E> implements Queue<E> {
    private static final int defaultSize = 10;
    private int maxSize; // Maximum size of queue
    private int front; // Index of front element
    private int rear; // Index of rear element
    private E[] listArray; // Array holding queue elements

    /** Constructors */
    AQueue() { this(defaultSize); }
    @SuppressWarnings("unchecked") // For generic array
    AQueue(int size) {
        maxSize = size+1; // One extra space is allocated to avoid the confusion between empty and full queue
        rear = 0; front = 1; // front towards lower indices  and rear towards higher indices
        listArray = (E[])new Object[maxSize]; // Create listArray
    }

    /** Reinitialize */
    public void clear() { rear = 0; front = 1; }

    /** Put "it" in queue */
    public void enqueue(E it) {
        assert ((rear+2) % maxSize) != front : "Queue is full";
        rear = (rear+1) % maxSize; // Circular increment
        listArray[rear] = it;
    }

    /** Remove and return front value */
    public E dequeue() {
        assert length() != 0 : "Queue is empty";
        E it = listArray[front];
        front = (front+1) % maxSize; // Circular increment
        return it;
    }

    /** @return Front value */
    public E frontValue() {
        assert length() != 0 : "Queue is empty";
        return listArray[front];
    }

    /** @return Queue size */
    public int length() { return ((rear+maxSize) - front + 1) % maxSize; }
}

4.3.2 Linked Queues¶

The Linked queues implementation is straightforward:

/** Linked queue implementation */
class LQueue<E> implements Queue<E> {
    private Link<E> front; // Pointer to front queue node
    private Link<E> rear; // Pointer to rear queue node
    private int size; // Number of elements in queue

   /** Constructors */
    public LQueue() { init(); }
    public LQueue(int size) { init(); } // Ignore size

   /** Initialize queue */
    private void init() {
        front = rear = new Link<E>(null);
        size = 0;
    }

    /** Reinitialize queue */
    public void clear() { init(); }

    /** Put element on rear */
    public void enqueue(E it) {
        rear.setNext(new Link<E>(it, null));
        rear = rear.next();
        size++;
    }

    /** Remove and return element from front */
    public E dequeue() {
        assert size != 0 : "Queue is empty";
        E it = front.next().element(); // Store dequeued value
        front.setNext(front.next().next()); // Advance front
        if (front.next() == null) rear = front; // Last Object
        size--;
        return it; // Return Object
    }

    /** @return Front element */
    public E frontValue() {
        assert size != 0 : "Queue is empty";
        return front.next().element();
    }

    /** @return Queue size */
    public int length() { return size; }
}

Queues Advanced ²¶

Queue Types:
- Standard Queue:
  - Insert at the back (rear) of the queue. Remove from the front.
  - Peek: look at the front element without removing it.
- Priority Queues:
  - Implemented using a Heap data structure.
  - Nodes have a priority value.
  - Nodes are sorted by priority upon insertion (and/or removal, and/or periodically).
  - The node with the highest priority is always at the front of the queue.
  - No changes to the dequeue() and frontValue() methods.
- Double ended Queue (deque):
  - Items can be inserted and removed from both ends of the queue.
  - This queue has no priority.
  - Has methods like: enqueueFront(), dequeueFront(), enqueueRear(), dequeueRear(), frontValue(), rearValue(), peekFront(), peekRear().
  - Implemented using Doubly Linked List.

4.4 Dictionaries¶

The Dictionary ADT is a collection of key-value pairs.

/** The Dictionary abstract class. */
public interface Dictionary<Key, E> {
    /** Reinitialize dictionary */
    public void clear();
    /** Insert a record */
    public void insert(Key k, E e);

    /** Remove and return a record.
    @param k The key of the record to be removed.
    @return A maching record. If multiple records match "k", remove an arbitrary one.
    Return null if no record with key "k" exists. */
    public E remove(Key k);

   /** Remove and return an arbitrary record from dictionary.  @return the record removed, or null if none exists. */
    public E removeAny();

    /** @return A record matching "k" (null if none exists).
    If multiple records match, return an arbitrary one.
    @param k The key of the record to find */
    public E find(Key k);

    /** @return The number of records in the dictionary. */
    public int size();
};

TheremoveAny() allows for iterating over the dictionary if we dont know the keys as:

    while (D.size() > 0) {
        E e = D.removeAny();
        // Do something with e
    }

Dictionaries are not able to find the first key or the first value efficiently.
Dictionaries can be implemented based onUnsorted Lists:
- Dictionaries as an unsorted list of KeyValuePair objects.
- see: UALdictionary class in ./code/PayRoll.java.
- The list itself can be implemented as anArrayList or aLinkedList.
- Insertion are Θ(1) while finding and removing are Θ(n) (linear or sequential search). removeAny() is Θ(1).
Dictionaries can be implemented based onSorted Lists:
- Dictionaries as a sorted list of KeyValuePair objects.
- Sorted lists are very different from the list that we studies:
  - User can not specify the position of insertion.
  - The list must sort itself on every insertion/removal.
  - Append operations are not allowed.
- Using sorted lists make find/remove much easier.
- Insertions are Θ(n) while findings are Θ(log n) (binary search), removing are still Θ(n). removeAny() is Θ(1).
Comparing the two implementations in terms of time complexity:

Operation	Unsorted List	Sorted List	Comments
insert	Θ(1)	Θ(n)
find	Θ(n)	Θ(log n)
remove	Θ(n)	Θ(n)	elements must be shifted in both implementations
removeAny	Θ(1)	Θ(1)

Which one to choose depends on the application. If you do more insertions than searches, then use the unsorted list. If you do more searches than insertions, then use the sorted list.

References¶

Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 4. ↩↩
Barnett, G. & Del Tongo, L. (2008). Data Structures and Algorithms: An Annotated Reference with Examples. Chapter 6: Queues. ↩

Lists, Stacks, Queues, and Dictionaries¶

4.1 Lists 1¶

4.1.1 Array-Based List Implementation¶

4.1.2 Linked List Implementation¶

FreeList¶

4.1.3 Comparing Linked Lists and Arrays¶

Dynamic arrays¶

4.1.4 Element Implementations¶

4.1.5 Doubly Linked Lists¶

4.2 Stacks 1¶

4.2.1 Array-Based Stacks¶

4.2.2 Linked Stacks¶

4.2.3 Comparison of Array-Based and Linked Stacks¶

4.2.4 Implementing Recursion¶

4.3 Queues¶

4.3.1 Array-Based Queues¶

4.3.2 Linked Queues¶

Queues Advanced 2¶

4.4 Dictionaries¶

References¶

4.1 Lists ¹¶

4.2 Stacks ¹¶

Queues Advanced ²¶