Data Structure Questions and Answers – Doubly Linked List

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

1. Which of the following piece of code removes the node from a given position?
A)

public void remove(int pos)
{
	if(pos<0 || pos>=size)
	{
		System.out.println("Invalid position");
		return;
	}
	else
	{
		if(head == null)
			return;
		if(pos == 0)
		{
			head = head.getNext();
			if(head == null)
			tail = null;
		}
	        else
	        {
			Node temp = head;
			for(int i=1; i<position; i++)
			temp = temp.getNext();
		}
		temp.getNext().setPrev(temp.getPrev());
		temp.getPrev().setNext(temp.getNext());
	}
	size--;
}

B)

public void remove(int pos)
{
	if(pos<0 || pos>=size)
	{
		System.out.println("Invalid position");
		return;
	}
	else
	{
		if(head == null)
		return;
		if(pos == 0)
		{
			head = head.getNext();
			if(head == null)
			tail = null;
		}
		else
		{
			Node temp = head;
			for(int i=1; i<position; i++)
			temp = temp.getNext();
		}
		temp.getNext().setPrev(temp.getNext());
		temp.getPrev().setNext(temp.getPrev());
	}
	size--;
}

C)

public void remove(int pos)
{
	if(pos<0 || pos>=size)
	{
		System.out.println("Invalid position");
		return;
	}
	else
	{
		if(head == null)
			return;
		if(pos == 0)
		{
			head = head.getNext();
			if(head == null)
			tail = null;
		}
		else
		{
			Node temp = head;
			for(int i=1; i<position; i++)
			temp = temp.getNext().getNext();
		}
		temp.getNext().setPrev(temp.getPrev());
		temp.getPrev().setNext(temp.getNext());
	}
	size--;
}

D)

public void remove(int pos)
{
	if(pos<0 || pos>=size)
	{
		System.out.println("Invalid position");
		return;
	}
	else
	{
		if(head == null)
			return;
		if(pos == 0)
		{
			head = head.getNext();
			if(head == null)
			tail = null;
		}
		else
		{
			Node temp = head;
			for(int i=1; i<position; i++)
			temp = temp.getNext().getNext();
		}
		temp.getNext().setPrev(temp.getNext());
		temp.getPrev().setNext(temp.getPrev());
	}
	size--;
}


Explanation: Advance to the specified location and control the previous and next pointers of the next and previous nodes, respectively, if the position to be removed is not the head.

2. How do you calculate the pointer difference in a memory efficient double linked list?
A) head xor tail
B) pointer to previous node xor pointer to next node
C) pointer to previous node – pointer to next node
D) pointer to next node – pointer to previous node

Explanation: Taking the XOR of the pointer to the previous node and the pointer to the next node yields the pointer discrepancy.

3. What is the worst case time complexity of inserting a node in a doubly linked list?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(1)

Explanation: In the worst-case scenario, the location to be inserted could be at the end of the list, forcing you to traverse the entire list to reach the correct position, resulting in O. (n).

4. How do you insert a node at the beginning of the list?
A)

public class insertFront(int data)
{
	Node node = new Node(data, head, head.getNext());
	node.getNext().setPrev(node);
	head.setNext(node);
	size++;
}

B)

public class insertFront(int data)
{
	Node node = new Node(data, head, head);
	node.getNext().setPrev(node);
	head.setNext(node);
	size++;
}

C)

public class insertFront(int data)
{
	Node node = new Node(data, head, head.getNext());
	node.getNext().setPrev(head);
	head.setNext(node);
	size++;
}

D)

public class insertFront(int data)
{
	Node node = new Node(data, head, head.getNext());
	node.getNext().setPrev(node);
	head.setNext(node.getNext());
	size++;
}


Explanation: The previous pointer of the new node will point to head, while the next pointer will point to the actual next of head.

5. Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?

	Node temp = new Node(6,head,head.getNext());
	Node temp1 = new Node(0,tail.getPrev(),tail);
	head.setNext(temp);
	temp.getNext().setPrev(temp);
	tail.setPrev(temp1);
	temp1.getPrev().setNext(temp1);

A) head-0-1-2-3-4-5-6-tail
B) head-1-2-3-4-5-6-tail
C) head-6-1-2-3-4-5-0-tail
D) head-0-1-2-3-4-5-tail

Explanation: The operations in the specified sequence add nodes at the top and bottom of the list.

6. What is the functionality of the following piece of code?

