Here is a list of the 5 most essential abstract data types you MUST know if you wish to be a competent programmer, with appropriate exercises for each.
Linked list
A linked list is similar to an array, in that it stores a ‘list’ of data. However, instead of contiguous memory, each element in the linked list is stored separately, and connected to the next one through pointers:
C-Code example
typedef struct Node
{
uint32_t data; // use any data type you need
Node* next; // must be set to NULL or next node in list
}
Node;Advantages
- Dynamic arrays
- Easy insertion/deletion (O(1))
Disadvantages
- Cannot do random-access
- Therefore, searching is inefficient as algorithms such as binary search cannot be used (so search is O(n) instead of O(log2(n)))
Further inspection
- Circular linked lists — last element points back to start
- Doubly linked list — holds both next and previous node. May also be circular
Queue
A queue, once again holds contiguous data, however, only of a specific size, and data is stored into the queue in a FIFO (first in, first out) order.
C-Code example
typedef struct Queue
{
int front, rear, size;
int* array; // initialise to malloc(size*sizeof(int))
}
Queue;Advantages
- Enqueue, dequeue, and getting front and rear are O(1).
- Useful in situations which operate under FIFO
Disadvantages
- Fixed size
- May result in overflow as if we keep dequeuing the beginning and enqueueing at the end, the indices get too large.
Further inspection
- Circular queue: indices loop back, so that even if we dequeue and everything is shifted one over, we don’t run out of space
- Priority queue — Like a queue but each element has a value associated with it, such that more ‘important values are dequeued before. (For example, if the priority is how large the number is, then dequeueing will not remove the first element input, but rather the largest)
Stack
A stack is the same thing as a queue except with a LIFO (last in first out) structure.
Instead of en/de-queueing, you can push from the front or pop from the back.
C-Code example
typedef struct Stack
{
int *arr;
int size;
int t; // must be inited to -1
}
Stack;// example of push and of pop
void push(Stack& s, int i)
{
s.t++;
if (s.t == s.size) return; // overflow
*(s.arr+s.t) = i;
}int pop(Stack& s)
{
if (s.t == -1) return; // underflow
int r = *(s.arr+s.t);
s.t--;
return r;
}
Uses
- ‘Towers of hanoi’ architecture: things are put in the and taken out of the same side
Further inspection (exercises for the reader)
- Mergeable stacks: hint: using linked lists
- Implement a Stack using Queues or vice versa.
Binary tree
Non-linear hierarchical representation. It has no upper bound since it is stored using pointers. It can be used for file storage, decision trees and router algorithms amongst other uses. You can insert, remove, search and traverse trees.
C-Code example
typedef struct Node
{
int data;
Node *left, *right;
}
Node;Advantages:
- Insertion is faster than linked lists and arrays,
- reflects structural relation
- can be used (similar to priority queue) to find min in O(1)
Disadvantages:
- Slow access and deletion
- Many pointers are null and unused
Further inspection:
- Traversal and reversal of binary tree
- Search algorithms such as depth-first search and breadth-first search
- Foldable binary trees
Heap
A heap is a complete binary tree. It is very important as it is fundamental in computers and programming languages.
C-Code
typedef struct Heap
{
int *arr; // since we know it is fully populated, we can predict
// array size
int size;
int max_size;
}
Heap;Note that heap is stored sorted either min or max at root.
Advantages:
- insertion and deletion in O(log(n)) (better than regular array)
- Min and max are efficient
Disadvantages:
- insertion and deletion in O(log(n)) (worse than binary tree for insertion and worse than linked list). This is because it is sorted.
- ‘Heapifying’ an array is costly O(n log(n))
Further inspection
- Fully functional heap
- Fibonacci heap
- Connect ropes at minimum cost / Huffman’s coding
END
There you go! I hope that was enough to get you started (I didn’t want to give too much away…), and enough to point you in the right direction without spoiling the joy of learning these for yourself. If you liked this article, certainly drop a clap and follow me.