Linked Lists

Question 1

What is the primary advantage of using a linked list over an array?

Answer 1

Dynamic size

Question 2

Which type of linked list allows traversal in both directions?

Answer 2

Doubly-linked list

Question 3

Which of the following operations is typically more efficient in a linked list than an array?

a) Accessing an element by index
b) Inserting an element at the beginning
c) Deleting an element from the end
d) Finding the max element

Answer 3

b) Inserting an element at the beginning

Question 4

In a singly linked list, what does each node contain?

Answer 4

Data and a pointer to the next node

Question 5

What is the time complexity of inserting a node at the beginning of a singly linked list?

Answer 5

O(1)

Question 6

What is the time complexity of searching for an element in an unsorted singly linked list?

Answer 6

O(n)

Question 7

Which of the following is NOT a valid operation on a linked list?

a) Insert at the head
b) Insert at the tail
c) Access an element by index in O(1) time
d) Delete a node from the middle

Answer 7

c) Access an element by index in O(1) time

Question 8

Which of the following is true about a doubly linked list?

A) Each node has a pointer to the next node only
B) Each node has a pointer to the previous node only
C) Each node has pointers to both the next and previous nodes
D) Each node has no pointers

Answer 8

C) Each node has pointers to both the next and previous nodes

Question 9

Describe the process of inserting a new node at the beginning of a singly linked list and provide the code.

Answer 9

Process:
1) create a new node
2) Set the new node’s next pointer to the current head of the list
3) Update the head of the list to be the new node

Code:
struct Node{
int data;
Node* next;
};
void insertAtBeg(Node* head, int data){
Node* newNode = newNode();
newNode->data = data;
newNode->next = head;
head = newNode;
}

Question 10

Describe the process of inserting a new node at the end of a singly linked list and provide the code.

Answer 10

Process:
1. Create a new node
2. Check if list is empty, then new node will be the head
3. Find the last node
4. Insert new node after last node/at the end

Code:
struct Node{
int data;
Node* next;
};
void insertAtEnd(Node* head, int data){
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;

 if(head == nullptr){
      head = newNode;
      return;
 }
 
 Node* curr = head;
 while(curr->next != nullptr){
      curr = curr->next;
 }
 curr->next = newNode; }

Question 11

Describe the process of inserting a new node after a given node of a singly linked list and provide the code.

Answer 11

Process:
1. Check if previous is NULL
2. Create new Node
3. Insert new Node after previous

struct Node{
int data;
Node* next;
};
void insertAfter(Node* prev, int data){
if(prev == nullptr){
cout &laquo_space;“Error” «endl;
return;
}
Node newNode = new Node();
newNode->data = data;

 newNode->next = prev->next;
 prev->next = newNode; }

Question 12

Explain how you would reverse a singly linked list. Write a function to accomplish this.

Answer 12

• Initialize three pointers: prev as NULL, current as the head of the list, and next as NULL.
• Iterate through the list, updating the next pointer of each node to point to the previous node.
• Move the prev and current pointers one step forward until current becomes NULL.
• Finally, set the head of the list to prev.

Code:
struct Node{
int data;
Node* next;
};
reverseLinkedList(Node* head){
Node* prev = nullptr;
Node* current = head;
Node* nextTemp = nullptr; // temp pointer to store next node
while(current != nullptr){
nextTemp=current->next; //store the next node
current->next = prev; // reverse the current node’s pointer
prev = current; // move previous to current node
current = nextTemp; // move to next node
}
head = prev;
}

Question 13

Write a function to merge two sorted linked lists into a single sorted linked list. Provide the function and explain your approach.

Answer 13

• Initialize a dummy node to act as the head of the merged list.
• Use two pointers to traverse the two lists.
• Compare the current nodes of both lists and append the smaller node to the merged list.
• Move the pointer of the list from which the node was taken.
• Continue until one of the lists is exhausted, then append the remaining nodes of the other list.

Code:
mergeSortedLists(Node* l1, Node* l2) {
Node dummy;
Node* current = &dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->data < l2->data) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if (l1 != NULL) {
current->next = l1;
} else {
current->next = l2;
}
}

Question 14

Describe the process of deleting a node with a given value from a singly linked list. Write the code for this operation.

Answer 14

• Handle special case where the node to delete is the head.
• Traverse the list to find the node before the target node.
• Adjust pointers to bypass the target node and free memory.
• Time Complexity: O(n)

Code:
Node* deleteNode(Node* head, int key) {
if (head == nullptr) return head;

// If head needs to be deleted
if (head->data == key) {
    Node* temp = head;
    head = head->next;
    delete temp;
    return head;
}

Node* current = head;
while (current->next && current->next->data != key) {
    current = current->next;
}

if (current->next) {
    Node* temp = current->next;
    current->next = current->next->next;
    delete temp;
}

return head; }