Insertion Sort

Complexity: O(N^2)
Insertion sort - Wikipedia

Singly Linked List

- Unordered array has fast insertion and slow search and deletion; ordered array has fast search and slow insertion and deletion; arrays have constant size;

Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;

Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.

Unordered (unsorted) Singly Linked List

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the list
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the list
- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the list
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the list
- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of  singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Search for the item with specific value (key):

- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)

Ordered (sorted) Singly Linked List

Operations:

// TBD

Circular Queue (Ring Buffer)

Priority Queue

- has front and rear and items are inserted in the rear and removed from the front
- items are ordered by key value, so that the item with the lowest key (or the highest key) is always at the front; items are inserted in the proper position to maintain the order

Deque

Deque is Double Ended Queue: items can be added/removed from the either end of the queue.

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the queue
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the queue
- Complexity: O(1)

Peek at the front:

- Algorithm: return a value of the item from the front of the queue
- Complexity: O(1)

Peek at the back:

- Algorithm: return a value of the item from the back of the queue
- Complexity: O(1)

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the queue
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the queue
- Complexity: O(1)

Queue

- FIFO concept - First In First Out
- opposite to arrays, only one item can be read or removed at a given time - the oldest item inserted
- its size is predefined: only limited number of items can be added (pushed)
- underlying data structure can be array, vector, linked list

Usage:
- e.g. when performing tasks is slower than the rate tasks are received we want to save tasks in the same order they are received and we want first to execute the oldest tasks: we will put them in the queue

Operations:

Insertion (enqueue):

- Algorithm: item is added at the end (rear) of the queue
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Removal (dequeue):

- Algorithm: remove the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Stack

- LIFO concept - Last In First Out
- opposite to arrays, only one item can be read or removed at a given time - the last item inserted
- its size is predefined: only limited number of items can be added (pushed)
- stack overflow occurs when a new item is being added but underlying buffer is full
- underlying data structure can be array, vector, linked list

Usage:
- to check whether parentheses ({ }), braces ([ ]) and brackets (( )) are balanced
- to parse arithmetic expressions
- in algorithms applied for other data structures (e.g. traversing binary trees)

Operations:

Insertion (push):

- Algorithm: item is added on the top of the stack
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Removal:

- Algorithm: remove the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Ordered (sorted) array

- data is ordered (sorted) in ascending (or descending) key order which enables fast search algorithm - binary search (this is the main reason why we want to keep data sorted)
- can be searched with linear search as well

Binary Search Algorithm

Take the idem from the middle of the range (array of sorted elements). If its value is smaller than the searched value then take right sub-array as a new range and repeat this step.

The range will eventually drop to only one member and if its value matches the searched one - item is found.

As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.

Operations

Insertion:

- Algorithm: linear search is needed to find the first element smaller than the one to be inserted; item is inserted after it and all bigger items are shifted one place towards the end

- Complexity: O(N) (linear search) + O(N) (shifting) = 2 * O(N) ~ O(N)

Search:

- Algorithm: binary search

- Complexity: O(logN) 

Deletion:

- Algorithm: binary search to find the element; once it's found it is removed and all subsequent elements are shifted towards the array beginning

- Complexity: O(logN)(binary search) + O(N) (shifting) ~ O(N)

Unordered (unsorted) array

Array:
-  is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values

Array is created with predefined size =>
   - if there are less elements than the array size is => memory waste
   - if there are more elements that the array size is => program fails

Implementations:
- C-style array
- std::vector

Unordered arrays with no duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed
- Complexity: O(N) (because of the search)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Unordered arrays with duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position)
- Complexity: O(1)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Hash table

Hash table

Multimap

Structure:

- multimap generalizes an associative array by allowing multiple values to be associated with a single key.

Implementation:

- often as a map with lists or sets as the map values

Multimap
multimap (sgi)
multimap

Map (associative array, dictionary)

Structure:

- a collection of (key, value) pairs such that each possible key appears at most once in the collection

Operations:

- add (insert): addition of pairs to the collection
- remove (delete): removal of pairs from the collection
- reassign: modification of the values of existing pairs; binding an old key to a new value
- lookup of the value associated with a particular key

Implementations:

- Association list (linked list in which each list element (or node) comprises a key and a value)
- direct addressing into an array (efficient only when the keys are restricted to a narrow range of integers)
- Hash table
- binary search tree

C++:

std::map: Internally, the elements in the map are sorted from lower to higher (or vice versa) key value following a specific strict weak ordering criterion set on construction.

Associative array