DS UNIT-2 TEST-3

Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

• Deleting a node whose location is given

• Searching an unsorted list for a given item

• Inserting a node after the node with a given location

• 
  Traversing the list to process each node

Answer explanation

Doubly linked lists have a few advantages over linear linked lists when it comes to certain operations. Specifically, the following operation is performed more efficiently by a doubly linked list than by a linear linked list

Deleting a node given a pointer to the node.

In a linear linked list, deleting a node requires traversing the list to find the node to be deleted and its predecessor. Once these nodes have been found, the predecessor's next pointer is updated to skip over the node to be deleted. This operation takes O(n) time in the worst case, where n is the number of nodes in the list.

The minimum number of fields with each node of doubly linked list is

A) in a normal case

B) in an optimal way

• 1 ,2

• 2 ,3

• 3, 2

• 4, 4

Answer explanation

In general, each node of doubly link list always has 3 fields, i.e., the previous node pointer, the data field, and the next node pointer, see - doubly linked list introduction So, answer should be option (C) 3. However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient doubly linked list, see - XOR linked list – a memory efficient doubly linked list | set 1 Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.

A doubly linked list is declared as

struct Node {

int Value;

struct Node Fwd;

struct Node Bwd; );

Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which of the following segments of code deletes the node pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last node of the list?

• X->Bwd.Fwd = X->Fwd ; X.Fwd->Bwd = X->Bwd ;

• X.Bwd->Fwd = X.Bwd ; X->Fwd.Bwd = X.Bwd ;

• X->Bwd->Fwd = X->Bwd ; X->Fwd->Bwd = X->Fwd;

• X->Bwd->Fwd = X->Fwd; X->Fwd->Bwd = X->Bwd ;

Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

• 
  Add an element after the last element of the list

• Interchange the first two elements of the list

• Delete the first element of the list

• Delete the last element of the list

Answer explanation

Interchange the first two elements of the list: To interchange the first two elements of the list, we can simply update the head pointer of the list to point to the second element and update the next pointer of the second element to point to the first element. This can be done in constant time, regardless of the length of the list.

See the image and answer the question

• It is not possible to reverse a singly linked list in O(1) space.

• The best algorithm for the problem takes 

  theta(n logn)    

  theta time in the worst case

• The best algorithm for the problem takes 

  theta(n)    

  theta time in the worst case

• The best algorithm for the problem takes theta(n^2)    

  theta time in the worst case

Correct Program to find Middle of a Linked list ?

• class Node:
     def init(self, k):
         self.data = k
         self.next = None

  def printList(head):
     curr = head
     while curr != None:
         print(curr.data)
         curr = curr.next
     print()
     def printMiddle(ptr):
     if head == None:
         return
     count = 0 
     curr = head
     while curr :
         curr = curr.next
         count+=1
        curr = head
     for i in range (count//2):
         curr = curr.next
     print(curr.data)  

  head = Node(10)
  head.next = Node(10)
  head.next.next = Node(20)
  printList(head)
  printMiddle(head)

• class Node:
     def init(self, k):
         self.data = k
         self.next = None

  def printList(head):
     curr = head
     while curr != None:
         print(curr.data)
         curr = curr.next
     print()
  def printMiddle(ptr):
     if head == None:
         return
     count = 0 
     curr = head
     while curr :
         curr != curr.next
         count+=1
        curr = head
     for i in range (count//2):
         curr = curr.next
     print(curr.data)
     head = Node(10)
  head.next = Node(10)
  head.next.next = Node(20)
  printList(head)
  printMiddle(head)

Which of the following problems can be solved using 2 pointers on linked list?

• Detecting cycle in a linked list

• Finding intersection of two linked lists

• Finding middle element of a linked list

Which of the following is optimal to find an element at kth position at the linked list?

• Single Linked List

• Double Linked List

• Circular Linked List

• Array implementation of Linked List

The type of pointer used to point to the address of the next element in a linked list?

• pointer to character

• pointer to integer

• pointer to node

• all of the above

A linked list in which none of the nodes contains a NULL pointer is?

• Single Linked List

• Double Linked List

• Circular Single Linked List

• Circular Double Linked List