Question 16: Write an algorithm to merge two sorted linked lists.
Solution:
- Initialize a dummy node to start the merged list.
- Compare the data of the two lists, and add the smaller node to the merged list.
- Continue merging until one of the lists is empty.
- Append the remaining nodes from the non-empty list.
Question 17: What is the time complexity for inserting an element at the beginning of a singly linked list?
Solution: The time complexity for inserting an element at the beginning of a singly linked list is O(1), as you only need to update the pointer of the new node to the current head.
Question 18: Describe a real-world application where a LinkedList is preferable over an array.
Solution: LinkedLists are preferable in applications like music playlists, where songs can be dynamically added or removed, and continuous traversal through the list is required.
Question 19: Can we use a LinkedList to implement a priority queue? Explain how.
Solution: Yes, a priority queue can be implemented using a LinkedList by maintaining the list in sorted order based on priority. Insertion involves traversing the list and inserting the new element at the appropriate position.
Question 20: Write two advantages of a doubly linked list over a singly linked list.
Solution:
- Efficient traversal in both directions (forward and backward).
- Deletions can be done more efficiently as you have access to both the next and previous nodes.
Question 21: Explain the concept of a circular doubly linked list.
Solution: A circular doubly linked list is a variation of a doubly linked list where the last node’s next pointer points to the first node, and the first node’s previous pointer points to the last node. This allows traversal in both directions without needing a NULL reference.
Question 22: How do you delete the last node of a singly linked list?
Solution:
- Traverse the list to the second-to-last node.
- Set its next pointer to NULL.
- Free the memory of the last node.
Question 23: How does garbage collection work in the context of LinkedLists?
Solution: Garbage collection automatically frees up memory by removing nodes that are no longer referenced. When a node in a LinkedList is deleted, its memory is deallocated if no other references to that node exist.
Question 24: Describe how you would implement a circular queue using a LinkedList.
Solution: In a circular queue using a LinkedList, the rear node’s next pointer is set to the front node to maintain the circular nature of the queue. Insertions are done at the rear, and deletions occur at the front.
Question 25: Write an algorithm to find the middle node of a singly linked list in one traversal.
Solution:
- Initialize two pointers: a slow pointer and a fast pointer.
- Move the slow pointer one step and the fast pointer two steps at a time.
- When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
Question 26: How would you detect a loop in a LinkedList without using extra memory?
Solution: Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm) can detect a loop using two pointers (slow and fast) without extra memory. The fast pointer moves two steps, and the slow pointer moves one step. If they meet, a loop exists.
Question 27: Explain why LinkedLists are not ideal for random access of elements.
Solution: LinkedLists are not ideal for random access because, unlike arrays, there is no direct index-based access. To access an element, you must traverse the list from the head, which takes O(n) time.
Question 28: Write the advantages and disadvantages of a singly linked list.
Solution:
- Advantages: Efficient memory usage, dynamic resizing, and fast insertions/deletions at the beginning.
- Disadvantages: No backward traversal, slow random access (O(n)), and higher memory usage due to pointers.
Question 29: Describe a scenario where a circular linked list would be more efficient than a singly linked list.
Solution: A circular linked list is more efficient in scenarios like implementing a round-robin scheduler in operating systems, where processes are cycled through repeatedly, as it allows continuous looping without needing to restart from the head.
Question 30: How do you insert a node at a specific position in a singly linked list?
Solution:
- Traverse the list to the node just before the desired position.
- Create a new node and set its next pointer to the next node in the list.
- Set the next pointer of the previous node to the new node.