415 views
0 votes
0 votes

2 Answers

Best answer
2 votes
2 votes
Single linked list is more efficient in terms of storage as every node will store only one pointer, as opposed to doubly linked list which has to store two pointers(prev and next).

Insert Operations for both lists is Ο(1) for inserting at head .i.e first node and O(n) else where

Search: Single linked list takes O(n) as there is only one pointer and it cannot traverse in reverse direction. Doubly linked list takes O(n), however reverse traversal is possible here.

Delete : O(n) worst case time for Single LL

O(1) for double LL if pointer to the node to be deleted is given. Here Double LL is faster
selected by
0 votes
0 votes

Insert

  1. Single LL : O(n) if at arbitary position, O(1) if at head, O(1) if "that node is given after which we have to insert the new node".
  2. Doubly LL : O(n) is at arbitary position, O(1) if at end, O(1) if at head, O(1) if "that node is given after which we have to insert the new node".

Delete

  1. Single LL : O(n) if at arbitary position, O(1) if at head, O(1) if "that node is given after which we have to delete the new node".
  2. Doubly LL : O(n) if at arbitary position, O(1) if at end, O(1) if at head, O(1) if "that node is given after which we have to delete the new node".

Search

  1. Singly LL : O(n)
  2. Doubly LL :O(n)

Related questions

2 votes
2 votes
1 answer
1
Chhotu asked Nov 20, 2017
398 views
Hi Guys,What is the time complexity of Insert, Search and Delete operation in Multiway Trees (mainly B-tree and B+ Tree) ?
0 votes
0 votes
1 answer
4