- size is static and bounded, dynamic resizing not possible
- insert requires shifting out subsequent elements to right
- delete requires shifting out subsequent elements to left
- A data structure that holds a pointer head to a chained link of nodes.
- Each node contains 2 parts:
- data: holds the data
- next: holds link to the next node
- No random access.
- To reach a node, always start from the head and traverse.
- insert
- delete
- search
- Given a sequence of operations, print the state after each operation
class Node {
int data;
Node next;
}
class LinkedList {
Node head;
void insert(int pos, int key);
void insert(int key);
boolean delete(int pos);
int search(int key); // returns position
int size();
void insertFirst(int key);
void deleteFirst();
}
For a step-by-step implementation of LinkedList, please refer to Linked List implementation step-by-step.
- In a single traversal find the middle element/position
- Design linked list
- Merge two sorted lists into one
- Rotate a linked list by k positions
- Remove duplicates from a sorted list
- Partition list based on > and <= x
- Remove linked list elements
- Intersection of two linked lists
- Reverse a linked list
- Check if a linked list has a cycle
- When inserts/deletes are more, use LinkedList
- Otherwise ArrayList
- Last node links back to first node
- Can reach the first node from the last node
- insert
- delete
- search
- Rotate right k times
- Rotate left = rotate right size - k times
- insert and delete needs modification to set the next back to head
- search needs modification to stop traversal as soon as next points to head
- Contains pointer to first node head
- Each node contains 3 parts:
- data: holds the data
- prev: holds pointer to previous node
- next: holds pointer to next node
- Can traverse in both left and right directions
- insert
- delete
- search
- insert and delete needs modification to set both prev and next
For the implementation of doubly linked list, visit Doubly Linked List.
- A data structure that holds pointer (top) to a chained link of nodes
- A new node is pushed onto the stack, and it becomes the new top
- Delete pops the top node from the stack, the below node becomes the top
- It can be seen as restricted linked list that supports insert first (last) and delete first (last)
- LIFO: Last-In-First-Out
- Insert and delete at one end only
- push
- pop
- peek
class Node {
int data;
Node next;
}
class Stack {
Node top;
void push(int key);
int pop();
int peek();
int size();
}
For the implementation of stack and its applications, please refer to Stack and its applications.
- Reverse
- Check palindrome
- Balanced parantheses
- Postfix evaluation
- Basic calculator - Infix to postfix + postfix evaluation
- Min stack
- Remove k digits
- Decode string
- Backspace string compare
- Score of parantheses
- A data structure that holds pointers (front, rear) to the first and last nodes of chained link of nodes
- A new node is enqueued to the rear
- Node is removed from the front
- It can be seen as restricted linked list that supports insert last and delete first
- FIFO: First-In-First-Out
- Insert at one end and remove from the other end
- enqueue
- dequeue
- peek
class Node {
int data;
Node next;
Node(int d);
int getData();
Node getNext();
}
class Queue {
Node front;
Node rear;
void enqueue(int key);
int dequeue();
int peek();
int size();
}
For the implementation of queue in its different forms, please refer to Queue implementation.
- Task scheduler
- Stack using queue
- Queue using stack
- Circular Queue
- Circular Deque
- Number of recent calls
- A non-linear representation of nodes where each node links to 0, 1 or 2 child nodes
- Child nodes are referred to as left and right
- Topmost node is called root
- Access to any node always starts with the root
- Level-order: Level-by-level from top to bottom, at each level left to right
- 25 48 16 11 37 64 76 83 51 93
- Preorder: visit(node), preorder(left), preorder(right)
- 25 48 11 76 83 37 51 16 64 93
- Inorder: inorder(left), visit(node), inorder(right)
- 76 11 83 48 37 51 25 16 93 64
- Postorder: postorder(left), postorder(right), visit(node)
- 76 83 11 51 37 48 93 64 16 25
- insert
- delete
- search
- preorder
- inorder
- postorder
class Node {
int data;
Node left;
Node right;
Node(int d);
boolean search(int key);
boolean insert(int key);
boolean delete(int key);
void preorder();
void inorder();
void postorder();
}
class BinaryTree {
Node root;
boolean search(int key) { root.search(key); }
boolean insert(int key) { root.insert(key); } // Implementation depends on the type of binary tree
boolean delete(int key) { root.delete(key); } // Implementation depends on the type of binary tree
void preorder() { root.preorder(); }
void inorder() { root.inorder(); }
void postorder() { root.postorder(); }
}
- Expression tree
- Huffman encoding
- Inorder traversal
- Preorder traversal
- Level order traversal
- Same tree
- Symmetric tree
- Max depth
- Diameter
- Lowest common ancestor
- Longest univalue path
- Construct BT from preorder & inorder
- Min heap
- Max heap
- A binary tree in which each node's value is less than that of its left and right nodes
- A binary tree in which each node's value is greater than that of its left and right nodes
- Access starts from the root
- Min Heap property: parent < left, right
- Min element at the root
- Max Heap property: parent > left, right
- Max element at the root
- No constraints between left and right
- Can be implemented as array for fast access
- Level-order (array implementation suits this)
- parent(i) = (i-1)/2
- left(i) = 2i + 1
- right(i) = 2i + 2
- insert
- getMin (or getMax)
class MinHeap {
int[] arr;
int root;
int size;
MinHeap() { arr = int[100]; root = 0; size = 0; }
int getParent(int i) { return (i-1)/2; }
int getLeft(int i) { return 2*i + 1; }
int getRight(int i) { return 2*i + 2; }
void buildHeap();
void insert(int key);
void fixHeap();
int getMin();
}
For a step-by-step implementation of MinHeap (a.k.a PriorityQueue), please refer to Min Heap implementation step-by-step.
- Heap sort
- Implement priority queue
- Kth largest element in an array
- Top K frequent elements
- Sort chars by frequency
- Split array into consecutive subsequences
- Top k frequent words
- Last stone weight
- K closest points to origin
- Distant bar codes
- Kth largest element in a stream
- Network delay time
- A binary tree in which a node's value is greater than its left and smaller than its right
- To search faster
- It takes O(n) time to search in a linked list
- BST provides a way to reduce search time to O(logn)
- Not always though!!!
- Access starts from the root
- left < data < right
- Inorder traversal results in sorted sequence
- Usually inorder to retrieve sorted sequence
- Other traversals are also common
- insert
- delete
- search
- preorder, inorder, postorder
class Node {
int data;
Node left;
Node right;
Node(int d);
boolean search(int key);
boolean insert(int key);
boolean delete(int key);
void preorder();
void inorder();
void postorder();
}
class BST {
Node root;
boolean search(int key) { root.search(key); }
boolean insert(int key) { root.insert(key); }
boolean delete(int key) { root.delete(key); }
void preorder() {root. preorder(); }
void inorder() { root.inorder(); }
void postorder() { root.postorder(); }
}
For a step-by-step implementation of LinkedList, please refer to Binary Search Tree implementation.
- search: traverse recursively taking appropriate path at each level until node containing search element is found or leaf node is reached
- insert: traverse recursively taking appropriate path at each level until point of insertion identified
- delete: search, remove the node, replace it with the node containing next higher element
- preorder: starting from root, traverse in node, preorder(left), preorder(right) manner
- inorder: starting from root traverse in inorder(left), node, inorder(right) manner
- postorder: starting from root traverse in postorder(left), postorder(right), node manner
- Insert BST
- Search BST
- Delete BST
- Validate BST
- Trim BST
- Lowest Common Ancestor
- Sorted array to BST
- Recover BST
- Find Mode in a BST
- Minimum distance between BST nodes
- A binary search tree which is height-balanced
- Height balanced: The height of the left and right subtrees differ by at most 1
- Usually inorder
- for retrieving sorted sequence
- Other traversals are also common
- insert, delete, search
- preorder, inorder, postorder
- rotateWithLeft
- rotateWithRight
- computeBalance
- height
class Node {
int data;
Node left;
Node right;
int balanceFactor;
Node(int d);
boolean search(int key);
boolean insert(int key);
boolean delete(int key);
void preorder();
void inorder();
void postorder();
void rotateWithLeft();
void rotateWithRight();
}
class AVLTree {
Node root;
boolean search(int key) { root.search(key); }
boolean insert(int key) { root.insert(key); }
boolean delete(int key) { root.delete(key); }
void preorder() { root.preorder(); }
void inorder() { root.inorder(); }
void postorder() { root.postorder(); }
}
The AVL Tree implementation is given here
- Median of two sorted arrays
A non-linear data structure that contains a group of node/vertices where each node/vertex maintains a list of adjacent nodes.
- Adjacency List
0: 1 -> 2
1: 4
2: 1 -> 4
3: 0 -> 2 -> 4
4:
- Adjacency Matrix
------------
.| 0 1 2 3 4
------------
0| x 1 1 0 0
1| 0 x 0 0 1
2| 0 1 x 0 1
3| 1 0 1 x 1
4| 0 0 0 0 x
------------
- Edge List
(0,1) (0,2) (1,4) (2,1) (2,4) (3,0) (3,2) (3,4)
- Incidence List
0: 3
1: 0 -> 2
2: 0 -> 3
3:
4: 1 -> 2 -> 3
- Incidence Matrix
------------
.| 0 1 2 3 4
------------
0| x 0 0 1 0
1| 1 x 1 0 0
2| 1 0 x 1 0
3| 0 0 0 x 0
4| 0 1 1 1 x
------------
-
Depth First Search (DFS)
-
Breadth First Search (BFS)
- addEdge
- dfs
- bfs
- connectivity
- path, cycle
- components
For a step-by-step implementation of a graph, please refer Graph Implementation.
- Find eventual safe states
- Clone graph
- Course schedule
- Reconstruct itinerary
- Is graph bipartite
- Cheapest flight within K stops
- Snake and ladder
- Connected component & cycle
- DFS Edges
- Rotting oranges
A disjoint set data structure is a collection of sets that are disjoint with each other. Also, there are no duplicates in each set.
- Items are unordered
- No duplicates
- Union
- Find
class Node {
int label;
Node parent;
Node(int l);
}
class DisjointSet {
Node[] arr;
void makeSet(int size);
int find(int key);
void union(int key1, int key2);
}
For a step-by-step implementation of Disjoint-Set, please refer to Disjoint-Set implementation
A data structure that stores <key,value> pairs.
- put
- get
- remove
class Node {
int key;
int value;
Node(int k, int v);
}
class HashTable {
Node[] harr;
int hash(int key);
void put(int key, int val);
int get(int key);
boolean contains(int key);
void remove(int key);
}
For a step-by-step implementation of HashTable, please refer to Hash Table implementation