Data Structure Algorithms: Linked Lists, Trees, and Hashing
SINGLY LINKED LIST
// Insert at beginning 0
Algorithm InsertAtBeginning(data)
:1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->next = head4. head = newNode
// Insert at endAlgorithm InsertAtEnd(data):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->next = NULL4. If head == NULL:
head = newNodeElse:temp = headWhile temp->next != NULL:temp = temp->nexttemp->next = newNode;
// Insert at position Algorithm InsertAtPos(data, pos):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. Temp = head4. Loop i from 1 to pos – 1:
temp = temp->next5. NewNode->next = temp->next6. Temp->next = newNode Deletion in Singly Linked List
// Delete from beginning Algorithm DeleteFromBeginning(): 1. If head == NULL:Print “List is empty” 2. Temp = head 3. Head = head->next 4. Free(temp)
// Delete from end Algorithm DeleteFromEnd():1. If head == NULL:Print “List is empty”2. Temp = head3. While temp->next->next != NULL; temp = temp->next4. Free(temp->next) 5. Temp->next = NULL
// Delete from position Algorithm DeleteAtPos(pos):1. If head == NULL: Print “List is empty” 2. Temp = head 3. Loop i from 1 to pos – 1: prev = temp temp = temp->next 4. Prev->next = temp->next 5. Free(temp)
Circular Linked List // Insert at beginning
Algorithm InsertAtBeginning(data):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. If head == NULL:
newNode->next = newNode
head = newNode4. Else: temp = head While temp->next != head: temp = temp->next newNode->next = head temp->next = newNode head = newNode
// Insert at end Algorithm InsertAtEnd(data): 1. NewNode = (Node*)malloc(sizeof(Node)) 2. NewNode->data = data 3. If head == NULL: newNode->next = newNode
head = newNode 4. Else: temp = head While temp->next != head: temp = temp->next temp->next = newNode newNode->next = head
Deletion in Circular Linked List // Delete from beginning
Algorithm DeleteFromBeginning(): 1. If head == NULL: Print “List is empty” 2. If head->next == head: free(head) head = NULL 3. Else:temp = head last = head While last->next != head: last = last->next head = head->next last->next = head free(temp)
// Delete from end
Algorithm DeleteFromEnd(): 1. If head == NULL: Print “List is empty” 2. Temp = head 3. While temp->next->next != head: temp = temp->next 4. Free(temp->next) 5. Temp->next = head
Doubly Linked List
// Insert at beginning
Algorithm InsertAtBeginning(data):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->prev = NULL4. NewNode->next = head5. If head != NULL: head->prev = newNode6. Head = newNode
// Insert at end
Algorithm InsertAtEnd(data):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->next = NULL4. If head == NULL: newNode->prev = NULL
head = newNode 5. Else: temp = head While temp->next != NULL: temp = temp->next temp->next = newNode newNode->prev = temp Deletion in Doubly Linked List
// Delete from beginning
Algorithm DeleteFromBeginning(): 1. If head == NULL: Print “List is empty” 2. Temp = head 3. Head = head->next 4. If head != NULL: head->prev = NULL 5. Free(temp)
// Delete from end
Algorithm DeleteFromEnd(): 1. If head == NULL: Print “List is empty” 2. Temp = head 3. While temp->next != NULL: temp = temp->next 4. If temp->prev != NULL: temp->prev->next = NULL 5. Else: head = NULL 6. Free(temp)
Part A: Infix to Postfix Conversion
Infix expression: Operators are placed between operands (e.G., A + B)..Postfix expression: Operators follow operands (e.G., AB+)..Algorithm to convert Infix to Postfix:..1…Create an empty stack for operators…2. Scan the infix expression from left to right…3. If the token is an operand:..Add it to the postfix expression…4. If the token is ‘(’:..Push it to the stack….5. If the token is ‘)’:…Pop and append operators until ‘(’ is found. Discard ‘(’…..6. If the token is an operator (op1):…While the stack is not empty and precedence of top of stack ≥ op1:..Pop and append to postfix…Push op1 onto the stack…7. After the expression is scanned:..Pop all remaining operators and append them to..Postfix…Example: Infix: A + B * C Postfix: A B C * +.
.Part B: Postfix Expression Evaluation.
.Algorithm to evaluate Postfix Expression:..1. Create an empty stack…2. Scan the postfix expression from left to right…3. If token is operand:Push it onto the stack…4. If token is operator:..Pop two operands from stack…Apply the operator and push theresult back to stack…5. After scanning, the result will be on the top of the stack.
Example: Postfix: 5 3 2 * + Step 1: Push 5 → [5] Step 2: Push 3 → [5, 3] Step 3: Push 2 → [5, 3, 2] Step 4: * → Pop 3 & 2 → Push 6 → [5, 6] Step 5: + → Pop 5 & 6 → Push 11 → [11] Result: 11
Case a) Leaf Node (No Children):If the node is a leaf, it can simply be removed without affecting the structure.Case b) Node with One Child:Replace the node with its child node (either left or right).Case c) Node with Two Children:Find the inorder successor (smallest node in the right subtree) or inorder predecessor (largest in the left subtree), copy its data to the current node, and delete the successor/predecessor.
Algorithm:
Delete(node, key)
:1. If node == NULL:..Return NULL..2. If key < node->data:..Node->left = Delete(node->left, key)..3. Else if key > node->data:..Node->right = Delete(node->right, key)..4. Else:..// Node found..A) If node has no child: ..Free(node)..Return NULL….B) If node has one child:..Temp = node->left ? Node->left : node->right..Free(node)..Return temp..C) If node has two children:..Temp = FindMin(node->right)..Node->data = temp->data..Node->right = Delete(node->right, temp->data)..5. Return node
FindMin(node):…While node->left != NULL:….Node = node->left….Return node
a heap is a complete binary tree that satisfies the heap property, which varies based on whether it is a max heap or a min heap. It is typically implemented using an array. types of heap: 1. Max heap •the value of the parent node is greater than or equal to the values of its children. •the root node contains the maximum value.2. Min heap:•the value of the parent node is less than or equal to the values of its children.•the root node contains the minimum value.Heap representation:a heap is stored as an array where:•parent(i) = i / 2•leftchild(i) = 2 * i•rightchild(i) = 2 * i + 1(indexing can be 0-based or 1-based based on implementation.)
algorithm to insert into a max heap (in c-style steps):insert(heap[], n, key): 1. Increase heap size: n = n + 1 2. Place key at heap[n] 3. I = n4. While i > 1 and heap[i] > heap[i / 2]: swap(heap[i], heap[i / 2]) i = i / 2 •this bubbles up the new element to maintain the max heap property.Algorithm to delete root from a max heap:deleteroot(heap[], n):1. Replace root with heap[n]2. Decrease heap size: n = n – 13. I = 14. While i has at least one child:maxindex = if left child exists and heap[left] > heap[maxindex]:maxindex = leftf right child exists and heap[right] > heap[maxindex]:maxindex = right
If maxindex == i:breakswap(heap[i], heap[maxindex])i = maxindex•this bubbles down the root to restore the heap structure.Building a max heap from an array (heapify process):buildmaxheap(heap[], n):1. For i = n/2 down to 1:maxheapify(heap, i, n)maxheapify(heap[], i, n):1. Largest = i2. Left = 2 * i3. Right = 2 * i + 14. If left ≤ n and heap[left] > heap[largest]:largest = left5. If right ≤ n and heap[right] > heap[largest]:largest = right6. If largest ≠ i:
swap(heap[i], heap[largest])maxheapify(heap, largest, n)this approach ensures o(n) time complexity for building a heap.Example:given array: [4, 10, 3, 5, 1]
•after building max heap: [10, 5, 3, 4, 1]
A B-tree of order m is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. For order 3 (m = 3), each node can have at most 2 keys and 3 children.
Properties of B-tree (Order 3):•Every node can have at most 2 keys (m-1 keys).•Every node except root must have at least 1 key (⌈m/2⌉ – 1).•The root node can have at least 1 key.•All leaf nodes appear at the same level.•Keys in nodes are sorted.•Children’s pointers separate the keys into ranges.Insertion Procedure in B-tree of order 3:
1.Start at the root node.2.Find the correct leaf node where the new key should be inserted by comparing keys.3.If the node has less than 2 keys, insert the key in sorted order.4.If the node has 2 keys (full):oInsert the key temporarily to have 3 keys.OSplit the node into two nodes:▪The middle key moves up to the parent.▪Left and right keys become separate nodes.5.If the parent node is also full, recursively split and push up.6.If splitting reaches the root, create a new root.7.Repeat for all n keys.
Stepwise Algorithm: BTree_Insert(root, key):1. If root is NULL:Create a new node with key and assign as root2. Else:node = root while node is not leaf:Find the child pointer where key should gonode = child3. Insert key into leaf node in sorted order4. If leaf node overflows (has m keys):Split nodePush middle key to parentIf parent overflows, recursively split5. If root overflows, create a new rootExample:Insert keys: 10, 20, 5, 6, 12, 30, 7, 17 into a B-tree of order 3.•Insert 10, 20 → node has 2 keys, no split.•Insert 5 → node full (3 keys), split:oMiddle key 10 moves up to root.OLeft child: 5, Right child: 20.•Insert 6 → goes to left child (5), inserted sorted (5, 6).•Insert 12 → goes to right child (20, 12) sorted (12, 20).•Insert 30 → right child overflows, split; middle key 20 moves up.•The root now has keys 10, 20 with three children
A Graph is a non-linear data structure consisting of a finite set of vertices (nodes) and a set of edges connecting these vertices. Graphs model relationships and connections, useful in social networks, maps, and computer networks….Types of Graphs:..•Directed Graph (Digraph): Edges have a direction from one vertex to another.
•Undirected Graph: Edges are bidirectional….•Weighted Graph: Edges carry weights or costs…•Unweighted Graph: Edges have no weights..
An Adjacency Matrix is a 2D array (or matrix) of size V x V, where V is the number of vertices in the graph.
Representation:
adj[i][j] = 1if there is an edge from vertexito vertexj(for unweighted graphs).adj[i][j] = weightif the graph is weighted.adj[i][j] = 0if there is no edge betweeniandjAn Adjacency List is an array (or list) of lists. Each index
irepresents a vertex, and the list aticontains all adjacent vertices (i.E., all vertices connected by outgoing edges fromi).Representation:
Each vertex has a list of pairs:
(neighbor, weight)for weighted graphs.For unweighted graphs, each entry is just the neighboring vertex.
Depth First Search (DFS) is a graph traversal algorithm that starts from a selected node and explores as far as possible along each branch before backtracking. It uses a stack data structure, either explicitly or via recursion.
Steps of DFS Algorithm:
1.Start at a chosen vertex, mark it as visited
2.Explore an unvisited adjacent vertex
3.Recursively apply DFS on that adjacent vertex
4.If no unvisited adjacent vertex exists, backtrack to the previous vertex
5.Continue until all reachable vertices are visited
Example:
Time Complexity:
•Using adjacency list: O(V + E) (V = number of vertices, E = number of edges) Each vertex and edge is explored once.
•Using adjacency matrix: O(V²) Due to scanning all vertices for edges.
Breadth First Search (BFS) is a graph traversal algorithm that starts from a chosen vertex and explores all its neighbors before moving to the next level neighbors. It uses a queue data structure to keep track of vertices to visit.
Steps of BFS Algorithm:1.Start from a selected vertex and mark it as visited.2.Enqueue this vertex.3.While the queue is not empty:
oDequeue a vertex from the queue.
oVisit all its adjacent unvisited vertices, mark them visited, and enqueue them.
4.Continue until all vertices reachable from the start vertex are visited
Example:
Consider the graph with vertices {A, B, C, D, E} and edges:
A — B, C
B — D
C — E
Start BFS from A:
•Visit A; enqueue A.•Dequeue A; enqueue neighbors B and C.•Dequeue B; enqueue neighbor D.
•Dequeue C; enqueue neighbor E.•Dequeue D; no new vertices.•Dequeue E; no new vertices.BFS order: A → B → C → D → E
Time Complexity:•Using adjacency list: O(V + E) Each vertex and edge is processed once.
•Using adjacency matrix: O(V²) Due to checking all vertices for adjacency.
Hashing is a technique used to map data of arbitrary size to fixed-size values called hash codes or hash values. These hash values are used as indices to store data in a hash table, enabling fast data retrieval.
The main goal of hashing is to convert a key into an index of an array where the corresponding value is stored, facilitating constant-time average complexity for search, insert, and delete operations.
Types of Hash Functions:
1.Division Method: Computes hash as h(k) = k mod m, where k is the key and m is the size of the hash table. Example: For key = 45 and table size m = 10, h(45) = 45 mod 10 = 5.
2.Multiplication Method: Uses a constant A (0 < A < 1), calculates h(k) = floor(m * (k * A mod 1)). This method distributes keys uniformly. Example: For key = 45, m = 10, A = 0.618, calculate fractional part of 45 * 0.618, multiply by m and floor it.
3.Mid-Square Method: Square the key and extract the middle digits as the hash value. Example: Key = 37, square = 1369, middle digits ‘36’ can be used as hash.
4.Folding Method: Break key into parts, add them, and use the sum as hash. Example: Key = 123456, split as 123 and 456, sum = 579.
A collision in hashing occurs when two different keys produce the same hash value, causing both to map to the same index in the hash table. Since hash tables rely on unique indices for efficient data retrieval, collisions must be resolved to maintain performance.
Collision Resolution Techniques:
1.Chaining: Each hash table index points to a linked list (chain) of entries. When a collision occurs, the new element is added to the linked list at that index. Example: If keys 12 and 22 hash to index 2, both are stored in a linked list at index 2.
2.Open Addressing: Instead of linked lists, open addressing searches for another empty slot using a probe sequence
Linear Probing: If collision occurs at index i, check (i+1) mod m, (i+2) mod m, etc., until an empty slot is found. Example: Keys 12 and 22 collide at index 2; 12 stored at 2, 22 checked at 3 and stored there if free.
Quadratic Probing: Uses a quadratic function to find the next slot: (i + c1 * j + c2 * j^2) mod m, where j is the probe number.
Double Hashing: Uses a second hash function to calculate the step size for probing.
Part A: Infix to Postfix Conversion
Infix expression: Operators are placed between operands (e.G., A + B)..Postfix expression: Operators follow operands (e.G., AB+)..Algorithm to convert Infix to Postfix:
1. Create an empty stack for operators.2. Scan the infix expression from left to right.3. If the token is an operand:
Add it to the postfix expression.4. If the token is ‘(’:….Push it to the stack….5. If the token is ‘)’:…Pop and append operators until ‘(’ is found. Discard ‘(’.
6. If the token is an operator (op1):…While the stack is not empty and precedence of top of stack ≥ op1:…Pop and append to postfix.
Push op1 onto the stack…7. After the expression is scanned:..Pop all remaining operators and append them to postfix.
Example: Infix: A + B * C Postfix: A B C * +
Part B: Postfix Expression Evaluation
Algorithm to evaluate Postfix Expression:
1. Create an empty stack.2. Scan the postfix expression from left to right.3. If token is operand:….Push it onto the stack.4. If token is operator:…Pop two operands from stack.
Apply the operator and push the result back to stack.5. After scanning, the result will be on the top of the stack.
Example: Postfix: 5 3 2 * + Step 1: Push 5 → [5] Step 2: Push 3 → [5, 3] Step 3: Push 2 → [5, 3, 2] Step 4: * → Pop 3 & 2 → Push 6 → [5, 6] Step 5: + → Pop 5 & 6 → Push 11 → [11] Result: 11
1.What is the time complexity of an infix to postfix conversion algorithm?➤ O(n)
2.Which of the following is essential for converting an infix expression to postfix notation?➤ Stack
3.A data structure is a particular way of ———- and ——— data either in computer’s memory or on the disk storage so that it can be used efficiently.➤ Organizing and storing
4.———— is not a stable sorting algorithm?➤ Selection sort
5.Time complexity of bubble sort in best case is————-➤ O(n) (when the array is already sorted)
6.When a sorting technique is called stable?➤ If it preserves the relative order of records with equal keys
7.What is the search complexity in direct addressing?➤ O(1)
8.What is the best case for linear search?➤ Element is found at the first position (O(1))
9.Reverse Polish notation is often known as——- ➤ Postfix notation
10.The values in a BST can be sorted in ascending order by using which of the traversal methods?➤ Inorder traversal
11.Which notation comprises a set of all functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n₀? ➤ Ω (Omega) notation
12.A circular queue is implemented using an array of size 10. The array index starts with 0, front is 6, and rear is 9. The insertion of next element takes place at the array index. ➤ 0
13.Which type of linked list contains a pointer to the next as well as the previous node in the sequence?➤ Doubly linked list
14.The time complexity of heap sort in worst case is———–➤ O(n log n)
15.The running time complexity of a linear time algorithm is——-➤ O(n)
16.A linear list in which elements can be added or removed at either end but not in the middle is known as———– ➤ Deque (Double-ended Queue)
17.If the elements of a data structure are stored sequentially, then it is a ______.➤ Linear data structure
18.Merge sort uses————Technique ➤ Divide and Conquer
19.Where is linear searching used? ➤ In unsorted arrays or lists
20.Stack can be implemented using _________ and ________ ? ➤ Array and Linked list
21.In C language, malloc( ) returns ➤ A pointer to the allocated memory
22.What is the number of edges present in a complete graph having n vertices?➤ n(n – 1)/2
23.________ notation provides a tight lower bound for f(n).➤ Ω (Omega) notation
24.Which data structure is used to implement recursion?➤ Stack
25.What is the disadvantage of array data structure? ➤ a) The amount of memory to be allocated should be known beforehand.
26.Which of the following data structures allow insertion and deletion from both ends? ➤ b) Deque
27.Which of the following sorting algorithms provide the best time complexity in the worst-case scenario?
➤ a) Merge Sort
28.Worst case time complexity to access an element in a BST can be?
➤ b) O(n)
29.How are string represented in memory in C?
➤ a) An array of characters
30.Which of the following data structures can be used to implement queues?
➤ d) Both b and c (Arrays and Linked List)
31.Which of the following is a Divide and Conquer algorithm?
➤ d) Merge Sort
32.What is the best case time complexity of the binary search algorithm?
➤ a) O(1)
33.What is the time complexity to insert an element to the front of a LinkedList (head pointer given)?
➤ b) O(1)
34.In a B+ tree, both the internal nodes and the leaves have keys
➤ a) True