public int function()
{
	Node temp = tail.getPrev();
	tail.setPrev(temp.getPrev());
	temp.getPrev().setNext(tail);
	size--;
	return temp.getItem();
}

A) Return the element at the tail of the list but do not remove it
B) Return the element at the tail of the list and remove it from the list
C) Return the last but one element from the list but do not remove it
D) Return the last but one element at the tail of the list and remove it from the list

Explanation: The tail’s previous and next pointers, as well as the last but one element, are manipulated, implying that the list’s last node is being removed.

7. Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?

	Node temp = new Node(6,head,head.getNext());
	head.setNext(temp);
	temp.getNext().setPrev(temp);
	Node temp1 = tail.getPrev();
	tail.setPrev(temp1.getPrev());
	temp1.getPrev().setNext(tail);

A) head-6-1-2-3-4-5-tail
B) head-6-1-2-3-4-tail
C) head-1-2-3-4-5-6-tail
D) head-1-2-3-4-5-tail

Explanation: A new node is added to the top of the list, and an old node is removed from the bottom.

8. Which of the following is false about a doubly linked list?
A) We can navigate in both the directions
B) It requires more space than a singly linked list
C) The insertion and deletion of a node take a bit longer
D) Implementing a doubly linked list is easier than singly linked list

Explanation: A doubly linked list has two pointers, left and right, that allow it to move in any direction. In contrast to a single linked list, which only has a ‘next’ pointer, a doubly linked list takes more space to store this additional pointer. Since any addition and deletion necessitates the manipulation of two pointers, it takes a little longer. Setting both the left and right pointers to the correct nodes in a doubly linked list takes longer than in a singly linked list.

9. Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.

public class Node
{
	protected int data;
	protected Node prev;
	protected Node next;
	public Node(int data)
	{
		this.data = data;
		prev = null;
		next = null;
	}
	public Node(int data, Node prev, Node next)
	{
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
	public int getData()
	{
		return data;
	}
	public void setData(int data)
	{
		this.data = data;
	}
	public Node getPrev()
	{
		return prev;
	}
	public void setPrev(Node prev)
	{
		this.prev = prev;
	}
	public Node getNext
	{
		return next;
	}
	public void setNext(Node next)
	{
		this.next = next;
	}
}
public class DLL
{
	protected Node head;
	protected Node tail;
	int length;
	public DLL()
	{
		head = new Node(Integer.MIN_VALUE,null,null);
		tail = new Node(Integer.MIN_VALUE,null,null);
		head.setNext(tail);
		length = 0;
	}
}

A)

public void insertRear(int data)
{
	Node node = new Node(data,tail.getPrev(),tail);
	node.getPrev().setNext(node);
	tail.setPrev(node);
	length++;
}

B)

public void insertRear(int data)
{
	Node node = new Node(data,tail.getPrev(),tail);
	node.getPrev().getPrev().setNext(node);
	tail.setPrev(node);
	length++;
}

C)advertisementhttps://64e63f71fdccdb87e8a3d726a07bedc0.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

public void insertRear(int data)
{
	Node node = new Node(data,tail.getPrev(),tail);
	node.getPrev().setNext(tail);
	tail.setPrev(node);
	length++;
}

D)

public void insertRear(int data)
{
	Node node = new Node(data,head,tail);
	node.getPrev().setNext(node);
	tail.setPrev(node);
	length++;
}


Explanation: Build a new node with a ‘prev’ that points to the node referred to by tail’s ‘prev’. The new node’s ‘next’ should point to tail. Set tail’s ‘prev’ to current node, and new node’s ‘prev’ to the new node.

10. What is a memory efficient double linked list?
A) Each node has only one pointer to traverse the list back and forth
B) The list has breakpoints for faster traversal
C) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
D) A doubly linked list that uses bitwise AND operator for storing addresses

Explanation: Just one pointer is used to traverse a memory-efficient doubly linked list back and forth. The implementation is based on the difference between two pointers. The front and rear pointer addresses are stored using the bitwise XOR operator. Rather than storing the actual memory address, each node stores the XOR address of the preceding and following nodes.

A doubly linked list is a linked data structure in computer science that consists of a series of sequentially linked records called nodes. There are three fields in each node: two relation fields (references to the previous and next node in the series of nodes) and one data field. The previous and next links on the beginning and ending nodes, respectively, point to a terminator, usually a sentinel node or null, to make traversing the list easier. The list is circularly connected through the sentinel node if there is only one sentinel node. It can be thought of as two singly connected lists made up of the same data objects, but in reverse chronological order.

Leave a Reply

Your email address will not be published.