Circular Linked List

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Circular Linked List”.

1. Which of the following application makes use of a circular linked list?
A) Undo operation in a text editor
B) Recursive function calls
C) Allocating CPU to resources
D) Implement Hash Tables

Answer: C
Explanation: The circular linked list data structure is commonly used to assign CPU time to resources in a round robin fashion. The stack data structure is used in recursive function calls. Reverse Double-linked lists are used to operate in the text editor. Singly connected lists are used in hash tables.

2. What differentiates a circular linked list from a normal linked list?
A) You cannot have the ‘next’ pointer point to null in a circular linked list
B) It is faster to traverse the circular linked list
C) You may or may not have the ‘next’ pointer point to null in a circular linked list
D) Head node is known in circular linked list

Answer: C
Explanation: When the list is empty, the ‘next’ pointer points to null; otherwise, it points to the top of the list. A starting point may be any node in a circular connected list (head).

3. How do you count the number of elements in the circular linked list?
A)

public int length(Node head)
{
	int length = 0;
	if( head == null)
		return 0;
	Node temp = head.getNext();
	while(temp != head)
	{
		temp = temp.getNext();
		length++;
	}
	return length;
}

B)

public int length(Node head)
{
	int length = 0;
	if( head == null)
		return 0;
	Node temp = head.getNext();
	while(temp != null)
	{
		temp = temp.getNext();
		length++;
	}
	return length;
}

C)

public int length(Node head)
{
	int length = 0;
	if( head == null)
		return 0;
	Node temp = head.getNext();
	while(temp != head && temp != null)
	{
		temp = head.getNext();
		length++;
	}
	return length;
}

D)advertisement

public int length(Node head)
{
	int length = 0;
	if( head == null)
		return 0;
	Node temp = head.getNext();
	while(temp != head && temp == null)
	{
		temp = head.getNext();
		length++;
	}
	return length;
}

Answer: A
Explanation: If the head property is null, the list is empty. Otherwise, keep going down the list until you hit the top.

4. What is the time complexity of searching for an element in a circular linked list?
A) O(n)
B) O(nlogn)
C) O(1)
D) O(n2)

Answer: A
Explanation: In the worst-case situation, you'll have to go through the entire n-element list.


5. Choose the code snippet which inserts a node to the head of the list?
A)
public void insertHead(int data) { Node temp = new Node(data); Node cur = head; while(cur.getNext() != head) cur = cur.getNext() if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head); head = temp; cur.setNext(temp); } size++; }
B)
public void insertHead(int data) { Node temp = new Node(data); while(cur != head) cur = cur.getNext() if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head.getNext()); cur.setNext(temp); } size++; }
C)
public void insertHead(int data) { Node temp = new Node(data); if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head.getNext()); head = temp; } size++; }
D)
public void insertHead(int data) { Node temp = new Node(data); if(head == null) { head = temp; head.setNext(head.getNext()); } else { temp.setNext(head.getNext()); head = temp; } size++; }

Answer: A
Explanation: If the list is empty, set the new node's next pointer to the current head and make it the head; otherwise, traverse the list to the end and make its'next' pointer point to the new node, then set the new node's next pointer to the current head and make it the head.

6. What is the functionality of the following code? Choose the most appropriate answer.
public int function() { if(head == null) return Integer.MIN_VALUE; int var; Node temp = head; Node cur; while(temp.getNext() != head) { cur = temp; temp = temp.getNext(); } if(temp == head) { var = head.getItem(); head = null; return var; } var = temp.getItem(); cur.setNext(head); return var; }
A) Return data from the end of the list
B) Returns the data and deletes the node at the end of the list
C) Returns the data from the beginning of the list
D) Returns the data and deletes the node from the beginning of the list

Answer: B
Explanation: To find the end node, first traverse the list, then use a trailing pointer to find the penultimate node, set the trailing pointer's 'next' to the head, and return the data stored in the 'temp' node.

7. What is the functionality of the following code? Choose the most appropriate answer.
public int function() { if(head == null) return Integer.MIN_VALUE; int var; Node temp = head; while(temp.getNext() != head) temp = temp.getNext(); if(temp == head) { var = head.getItem(); head = null; return var; } temp.setNext(head.getNext()); var = head.getItem(); head = head.getNext(); return var; }
A) Return data from the end of the list
B) Returns the data and deletes the node at the end of the list
C) Returns the data from the beginning of the list
D) Returns the data and deletes the node from the beginning of the list

Answer: D
Explanation: To find the end node, first traverse the list to find it, then manipulate the ‘next' pointer to point to the current head's next node, return the data from head, and make this next node the head.

8. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
A) Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
B) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
C) Cannot determine, you have to pre-define if the list contains cycles
D) Circular linked list itself represents a cycle. So no new cycles cannot be generated

Answer: B
Explanation: Advance the pointers such that the quick pointer advances two nodes at a time and the slow pointer advances one node at a time, and then check to see if the fast pointer is pointing to the slow pointer or if the fast pointer's 'next' is pointing to the slow pointer at any given time. For smaller lists, this is sufficient.

9. Which of the following is false about a circular linked list?
A) Every node has a successor
B) Time complexity of inserting a new node at the head of the list is O(1)
C) Time complexity for deleting the last node is O(n)
D) We can traverse the whole circular linked list by starting from any point

Answer: B
Explanation:Since you must traverse the list to reach the tail node, the time complexity of adding a new node at the top of the list is O(n).


10. What is the functionality of the following piece of code? Select the most appropriate.
public void function(int data) { int flag = 0; if( head != null) { Node temp = head.getNext(); while((temp != head) && (!(temp.getItem() == data))) { temp = temp.getNext(); flag = 1; break; } } if(flag) System.out.println("success"); else System.out.println("fail"); }
A) Print success if a particular element is not found
B) Print fail if a particular element is not found
C) Print success if a particular element is equal to 1
D) Print fail if the list is empty

Answer: B
Explanation: In the worst-case situation, you'll have to go through the entire n-element list.

A circular linked list is a set of elements in which each element is linked to the next element in the sequence, and the last element is linked to the first. That is, a circular linked list is identical to a single linked list with the exception that the last node in the list points to the first node. The last node of a circular Singly linked list includes a pointer to the first node of the list. There is no beginning or end to the circular list of singlely liked products. In the next section of any of the nodes, there is no null value.

Leave a Reply

Your email address will not be published. Required fields are marked *