wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Remove and element from a linked list based Queue
        
(Message started by: Ved on Dec 23^rd, 2011, 8:00am)

Title: Remove and element from a linked list based Queue
Post by Ved on Dec 23^rd, 2011, 8:00am

I want to build a system with the following APIs :
1. put(n) - stores data in the system
2. get() - will give me the element added the first and so on.
I gave a queue implementation using the LinkedList (using a head and tail pointers). Interviewer asked the complexity of both put and get operations and asked how I would implement "removeElement(n)" - now, given a linkedlist/array implementation of a queue, removeElement(n) is going to be O(n) worst case operation, I could not find any other options.

Title: Re: Remove and element from a linked list based Qu
Post by towr on Dec 23^rd, 2011, 8:43am

You add a tree to index the elements, then all three are O(log n).

Title: Re: Remove and element from a linked list based Qu
Post by Ved on Dec 23^rd, 2011, 9:58pm

If I get a tree with indices, how can I have removeElement(n) as O(log n) ? I should have been more clear, removeElement(n) does not mean remove nth element, but remove element with value "n". So even in a tree, I will have to traverse all indexes to see if that index contains element with value "n".

Title: Re: Remove and element from a linked list based Qu
Post by birbal on Dec 24^th, 2011, 4:13am

on 12/23/11 at 21:58:39, Ved wrote:

You can you a BST or a B+ tree to index the elements of the linked list. So tree nodes should have pointers to list nodes. Whenever you want to search n, use tree n reach the list node with value n.