1. Stack
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. It has two major operations: push (insert an element onto the top of the stack) and pop (remove an element from the top of the stack).
Advantages:
- Simple data structure, easy to implement.
- Provides a systematic way of managing function calls (recursion).
- Efficient in memory utilization.
Disadvantages:
- Limited in size, prone to overflow.
- Can lead to inefficiency due to the LIFO method if not managed properly.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(1)
- Deletion - O(1)
// Stack implementation in C++
#include
int main() {
std::stack s;
s.push(10); // Insert 10 onto the stack
s.pop(); // Remove top element from the stack
return 0;
}
2. Queue
A queue is a linear data structure that follows the First In First Out (FIFO) principle. It has two major operations: enqueue (insert an element at the end of the queue) and dequeue (remove an element from the front of the queue).
Advantages:
- Efficient when dealing with sequential processes (like a print queue).
- Easy to manage and maintain.
Disadvantages:
- Fixed size, can lead to queue overflow.
- Inefficient in memory allocation and deallocation.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(1)
- Deletion - O(1)
// Queue implementation in C++
#include
int main() {
std::queue q;
q.push(10); // Insert 10 into the queue
q.pop(); // Remove the element from the front of the queue
return 0;
}
3. Deque (Double Ended Queue)
A deque is a type of queue that allows insertion and removal of elements from both the front and back. In a standard deque, no priority is assigned to elements, thus they can be inserted and deleted from both ends.
Advantages:
- Flexible, as elements can be added or removed from both ends.
- Better memory utilization compared to the stack and queue.
Disadvantages:
- Complex implementation compared to the stack and queue.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(1)
- Deletion - O(1)
// Deque implementation in C++
#include
int main() {
std::deque dq;
dq.push_back(10); // Insert 10 at the end
dq.push_front(20); // Insert 20 at the front
dq.pop_back(); // Remove the element from the end
dq.pop_front(); // Remove the element from the front
return 0;
}
4. Circular Queue
A circular queue is a variant of the linear queue which follows a circular shape. The last element points to the first making the queue behave like a circle.
Advantages:
- Better memory utilization as any insertion into an empty space is feasible.
- Can be used for repetitive processes where the first process starts after the last process is finished.
Disadvantages:
- More complex to implement than a linear queue.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(1)
- Deletion - O(1)
// Circular Queue implementation in C++
#include
class CircularQueue {
private:
int front, rear, size;
int* queue;
public:
CircularQueue(int size) {
front = rear = -1;
this->size = size;
queue = new int[size];
}
void enQueue(int value) {
if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) {
return;
} else if (front == -1) {
front = rear = 0;
queue[rear] = value;
} else if (rear == size-1 && front != 0) {
rear = 0;
queue[rear] = value;
} else {
rear++;
queue[rear] = value;
}
}
int deQueue() {
if (front == -1) {
return -1;
}
int temp = queue[front];
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size-1) {
front = 0;
} else {
front++;
}
return temp;
}
};
int main() {
CircularQueue q(5);
q.enQueue(10);
q.enQueue(20);
q.deQueue();
return 0;
}
5. Array
An array is a static linear data structure where elements are placed contiguous in memory. Elements in an array can be directly accessed using indices.
Advantages:
- Fast access to elements.
- Easy to understand and use.
Disadvantages:
- Fixed size - Inefficient if the array isn't fully utilized, and limiting if more elements need to be stored.
- Insertion and deletion operations are time consuming due to the need for shifting elements.
Time Complexity:
- Access - O(1)
- Search - O(n)
- Insertion - O(n)
- Deletion - O(n)
// Array implementation in C++
int main() {
int array[5]; // Declaration of array
array[0] = 10; // Inserting 10 at 0th index
array[1] = 20; // Inserting 20 at 1st index
return 0;
}
6. Linked List
A linked list is a dynamic linear data structure where each element is a separate object. Each element or node contains a pointer that points to the next node in the list.
Advantages:
- Dynamic size - Size can be increased or decreased at run-time.
- Efficient insertions/deletions at any place in the linked list.
Disadvantages:
- Random access is not allowed. We have to access elements sequentially starting from the first node.
- Extra memory space is required for a pointer with each element of the list.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(1)
- Deletion - O(1)
// Linked List implementation in C++
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node();
head->data = 10; // Inserting 10 at the head
head->next = NULL;
return 0;
}
7. Tree
A tree is a non-linear data structure with hierarchical relationships between its elements, known as nodes. Each node in a tree has a parent node and a set of child nodes. The node without a parent is the root of the tree.
Types of Trees:
- General Tree
- Binary Tree
- Binary Search Tree
- AVL Tree
- B-tree
- Heap Tree, etc.
Advantages:
- Reflect hierarchical structure of data.
- Efficient insertion, deletion, and search operations.
Disadvantages:
- Complex data structure, hence complex to program and manage.
- Space intensive, as pointers are needed to connect nodes.
Time Complexity:
The time complexity depends on the type of tree and the operation.
8. Binary Tree
A binary tree is a type of tree where each node can have at most two children, known as the left child and the right child.
Advantages:
- Quick and easy to implement.
- Efficient traversal methods.
Disadvantages:
- In the worst case, the tree can become skewed, leading to inefficient operations.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(n)
- Deletion - O(n)
// Binary Tree implementation in C++
struct Node {
int data;
Node* left;
Node* right;
};
Node* newNode(int data) {
Node* node = new Node();
if (node == NULL) {
return NULL;
}
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
return 0;
}
9. Binary Search Tree (BST)
A Binary Search Tree is a type of binary tree where the nodes are arranged in order: for each node, all elements in the left subtree are less-than the node, and all elements in the right subtree are greater-than the node.
Advantages:
- Provides moderate access/search (quicker than Linked List and slower than arrays).
- Provides moderate insertion/deletion (quicker than arrays and slower than Unordered Linked Lists).
Disadvantages:
- In worst case, can become skewed like a linked list.
- Complex implementation of deletion operation.
Time Complexity:
- Access - O(n)
- Search - O(n)
- Insertion - O(n)
- Deletion - O(n)
However, in a 'balanced' binary search tree (AVL Trees, Red-Black Trees, etc), these operations can be performed in O(log n) time.
// Binary Search Tree implementation in C++
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node
Node* newNode(int data) {
Node* node = new Node();
if (node == NULL) {
return NULL;
}
node->data = data;
node->left = node->right = NULL;
return node;
}
// Function to insert a node in a BST
Node* insert(Node* node, int data) {
if (node == NULL) {
return newNode(data);
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
}
return node;
}
int main() {
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
return 0;
}
10. AVL Tree and Balance Factor
An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree in which the difference between the heights of the left and right subtrees (the balance factor) is not more than one for all nodes.
Balance factor of a node = height of left subtree - height of right subtree. If this factor is more than 1 or less than -1, the tree is unbalanced, and specific tree rotations are used to rebalance the tree.
Advantages:
- Ensures O(log n) time complexity for search, insertion and deletion.
Disadvantages:
- More complex to implement due to the need for maintaining balance.
Time Complexity:
- Access - O(log n)
- Search - O(log n)
- Insertion - O(log n)
- Deletion - O(log n)
11. Rotation Rules
Tree rotations are used in AVL trees to maintain their balance. There are four types of rotations: left-left, left-right, right-left, and right-right. The rotation type is determined by the 'heavy' side of the unbalanced node and its child.
- Left-Left Case: This requires a single right rotation.
- Right-Right Case: This requires a single left rotation.
- Left-Right Case: This requires a left rotation followed by a right rotation.
- Right-Left Case: This requires a right rotation followed by a left rotation.
12. Time Complexity
Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the program. It is usually expressed using Big O notation.
The most common time complexities are: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), and O(2^n), which represent constant time, logarithmic time, linear time, linearithmic time, quadratic time, cubic time, and exponential time, respectively.
13. Calculating Maximum and Minimum Number of Nodes in a Tree
The minimum number of nodes in a tree of height h (height of root node = 1) can be calculated as h.
The maximum number of nodes in a tree of height h can be calculated as 2^h - 1.
In case of binary trees:
- The minimum number of nodes in a binary tree of height h is h.
- The maximum number of nodes in a binary tree of height h is 2^h - 1.
14. Typecasting
Typecasting, or type conversion, is a method of changing an entity from one data type to another. It is used in C++ for various purposes, such as to avoid loss of data, to add greater functionality to a program, or to convert objects of one class type into those of another class type.
// Typecasting in C++
int main() {
double x = 10.3;
int y;
y = (int) x; // This will assign the value 10 to y
return 0;
}
15. BST Traversing (Pre, In, Post Order)
Tree traversal is a process of visiting (checking or updating) each node in a tree data structure, exactly once. In case of binary trees, they can be traversed in pre-order, in-order, and post-order.
15.1 Pre-order Traversal
In a pre-order traversal, the tree nodes are visited in the following order: Root, Left Subtree, Right Subtree.
void preOrder(Node* node) {
if (node == NULL)
return;
cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}
15.2 In-order Traversal
In an in-order traversal, the tree nodes are visited in the following order: Left Subtree, Root, Right Subtree.
void inOrder(Node* node) {
if (node == NULL)
return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
15.3 Post-order Traversal
In a post-order traversal, the tree nodes are visited in the following order: Left Subtree, Right Subtree, Root.
void postOrder(Node* node) {
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
cout << node->data << " ";
}
16. Spanning Tree
A Spanning Tree of a connected, undirected graph is a subgraph that is a tree and connects (spans) all vertices of the graph. In a weighted graph, a Minimum Spanning Tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.
Two popular algorithms to find the MST are Kruskal’s Minimum Spanning Tree Algorithm and Prim’s Minimum Spanning Tree Algorithm.
17. Linear vs Non-linear DS
In data structures, linear and non-linear data structures are the classifications based on the arrangement of data and the ability to change its position:
17.1 Linear Data Structures
Linear data structures have data elements arranged sequentially with each element connected to its previous and next element. The basic operations are performed in a linear order. Examples: Array, Stack, Queue, Linked List.
17.2 Non-linear Data Structures
Non-linear data structures have data elements arranged hierarchically, and each element can connect to two or more other elements, without a particular sequence. Examples: Trees and Graphs.
18. Types of Trees
Trees are a type of non-linear data structure that are used to represent hierarchical structure in a graphical form. Here are some common types of trees:
- General Tree
- Binary Tree
- Binary Search Tree
- AVL Tree
- Heap Tree
- B-Tree
- Red-Black Tree
- 2-3 Tree, etc.
19. Quick Summary
19.1 Stack
A stack is essentially a list with the restriction that insertions and deletions can only be performed at one end. This end is known as the top. The element at the other end is known as the base. Stacks are useful in various algorithms where we need to temporarily store information and retrieve it in a LIFO manner.
LIFO structure. Main operations: push (add to top), pop (remove from top), peek (get top without removing it). Useful for reversing, backtracking, and parsing tasks. O(1) for main operations.
19.2 FIFO Structure
A queue is also a list, but with the condition that insertions are performed at one end (rear), while deletions are performed at the other end (front). It follows a FIFO pattern, making it useful in scenarios where we need to maintain the order of elements.
FIFO structure. Main operations: enqueue (add to rear), dequeue (remove from front). Useful in CPU scheduling, disk scheduling, data buffering. O(1) for main operations.
19.3 Deque (Double Ended Queue)
A Deque (Double Ended Queue) is a type of queue in which insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO rule.
Insertion and deletion can be performed from either end. Combines capabilities of stacks and queues.
19.4 Circular Queue
A circular queue is a variant of the linear queue which follows a FIFO principle but with a twist: the last position is connected back to the first position making a circle. It efficiently utilizes memory that is freed after a dequeue operation.
Queue in a circular structure. Maximizes space utilization by using empty slots after dequeue operations.
19.5 Array
An array is a simple data structure used for storing an ordered list of items. The items can be the same type or different types. Arrays are useful when you need to access items by their numerical position in the list.
Fixed-size, contains elements of the same type. Random access possible, but insertions/deletions are costly due to shifting. O(1) for access, O(n) for insertion/deletion.
19.6 Linked List
A linked list is a dynamic data structure, in which data is not stored at contiguous memory locations. The concept of next points to the next node, and the last node points to null. A linked list is not suitable for direct access but efficient for insertions and deletions.
Dynamic size, contains nodes with data and link to next node. No random access but efficient insertions/deletions. O(n) for access/search, O(1) for insertion/deletion at head.
19.7 Tree
A tree is a hierarchical data structure that stores data in a sorted manner and enables search, insert, delete operations to be carried out efficiently. It's a powerful tool for organizing data in a natural hierarchy, such as a file system.
Hierarchical structure with a root node and children nodes. Used to represent hierarchical relationships, enable fast search/insert/delete operations.
19.8 Binary Tree
A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. The two children are usually differentiated as left child and right child. It is used in many algorithms due to its simple structure and ease of use.
Tree with a maximum of two children per node. Used in many algorithms for its simple structure.
19.9 Binary Search Tree (BST)
BST is a binary tree with a special property: each node has a value greater than all the values in its left subtree and less than all the values in its right subtree. This property provides a balance between the benefits of a sorted array and a linked list, allowing us to quickly search for, insert, and delete items.
Binary tree with left child node < parent node < right child node. Efficient search, insertion, deletion operations (O(log n) in ideal case).
19.10 AVL Tree (BST)
AVL tree is a self-balancing binary search tree, which means heights of two subtrees of any node differ by at most one. If at any point they differ by more than one, rebalancing is done to restore the property.
Self-balancing BST. Balance factor is the height of the left subtree - height of the right subtree and must be -1, 0, or 1. Balancing done via rotations.
19.11 Time Complexity
Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run, as a function of the length of the input. It is a theoretical estimate of the amount of time an algorithm needs to complete based on the size of the input.
Measures the time taken by an algorithm to run, as a function of the size of the input. Big O notation describes worst-case time complexity.
19.12 Calculating maximum and minimum number of nodes in a tree
In a binary tree of height 'h', the minimum number of nodes can be 'h' (if each level only has one node) and the maximum number of nodes can be 2^h - 1 (if each level is fully populated).
For a binary tree with 'h' height, min nodes = h, max nodes = 2^h - 1.
19.13 Typecasting
Typecasting is a way to convert a variable from one data type to another. This is used when you want to use a variable of one type as if it were a different type.
Converting a variable from one data type to another.
19.14 BST Traversing
Traversing is visiting every node in the BST. There are three common ways to traverse them in a depth-first order: Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root).
Preorder (root, left, right), Inorder (left, root, right), Postorder (left, right, root).
19.15 Spanning Tree
In graph theory, a spanning tree T of a connected, undirected graph G is a tree that includes every vertex of G, with minimum possible number of edges.
Tree that includes all vertices of a graph. Minimum spanning tree (MST) is a spanning tree with minimum total edge weight.
19.16 Linear vs Non-linear Data Structures
Linear data structures have data elements arranged in a linear order where each element is connected to its previous and next element. Non-linear data structures are those data structures in which data elements are not in sequence, i.e., they are arranged hierarchically.
Linear - elements arranged in a sequence (Array, Stack, Queue, Linked List). Non-linear - hierarchical arrangement of elements (Trees, Graphs).