Linked list: Insertion at beginning and end O(1) ... constant time Insertion at an arbitrary location (based on some condition): O(n) as you have to traverse through all n-x elements to get to element x in the list.
Same goes for deletion. Since linked lists are dynamic, other than changing one pointer, (and freeing up memory) not much needs to be done. Queues are linked lists with enqueue(Node* n) and Node* dequeue() functions implemented. Using these functions are O(1), constant time operations. I wouldn't imagine why one would need to insert/delete at random locations in a queue, as this would negate the point of a queue and make it a vanilla linked list. -Minotauraus. On Jun 8, 1:38 am, Raj N <[email protected]> wrote: > What is the time complexity of insertion and deletion in > 1. Linked list > 2. Queue > 3. Queue implemented using a linked list -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
