11,312 views
0 votes
0 votes

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head and tail pointer. 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

3 Answers

Best answer
1 votes
1 votes

Options 1,2,3  

could be implemented in O(1) time 

since head,tail pointers is given

1) can insert node and get the address of that node into head pointer and next of that node contains next node address

2)As tail pointer is present new node address is stored in tail and even in last but 1 node of linked list

3)Could be deleted easily but pointing head to the next node

All this could be done with O(1)

But option 4 is done within O(n)

since even we have tail pointer which points to last node we need to get last but 1 node and next of that node is changed to null to do this we need to move from head pointer as it is single linked list we can't move back from tail pointer 

so it take O(n) time

selected by
1 votes
1 votes
+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+
I think should be 1,2,3,4

Related questions

1 votes
1 votes
1 answer
1
2 votes
2 votes
1 answer
3
rahul sharma 5 asked Sep 28, 2017
7,761 views
if we implement queue using singly linked list then how juch time enqueue enqueue and dequeue will take ?