Self-Doubt

Question

What is the time-complexity of Enqueue and Dequeue operations when Queue is implemented using linked list?

What is the time complexity of inserting a element in single linked list ?

Comments

What is the time complexity of inserting an element in a single linked list  : Following cases

1. At start: O(1) 
2. At middle: O(n) 
3. At end: O(n) 
4. After or before any element of a linked list: O(n) 

 

---

After or before any element of a linked list: O(n)

say for after 3rd element? It will be $O(1)$ , right? 

---

Asking for a specific element is O(1) since I give when n is unknown.
Yes you are correct.

Answer 1

In linked list if we want to insert  an element in the beginning then time complexity  is O(1)

in linked list if we want to insert an element at the last or in between then time complexity is O(n)

if we want to implement queue using linked list ,in queue we have two pointers front and rear ,insertion is done using rear pointer and deletion is done using rear pointer ,if head of linked list is rear pointer(for insertion) means enqueue operation so time complexity will be O(1) and tail pointer as front pointer (for deletion) means dequeue so time complexity will be O(n)

Comments

So basically it all depends on the situation given.

---

yes

---

@Anil ji 

 Enqueue and Dequeue operations when Queue is implemented using linked list will take O(1).

because there are two pointer front and rear ,by which you can enque through rear pointer and deque through front pointer . 

---

https://gateoverflow.in/204077/gate2018-3

 

---

@Anil ji that question is different ,,,that was modified queue implementation ,,,but in general  queue enque is done from tail and deque is done from head right.

---

ok..so think in that case if enqueue is done from tail so time complexity will be O(n) for insertion(enqueue) and dequeue is done from head so time complexity will be O(1) for deletion(dequeue)

---

Why O(n)?? ,,there is already tail  pointer .you have to just adjust pointer only which will take only O(1).

---

what about in worst case?

can u provide me some reference where it is given?

---

got it..

---

If there is only one pointer then it will take O(n) in enque but pointers are provided then it will take only O(1).