Abstract Data Types

Posted on August 3rd, 2022

Talks aboutComputer Science

Producing software with a real-world purpose means translating a high-level problem into something computational. When considering its data, we don't immediately jump to CREATE TABLE; we start by considering what data is needed, how it relates, and how we can represent it.

For example, we can represent a Person with a Map, with keys to identify something about them and corresponding values. More technically, we can model a List data type with the functions insert, find, reduce without specifying it as an array or linked list.

An Abstract Data Type (ADT) is a model for a data type defined by its behaviour from the perspective of a consumer, not its implementation.

Basically, it's what it does, not how it does it.

Double-Ended Queue

Think of browser history (😬). Values are added and removed from the front as navigation moves forwards and backwards; to limit its size, the oldest values are removed from the back.

The double-ended queue ADT (or dequeue, or deque, pronounced 'deck') is generally defined with:

addFront(x)
addBack(x)
peekFront()
peekBack()
removeFront()
removeBack()
size()

Both a circular array and a linked list can implement a deque. Neither is perfect, as they are both $\mathcal{O}(n)$ when inserting and indexing/searching respectively.

The following structures can also use a deque as a backing structure.

Queue

Think of a queue. Values are only added to the back and are only removed from the front, making it first in, first out (FIFO).

A queue is a generally defined with:

Function	Using Deque
`enqueue(x)`	`addBack(x)`
`peek()`	`peekFront()`
`dequeue()`	`removeFront()`

Stack

Think a pile of plates ready for the washing up. Values are added and removed to the front, making it last in, first out (LIFO).

A stackis generally defined with:

Function	Using Deque
`push(x)`	`addFront(x)`
`peek()`	`peekFront()`
`pop()`	`removeFront()`

Priority Queue

Think of the queue in A&E. It's still FIFO but the elements are reordered by their priority, making it highest priority in, first out (HPIFO).

A priority queue is generally defined with:

insert(x)
peek()
pop()

Implementing a priority queue with a list structure realises an issue: a sorted linked list would result in $\mathcal{O}(1)$ to peek and remove, but $\mathcal{O}(n)$ to insert into a sorted position. An unsorted linked list swaps the time complexities and array implementations suffer the same pain.

Instead we can use a heap, giving us $\mathcal{O}(1)$ to peek and $\mathcal{O}(\log n)$ to insert/remove.

Map

There's lots of associated data: a students name and their grade, a customer's account number and their balance, etc.

A map uses a key to identify data and a value to store the data. They are generally defined with

put(key, value)
get(key)
remove(key)
size()
has(key)

When inserting a duplicate key, the value is generally overwritten but C++ deviates from this with its unordered_map().

We can implement maps with many data structures but random lookup is often prioritised by using hash maps. That said, a binary search tree could keep the keys ordered while sacrificed that sweet sweet constant lookup time complexity of a hash map.