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

**1. Which of the following is not a disadvantage to the usage of the 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 a specified position

**Answer: d**Explanation: Array elements can be accessed in two steps. First, multiply the size of the data type with the specified position, second, add this value to the base address. Both of these operations can be done in constant time, hence accessing elements at a given index/position is faster.

**2. 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)

**Answer: d**Explanation: Depending on whether the array is full or not, the complexity in a dynamic array varies. If you try to insert into an array that is not full, then the element is simply stored at the end, this takes O(1) time. If you try to insert into an array that is full, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O(n) time.

3. 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(n^{2})

**Answer: b**Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n).

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

classNode {protectedNode next;protectedObject ele; Node(Object e,Node n) { ele = e; next = n; }publicvoidsetNext(Node n) { next = n; }publicvoidsetEle(Object e) { ele = e; }publicNode getNext() {returnnext; }publicObject getEle() {returnele; } }classSLL { Node head;intsize; SLL() { size = 0; } }

a)

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

b)

publicvoidremoveLast() {if(size == 0)returnnull; Node cur; Node temp; cur = head;while(cur !=null) { temp = cur; cur = cur.getNext(); } temp.setNext(null);returncur; }

c)

publicvoidremoveLast() {if(size == 0)returnnull; Node cur; Node temp; cur = head;while(cur !=null) { cur = cur.getNext(); temp = cur; } temp.setNext(null);returncur; }

d)

publicvoidremoveLast() {if(size == 0)returnnull; Node cur; Node temp; cur = head;while(cur.getNext() !=null) { cur = cur.getNext(); temp = cur; } temp.setNext(null);returncur; }

**Answer: a**Explanation: Since you have to traverse to the end of the list and delete the last node, you need two reference pointers. ‘cur’ to traverse all the way and find the last node, and ‘temp’ is a trailing pointer to ‘cur’. Once you reach the end of the list, setNext of ‘temp’ to null, ‘cur’ is not being pointed to by any node, and hence it is available for garbage collection.

**5. What is the functionality of the following code?**

publicvoidfunction(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

**Answer: c**Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext(node);

**6. 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(long)

**Answer: a**Explanation: You need a temp variable to keep track of the current node, hence the space complexity is O(1).

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

publicvoiddelete(intpos) {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(inti=1; i<pos; i++) { temp = temp.getNext(); } temp.setNext(temp.getNext().getNext()); } size--; }

b)

publicvoiddelete(intpos) {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(inti=1; i<pos; i++) { temp = temp.getNext(); } temp.setNext(temp.getNext()); } size--; }

c)

publicvoiddelete(intpos) {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(inti=1; i<pos; i++) { temp = temp.getNext().getNext(); } temp.setNext(temp.getNext().getNext()); } size--; }

d)

publicvoiddelete(intpos) {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(inti=0; i<pos; i++) { temp = temp.getNext(); } temp.setNext(temp.getNext().getNext()); } size--; }

**Answer: a**Explanation: Loop through the list to get into position one behind the actual position given. temp.setNext(temp.getNext().getNext()) will delete the specified node.

**8. 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

**Answer: d**Explanation: To implement a file system, separate chaining in hash-tables, and implement non-binary tree linked lists are used. Elements are accessed sequentially in the linked list. Random access of elements is not an application of a linked list.

**9. Which of the following piece of code has the functionality of counting the number of elements in the list?**a)

publicintlength(Node head) {intsize = 0; Node cur = head;while(cur!=null) { size++; cur = cur.getNext(); }returnsize; }

b)

publicintlength(Node head) {intsize = 0; Node cur = head;while(cur!=null) { cur = cur.getNext(); size++; }returnsize; }

c)

publicintlength(Node head) {intsize = 0; Node cur = head;while(cur!=null) { size++; cur = cur.getNext(); } }

d)

publicintlength(Node head) {intsize = 0; Node cur = head;while(cur!=null) { size++; cur = cur.getNext().getNext(); }returnsize; }

**Answer: a**Explanation: ‘cur’ pointer traverses through list and increments the size variable until the end of list is reached

**10. How do you insert an element at the beginning of the list?**a)

publicvoidinsertBegin(Node node) { node.setNext(head); head = node; size++; }

b)

publicvoidinsertBegin(Node node) { head = node; node.setNext(head); size++; }

c)

publicvoidinsertBegin(Node node) { Node temp = head.getNext() node.setNext(temp); head = node; size++; }

d)

publicvoidinsertBegin(Node node) { Node temp = head.getNext() node.setNext(temp); node = head; size++; }

**Answer: a**Explanation: Set the ‘next’ pointer point to the head of the list and then make this new node the head.

**11. What is the functionality of the following piece of code?**

publicintfunction(intdata) { Node temp = head;intvar = 0;while(temp !=null) {if(temp.getData() == data) {returnvar; } var = var+1; temp = temp.getNext(); }returnInteger.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

** Answer: c**Explanation: When the temp is equal to the data, the position of data is returned.