data_structures
Linked Lists
Yeah the good old. Can be singly linked lists, doubly, circular etc. Mostly the idea is to keep a decent brain while writing this stuff out.
Stack
Last in first out. Can be made using an array by having a back pointer, that keeps moving back and forth as and when elements come up. Same with linked lists, have a pointer to the last node in the list and insert and remove accordingly.
Queue
First in first out. Circular buffer. first
points to an element that is empty and right behind the first filled element. last
points to the position where the element is going to be filled next. One extra node is always kept empty.
- Empty:
last = (first + 1) % size
- Full:
last = first
Deque
Basically a stack and queue together.
Trees
A linked list with two pointers instead of one. Basically having a right child and a left child. Mostly class implementations will also be having a parent pointer.
- Full tree: Every node has 0 or 2 children.
- Complete tree: Filled in level order fashion.
- Perfect tree: 2n - 1
Binary Search Tree
All nodes on the right side of the current node are smaller in value than the current node. All on the right are greater than the current node.
- Balancing (AVL): Need to do a left rotate or a right rotate. Or a double rotate.
Binary Heap
The top element is the minimum or maximum. All the elements below one node are larger than it (or smaller than it).
Hash tables
Basically an array. Takes a hash function (like modulo p) and insert it in the position of h(x). If there are collisions (two inputs having the same hash), there are two approaches to resolve this.
-
Linked list: It is called something I can’t remember. Basically start inserting everything that collides into a linked list.
-
Probing: Not what you think it is. It has categories.
- Linear probing: if h(x) is filled, go to h(x) + 1 mod p. Keep going till you find a spot that is empty or deleted.
- Quadratic probing: Go to h(x) + k2 : if p is a prime, then you are guaranteed to find an empty bucket in p/2 probes.
If searching in the probing method, you get a cell that is deleted, then keep proceeding for the search. If you get a cell that is empty, however, the search should stop there because if the searched element was in the table, it would have occupied that one. Use an enum to keep track of full, empty and deleted.