Abstract Data Types

Main abstract data types:

• Lists
• Maps/Dictionaries
• Sets
• Stacks
• Queues
• Trees

These are basic types of data structures (although some of the data types above may utilize other data types in their implementation, e.g., a linked list structure used to store a dictionary).

Lists

Array list data type

Main article: ArrayLists

Dynamically expanding array list type. The best way to implement a dynamically expanding array is to have it double in size when the array of capacity n reaches n+1 items. Increasing by a fixed amount incurs an O(n^2) cost.

We also want to dynamically shrink the array, but at a different multiple than 1/2 (otherwise we have a single size change that can toggle the size of the array, incurring O(n) cost with each operation.)

Array list interface

The array list type should implement the following methods:

• size
• is empty
• search
• append/insert
• remove/pop
• get
• set
• minimum
• maximum

Array list computational complexity

Operation	Array list	Array list, sorted
Search(L,k)	O(n)	O(log n)
Insert(D,x)	O(1)	O(n)
Delete(L,x)	O(1)*	O(n)
Successor(L,x)	O(n)	O(1)
Predecessor(L,x)	O(n)	O(1)
Minimum(L)	O(n)	O(1)
Maximum(L)	O(n)	O(1)

Linked list data type

Main: Linked Lists

Linked data structures: much/most of the data in a linked list data type is dedicated to links/addresses

Main differences in implementation of linked list types are in the links themselves. Doubly linked lists have simpler algorithms and are easier to implement, but come with the extra overhead of additional pointers.

Linked list interface

The linked list type should implement the following methods:

• size
• isEmpty
• addFirst
• addLast
• removeFirst
• removeLast
• get(i)

Linked list computational complexity

Speed of operations on sorted and unsorted linked lists:

Operation	Singly Linked List	Doubly Linked List	Singly Linked List, Sorted	Doubly Linked List, Sorted
Search(L,k)	O(n)	O(n)	O(n)	O(n)
Insert(D,x)	O(1)	O(1)	O(n)	O(n)
Delete(L,x)	O(n)*	O(1)	O(n)*	O(1)
Successor(L,x)	O(n)	O(n)	O(1)	O(1)
Predecessor(L,x)	O(n)	O(n)	O(n)*	O(1)
Minimum(L)	O(n)	O(n)	O(1)	O(1)
Maximum(L)	O(n)	O(n)	O(1)*	O(1)

Stacks and Queues

Main article: StacksQueues

Stacks

Stacks are LIFO (last in, first out) data structures. They have fast O(1) access to add to and remove from the top of the stack. No random access to the inner elements of the stack is provided. Stacks can be implemented using arrays (bottom of stack is beginning of array, top of stack is last element in array) or a using linked list structure.

Stack interface

Any standard Stack data structure should implement the following methods:

• size() - get the number of elements currently in the stack
• isEmpty() - returns true if stack is empty
• push() - add the given item to the top of the stack
• pop() - remove the top item in the stack and return it
• peek() - return reference to top item in stack, but do not remove it

Queues

Queues are FIFO (first in, first out) data structures. They have fast O(1) access to add to the back and remove from the front. No random access to the inner elements of the queue is provided. Queues are sometimes referred to as "priority queues". They can be implemented using arrays (with floating pointers to the beginning and end of the queue that rotate through the array), or using linked lists. Circular linked lists may prove useful here as well.

Queue interface

Like stacks, queues don't need to implement a lot of methods. Here's what the queue interface looks like:

• size() - get the number of elements in the queue
• isEmpty() - returns true if queue is empty
• enqueue()/add() - add the element to the back of the queue
• dequeue()/remove() - remove and return the element at the front of the queue
• peek() - return a reference to the first item in the queue, but do not remove it

Optional:

• rotate

Stack and queue computational complexity

Operation	Stack	Queue
Add/Push/Enqueue	O(1)	O(1)
Remove/Pop/Dequeue	O(1)	O(n) if singly linked list, O(n) if circular linked list, O(1) if array.
Peek	O(1)	O(1)
Size	O(1)	O(1)

Of course, any discussion of a data structure and its big O complexity depends heavily on the source of the implementation, how complex it is, the size of the object, and the complexity of the algorithms. There is always a tradeoff to be made between space and algorithmic complexity.

Deques

Deques are double-ended queues. Like queues, they are a FIFO data structure, but they provide access at both ends.

The deque offers addFront() and addBack() methods (or, as in Python, the push() and push_left() method.)

The deque also offers removeFront() and removeBack() methods.

first()/last() offer a peek() method for either end of the deque.

Deque interface

Deque data structures implement the following methods:

• enqueueFront : add something to the front of the queue (will be the next thing to come out)
• enqueueBack : add something to the back of the queue (normal order)
• dequeueFront : remove something from the front of the queue (normal order)
• dequeueBack : remove something from the back of the queue (cutting in line)
• first : peek at first item
• last : peek at last item
• size : size of deque
• isEmpty : is deque empty
• rotate : rotate deque, move item from front to back

Dictionary/Map

The basic idea behind the dictionary or map concept is that it enables looking up data by value. Thus, you can pass it a value and have the corresponding location in the data container returned, removed, etc.

Dictionary data type

Dictionary data type is covered by Skiena in Chapter 3 Section 3. Dictionaries provide a means of storing values, and accessing them by their content. You put an item into a dictionary so that you can find it later when you need it.

Dictionary interface

A dictionary should support the following operations:

• search
• insert
• delete
• max or min
• predecessor or successor

Trees

Tree data type

Tree interface

Trees, regardless of their implementation, should support the following methods:

Position object should support:

• getElement - get data element stored at this position in the tree

Tree ADT should support these access methods:

• root() - returns position of root of tree
• parent(p) - returns position of parent of p
• children(p) - returns iterable collection with positions of children of p
• numChildren(p) - returns number of children of p

query methods:

• isInternal(p) - true if p has at least one child
• isExternal(p) - true if p has no children
• isRoot(p) - true if p is root

general methods:

• size() - size of tree/number of positions
• isEmpty() - true if tree contains no positions/no elements
• iterator() - iterator for all elements in tree (makes Tree iterable)
• positions() - returns iterable collection of all positions

Throws IllegalArgumentException if position p is bad.

Binary Tree data type

If it's binary trees we're talking about, then here are the additional methods implemented in the binary tree:

• left(p) - position of left child of p
• right(p) - position of right child of p
• sibling(p) - position of sibling of p

public interface BinaryTree<T> extends Tree<T> {}

For the sake of efficiency, we wait to implement additional methods until we have a concrete implementation that we can optimize for.

Concrete Binary Tree interface

Once we have a concrete implementation of a binary tree, we can implement concrete methods like:

• addRoot(e)
• addLeft(p,e)
• addRight(p,e)
• set(p,e)
• attach(p,T1,T2)
• remove(p)

OOP Programming Patterns

Factory Pattern Method - when assembling nodes in the tree, using a createNode() method, so we can subclass the Node types later on into other, more specialized types. Each of the three add methods - addRoot, addLeft, and addRight - make use of the createNode method to add elements to the tree.

Exceptions - the Tree should throw some kind of illegal exception when an illegal argument occurs. Can either throw IllegalArgumentException, or can extend this into an Illegal class, or &c.

The Java design pattern also makes a bit more sense:

• AbstractBinaryTree is the interface, LinkedBinaryTree is the concrete class
• Position is the interface, Node is the concrete class