ADT
The theory they talk about in school that is never used after the exam
A abstract data type (ADT) is a model to describe the operations of a data structure. The details of how it works or store the data below the surface of the interface depend on the language one write it in. ADT is a way to talk about algorithms or how to do things without the details how it work on a lower level.
Abstract
Stack
In a stack things are stored in Last-In-First-Out (LIFO) data structure. Things are added to the stack with push and removed from the stack with pop. Peek can be used to look at the top element without removing it.
push(T)
T pop()
T peek()
Queue
This is a First-In-First-Out (FIFO) data structure. Add things in one end with push and get them out at the other end with pop.
push(T)
T pop()
T peek()
Double-ended queue
In a Double-ended queue one can add and remove items for the front or the back of the queue.
push_back(T)
push_front(T)
T pop_back()
T pop_front()
T back()
T front()
Priority queue
In a Priority queue each element needs a priority that tells the queue how important the element is compared to another element. Then when one get the front element or peek at the queue it will return the element with the highest priority.
push(T, priority)
T pop()
T peek()
Set
A set contains elements without any particular order, and no repeated values. The common operation is to check whatever a element is part of a set. Sets also support operations (union, intersection, difference) to combine a set with another in different ways.
push(T)
pop(T)
peek(T)
set union (set a, set b) - Return a new set the contain all the elements from set a and b.
set intersection(set a, set b) - Return a new set of the elements that are in both sets.
set difference/(set a, set b) - Return a set with the things in B that is not in. b - a.
bool subset(set a, set b) - Returns true if all items in A is also found in A.
Map
A map store each element (t) linked to a specific key (k). So to insert a element one use push(k, t) and the same element can be added multiple times as long as different keys are used. Pop(k) returns the element and peek(k) can be used to check if any element exist bound to the given key.
Linked
Linked list
A linked list is made up of nodes that contain the data and also a next pointer that point to the next node. The final node in the list have next set to NULL. The list itself start with a pointer to the first node.
Circular Linked Lists and Branching - 2015
Doubly linked list
A double linked list is like a linked list by each node also have a prev pointer that point to the node before it.
Trees
Binary search tree
B-tree
Introduction to B-Trees - 2008
Heap
Binary Heaps in C - 2016
R-tree
R-trees – adapting out-of-core techniques to modern memory architectures - 2010