Which of the following descriptions are TRUE about Linked List? (((F)(G) the Big

Question

Which of the following descriptions are TRUE about Linked List? (((F)(G) the Big-0 complexity to insert a node into a singly linked list is always 0(1). The Big-0 complexity to delete a node from a doubly linked list is always 0(1). If there are both head and tail pointers in doubly linked list, then the insertion and deletion operation is always 0(1) at the beginning and end of the list. If a stack is implemented using a singly linked list, then it is more efficient to use the head pointer as the top of the stack. If a queue is implemented using a singly linked list (with tail pointer), then it is more efficient to use the tail pointer as the front of the queue and the head pointer as the rear of the queue than vice versa. Given only a pointer pointing to one of the nodes to be deleted, it is more efficient to delete that node in a doubly linked list than in a singly linked list. Merging two sorted linked lists, each with N nodes, is 0(N).

Explanation / Answer

A) The Big O complexity to insert a Node is Not O(1) , because you have the head pointer ..We will be traversing to the End Most Node and Then Insert there so Its definitely not O(1), It will be O(N) ..So False

B) To delete a node, we will be traversing to that node first to find out where it is, So Its definitely not O(1) , In worst case we might say we want to delete the last node, so we have to traverse way down to delete it..So worst case is O(N)..So False

C)Yes, True..If Head and Tail pointers are given then Its easy to insert at the end because we know where it ends so we can add..and delete at beginning and end..Note Only beginning and end but not in between.


D) True, If stack is implemented..Then Keep on adding Node at its head..Make the list grow in leftwards direction, then head will contain the last node added..So It will simulate the stack..So True


E) Queue as we know last In and First Out..I queue we add the nodes at rear end and remove from the front..So If head is front then we can remove it easily and if tail is rear we can add it easily..Given statement is opposite to what is correct..So Its False

F) Given a single pointer, Its easy in Doubly linked list because we know the previous node to it ..so we can link directly to the next next node , where as In Singly Linked list we have to traverse to know which is the prev node...True


G) Merging two Sorted Linked List each with N nodes will take O(N) time..We can use Merge Procedure of Merge Sort so its definitely O(N)..So Its True

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.