# Abstract Data Types

### From charlesreid1

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

# Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |