Data Structure Questions and Answers – Singly Linked List

Uncategorized Computer Science & Engineering Data Structures & Algorithms

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

1. Which of the following performs deletion of the last element in the list? Given below is the Node class.

class Node
{
	protected Node next;
	protected Object ele;
	Node(Object e,Node n)
	{
		ele = e;
		next = n;
	}
	public void setNext(Node n)
	{
		next = n;
	}
	public void setEle(Object e)
	{
		ele = e;
	}
	public Node getNext()
	{
		return next;
	}
	public Object getEle()
	{
		return ele;
	}
}
class SLL 
{
	Node head;
	int size;
	SLL()
	{
		size = 0;
	}
}

A)

public Node removeLast()
{
	if(size == 0)
	return null;
	Node cur;
	Node temp;
	cur = head;
	while(cur.getNext() != null)
	{
		 temp = cur;
		 cur = cur.getNext();
        }
	temp.setNext(null);
	size--;
	return cur;
}

B)advertisement

public void removeLast()
{
	if(size == 0)
	return null;
	Node cur;
	Node temp;
	cur = head;
	while(cur != null)
	{
		temp = cur;
		cur = cur.getNext();
        }
	temp.setNext(null);
	return cur;
}

C)

public void removeLast()
{
	if(size == 0)
	    return null;
	Node cur;
	Node temp;
	cur = head;
	while(cur != null)
	{
		cur = cur.getNext();
		temp = cur;
	 }
	temp.setNext(null);
	return cur;
}

D)

public void removeLast()
{
	if(size == 0)
		return null;
	Node cur;
	Node temp;
	cur = head;
	while(cur.getNext() != null)
	{
		cur = cur.getNext();
		temp = cur;
	}
	temp.setNext(null);
	return cur;
}


Explanation: Two reference pointers are needed because you must traverse to the end of the list and delete the last node. ‘cur’ is a trailing pointer to ‘temp’, and it traverses all the way to the last node. SetNext of ‘temp’ to null as you hit the end of the list; ‘cur’ is not pointed to by any node and is therefore usable for garbage collection.

2. What is the functionality of the following code?

public void function(Node node)
{
	if(size == 0)
		head = node;
	else
	{
		Node temp,cur;
		for(cur = head; (temp = cur.getNext())!=null; cur = temp);
		cur.setNext(node);
	}
	size++;
}

A) Inserting a node at the beginning of the list
B) Deleting a node at the beginning of the list
C) Inserting a node at the end of the list
D) Deleting a node at the end of the list

Explanation: The for loop iterates over the list, inserting a new node with cur.setNext(node);

3. What is the space complexity for deleting a linked list?
a) O(1)
b) O(n)
c) Either O(1) or O(n)
d) O(logn)

Explanation: To keep track of the current node, you’ll need a temp variable, so the space complexity is O. (1).

4. How would you delete a node in the singly linked list? The position to be deleted is given.
A)

public void delete(int pos)
{
	if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
            {
		temp = temp.getNext();
            }
	    temp.setNext(temp.getNext().getNext());
	}
	    size--;
}

B)

public void delete(int pos)
{
	if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
	    {
		temp = temp.getNext();
	    }
	    temp.setNext(temp.getNext());
	}
	    size--;
}

C)

public void delete(int pos)
{
        if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
	    {
		temp = temp.getNext().getNext();
            }
	    temp.setNext(temp.getNext().getNext());
	}
	    size--;
}

D)

public void delete(int pos)
{
        if(pos < 0)
        pos = 0;
        if(pos > size)
        pos = size;
        if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=0; i<pos; i++)
	    {
		temp = temp.getNext();
	    }
	    temp.setNext(temp.getNext().getNext());
	}
	size--;
}


Explanation: To get into position one behind the actual position given, loop through the list. (temp.setNext(temp.getNext (). The defined node will be deleted if getNext() is called.

5. Which of these is not an application of a linked list?
A) To implement file systems
B) For separate chaining in hash-tables
C) To implement non-binary trees
D) Random Access of elements

Explanation: Related lists are used to implement file systems, separate chaining in hash tables, and non-binary trees. In a linked list, elements are accessed in order. Random access to elements is not a linked list programme.

6. Which of the following piece of code has the functionality of counting the number of elements in the list?
A)

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

B)

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

C)

public int length(Node head)
{
	int size = 0;
	Node cur = head;
	while(cur!=null)
	{
	    size++;
	    cur = cur.getNext();
	}
}

D)

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


Explanation: ‘The cur’ pointer travels through the array, incrementing the size variable until it reaches the end.

7. How do you insert an element at the beginning of the list?
A)

public void insertBegin(Node node)
{
	node.setNext(head);
	head = node;
	size++;
}

B)

public void insertBegin(Node node)
{
	head = node;
	node.setNext(head);
	size++;
}

C)

public void insertBegin(Node node)
{
	Node temp = head.getNext()
	node.setNext(temp);
	head = node;
	size++;
}

D)

public void insertBegin(Node node)
{
	Node temp = head.getNext()
	node.setNext(temp);
	node = head;
	size++;
}


Explanation: Make this new node the head of the list by setting the ‘next’ pointer to the top of the list.

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

public int function(int data)
{
	Node temp = head;
	int var = 0;
	while(temp != null)
	{
		if(temp.getData() == data)
		{
			return var;
		}
		var = var+1;
		temp = temp.getNext();
	}
	return Integer.MIN_VALUE;
}

A) Find and delete a given element in the list
B) Find and return the given element in the list
C) Find and return the position of the given element in the list
D) Find and insert a new element in the list

Explanation: When temp equals data, the data location is returned.

9. Which of the following is not a disadvantage to the usage of array?
A) Fixed size
B) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
C) Insertion based on position
D) Accessing elements at specified positions

Explanation: The elements of an array can be accessed in two ways. Multiply the data type’s size by the given location, then apply the result to the base address. Since all of these operations take the same amount of time, accessing elements at a specific index/position is quicker.

10. What is the time complexity of inserting at the end in dynamic arrays?
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1) or O(n)

Explanation: The complexity of a dynamic array varies depending on whether the array is complete or not. If you try to insert an element into an empty array, it is simply stored at the end, which takes O(1) time. If you want to insert into an array that is already complete, you must first allocate an array that is twice the size of the current array, copy all of the elements into it, and then insert the new element, which takes O(n) time.

11. What is the time complexity to count the number of elements in the linked list?
a) O(1)
b) O(n)
c) O(logn)
d) O(n2)

Explanation: Since you must traverse the entire list to count the number of elements, the difficulty is O(n).

A linked list is a linear set of data elements whose order is not determined by their physical location in memory in computer science. Instead, each aspect serves as a stepping stone to the next. It’s a data structure made up of a number of nodes that together form a sequence. Each node contains data and a connection (or link) to the next node in the series in its most basic form. During iteration, this structure allows for efficient addition and removal of elements from any place in the sequence. Additional connections are added in more complex versions, allowing for more effective insertion and removal of nodes at arbitrary locations.

Leave a Reply

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