Linked Lists
This data structure is a series of nodes linked together linearly. Each node has at minimum two values: node data (content) and node next/reference (points to the node it is “linked” to). This simple data structure is the base for other types of structures, including stacks and queues.
Pros:
- Insertion and deletion of elements can be very quick
- Prepending items (at beginning) takes O(1) constant time while appending items (at end) takes O(n) time (must go through each element in the list before reaching the end)
Cons:
- Searching a linked list is extremely slow to find a n-th element since the elements are not indexed (as they are indexed in an array). Searching a linked list has O(n) runtime.
Hash Tables
This data structure takes a value, computes the value into a key through a hash function, and maps the key into an index in an array*.
string → hash code (some computation) → index
The array of indices is often smaller than the number of hash codes, so two input values could have different hash codes and yet still map to the same index in the array. This is called a collision, and it’s not good. To get around this problem, we can use an array of linked lists. At each array index, there will be a linked list object that contains a series of key=>value pairs.
Given a series of names (Christy, Alex, Kevin, Sarah, Bob), an array with size 4, and some hash function, the hash table may look like the following:
a[0] = (P0, "Christy"), (P1, "Alex"), (P2, "Kevin")
a[1] = (P3, "Sarah")
a[2] = (P4, "Bob)It is only possible to have multiple objects at a[0] because of the linked list structure.
A good hash table should have O(1) runtime for all insert, find, and delete actions.
Trees
The tree data structure sounds similarly to what you imagine a tree would be like, only inverted:
Every tree structure has a single root from which child nodes will spawn. Each node will have a parent and can have multiple or no children. Nodes with no children are called leaves. A binary search tree (BST) is the most common of the trees, with the following qualities:
- Each node has 0–2 child nodes (child nodes can be null)
- At any subtree (a single parent + child nodes unit), the value of the left node < value of parent/root node < value of right node
- At each operation (e.g. search), half of the nodes will be eliminated.
Trees can be balanced or unbalanced:
A balanced binary tree will have O(log n) runtime for insert/find operations, while an unbalanced tree will have O(n) runtime for the same operations. In a balanced BST, each recursive operation will be performed on half of the previous operation’s nodes, but that is not the case for an unbalanced BST.
So how would you traverse (walk through) any tree?
There are 3 methods: inorder, preorder, and postorder. Imagine a subtree with root B and children A and C:
inorder: left -> root -> right (A -> B -> C)
preorder: root -> left -> right (B -> A -> C)
postorder: left -> right -> root (A -> C -> B)Binary search generally will traverse using inorder and print the elements of the tree in order.
Heaps
Heaps are a special type of tree that satisfies the heap property: the relationship between a parent node P and child nodes C is constant throughout the entire tree. If any P is greater than it’s C, all P nodes will be greater than its C nodes. There are two types of heaps:
- Min Heap — the root is always the smallest element, and P < C for all subtrees
- Max Heap — the root is always the largest element, and P > C for all subtrees
The heap (an implementation of the priority queue) is not sorted, but partially ordered based on the above types.
Taking an example of a min heap, what happens during insertion and deletion of elements in the heap?
Insertion:
- The element to insert A will always be inserted in the next available node spot, from top to bottom and left to right. This is generally at the bottom of the tree at one of the leaves.
- If A does not belong in that spot (if root node value is 4 and A value is 2, then the newly inserted element should be the new root node), compare A with it’s immediate parent P. If A < P, swap locations. Continue the process of comparing A with P until A is in it’s right location (bubbling up the tree)
Removing the Min Element
- Since the minimum element of a min heap is always the root, remove the root.
- Replace the root with the last element added (the last leaf in the heap) and compare the root R with its children C.
- While R > C, swap locations with the smaller of the two Cs. Continue the process of comparing R with C until R is in it’s right location and the heap structure is resorted (bubbling down the tree).
A heap can also be visualized as an array (each node has an index) when implementing a heap in code.
Stacks and Queues
These two, mentioned early under linked lists, are linear data structures with a flexible size. The main difference between the two comes from how items are removed.
Stacks — LIFO
Never thought I’d come across LIFO outside accounting for inventory, but here it is. LIFO stands for “Last In, First Out”. The last pancake placed on your stack is the first one you eat.
Implementing a stack is relatively easy; there is no need to keep track of a head node and a tail node since all of the action happens at the top of the stack. Common methods are:
Push() // add item A to stack and set A as topnode = Node.new(data)
node.next = top
top = node Pop() // remove item A from stack and set A.next as toptop = top.next
Queues — FIFO
Queues have opposite behavior from stacks. FIFO stands for “First In, First Out”. The first pancake at the bottom of your stack is the first one you eat. But of course not — who eats pancakes like that?
Implementing a queue requires keeping track of a head node and a tail node since you remove from the head and add to the tail. The add/remove methods in a queue may look like this:
Add()
node = Node.new
if (tail != nil), tail.next = node // if there is a tail, append node to tail if (head == nil), head = node // if there is no data (empty structure), create head
Remove()
data = head.data // save this to-be removed data
head = head.next // set a new headif (head == nil), tail == nil // if head is empty, there is no data, so empty the tail
SO there you have it: 6 data structures (5 if you count stacks and queues as one) in minutes! My next step is to implement each in Ruby and test. Please leave a note if you have an easier way to learn/understand these or if you found this helpful!
