A linked list is a linear data structure where elements (nodes) are stored in memory, connected by pointers.
Types of Linked Lists:
1. Singly Linked List:
Each node has:
Data Pointer to the next node.
Traversal is one-directional.
struct Node { int data; Node* next; };
2. Doubly Linked List:
Each node has:
Data Pointer to the next node. Pointer to the previous node.
Traversal can be both directions.
struct Node { int data; Node* prev; Node* next; };
3. Circular Linked List:
Last node points back to the first node, forming a circle.
Common Operations: 1. Insertion : At the beginning At the end At a specific position
2. Deletion : From the beginning From the end A specific node
3. Traversal : Iterate through the list to access elements.
Advantages: Dynamic memory allocation (no fixed size). Efficient insertion and deletion (compared to arrays).
Disadvantages: Extra memory required for pointers. Sequential access only (no random access).
2. Stack
Definition:
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first to be removed. Basic Operations: 1. Push: Add an element to the top of the stack. 2. Pop: Remove the top element from the stack. 3. Peek/Top: View the top element without removing it. 4. IsEmpty: Check if the stack is empty.
Implementation: 1. Using Arrays: #define MAX 100 int stack[MAX], top = -1;
void push(int x) { if (top == MAX - 1) return; // Overflow stack[++top] = x; }
int pop() { if (top == -1) return -1; // Underflow return stack[top--]; }
2. Using Linked List: struct Node {
int data; Node* next; };
void push(Node*& top, int x) {
Node* newNode = new Node{x, top}; top = newNode; }
int pop(Node*& top) {
if (!top) return -1; int val = top->data; Node* temp = top; top = top->next; delete temp; return val; }
Applications: Function call management in recursion. Undo operations in text editors. Expression evaluation and conversion (Infix to Postfix). 3. Queues
Definition:
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first element added is the first to be removed.
Types of Queues: 1. Simple Queue:
Insertion at the rear.
Deletion from the front.
2. Circular Queue:
Rear connects back to the front when the queue is full.
3. Priority Queue:
Elements are processed based on priority, not just arrival order.
4. Double-Ended Queue (Deque):
Insertion and deletion possible at both ends.
Basic Operations: 1. Enqueue: Add an element to the rear. 2. Dequeue: Remove an element from the front. 3. Peek/Front: View the front element. 4. IsEmpty: Check if the queue is empty.
Implementation: 1. Using Arrays: #define MAX 100 int queue[MAX], front = 0, rear = -1;
void enqueue(int x) { if (rear == MAX - 1) return; // Overflow queue[++rear] = x; }
int dequeue() { if (front > rear) return -1; // Underflow return queue[front++]; }
int dequeue(Queue& q) { if (!q.front) return -1; int val = q.front->data; Node* temp = q.front; q.front = q.front->next; if (!q.front) q.rear = nullptr; delete temp; return val; }
4. Binary Search Tree (BST)
Definition:
A binary search tree is a binary tree where:
1. The left child of a node contains values smaller than the node. 2. The right child contains values greater than the node.
Operations: 1. Insertion:
struct Node { int data; Node* left; Node* right; };
Node* insert(Node* root, int x) {
if (!root) return new Node{x, nullptr, nullptr}; if (x < root->data) root->left = insert(root->left, x); else root->right = insert(root->right, x); return root; }
2. Search:
bool search(Node* root, int x) {
if (!root) return false; if (root->data == x) return true; if (x < root->data) return search(root->left, x); return search(root->right, x); }
3. Deletion:
Deleting a node with:
No child (Leaf) One child Two children (replace with in-order successor or predecessor).
4. Traversal:
Inorder (LNR): Left Node Right
Preorder (NLR): Node Left Right Postorder (LRN): Left Right Node Applications: Searching and sorting. Implementing sets and maps.
5. Hashing
Definition:
Hashing is a technique to map data to a fixed-size table (hash table) using a hash function.
Hash Function:
Maps keys to indices in the hash table. Example:
int hashFunction(int key, int tableSize) {
return key % tableSize; }
Collision Handling: 1. Chaining:
Use a linked list at each index to handle multiple elements mapping to the same index.
2. Open Addressing:
Linear Probing: Search sequentially for the next empty slot.
Quadratic Probing: Search slots quadratically. Double Hashing: Use a secondary hash function.
Applications: Symbol tables in compilers. Caching (e.g., LRU Cache). Databases and file systems. Quick Tips for Preparation: 1. Focus on understanding basic operations (insert, delete, search) for all data structures. 2. Write down the differences between stacks, queues, and linked lists. 3. Practice small code snippets for traversal and insertion. 4. Revise hash table collision resolution techniques. 5. Don't forget the tree traversals (Inorder, Preorder, Postorder).
