91. 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. None of the mentioned
Answer: (a).Each node has only one pointer to traverse the list back and forth

92. 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) None of the mentioned
a. a
b. b
c. c
d. d
Answer: (a).a

93. 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
Answer: (b).pointer to previous node xor pointer to next node

94. What is the time complexity of inserting a node in a doubly linked list?
a. O(nlogn)
b. O(logn)
c. O(n)
d. O(1)
Answer: (c).O(n)

95. 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++;
}
a. a
b. b
c. c
d. d
Answer: (a).a

96. 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
Answer: (c).head-6-1-2-3-4-5-0-tail

97. 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
Answer: (b).Return the element at the tail of the list and remove it from the list

98. 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
Answer: (b).head-6-1-2-3-4-tail

99. Consider the 2-level skip list. How to access 38?
a. travel 20-30-35-38
b. travel 20-30-40-38
c. travel 20-38
d. travel 20-40-38
Answer: (a).travel 20-30-35-38

100. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only.
Given the representation, which of the following operation can be implemented in O(1) time?

i) Insertion at the front of the linked list

ii) Insertion at the end of the linked list

iii) Deletion of the front node of the linked list

iv) Deletion of the last node of the linked list
a. I and II
b. I and III
c. I, II and III
d. I, II and IV
Answer: (b).I and III