CODEWITHSUNDEEP
javaperformancelinked-listtime-complexity
Parikksit Bhisay
Parikksit Bhisay

Reputation: 163

How can we reduce search time in linked list?

I read this question on career cup but didn't find any good answer other than 'SkipList'. The description of SkipList that I found on wikipedia was interesting, however, I didn't understand some terms like 'geometric/binomial distrubution'... I read what it is and goes deep into probabilistic theory. I simply wanted to implement a way to make some searching quicker. So here's what I did: 1. Created indexes. - I wrote a function to create say 1000 nodes. Then, I created an array of type linked list and looped through the 1000 nodes and picked every 23rd element (random number that came in my mind) and added to the array which I call 'index'.

    SLL index = new SLL[50]

Now the function to to create the index:

    private static void createIndex(SLL[] index, SLL head){
    int count=0;
    SLL temp = head;
    while(temp!=null)
    {
        count++;
        temp = temp.next;
        if((count==23){
            index[i] = temp;
            i++;
            count=0;
        }
    }       
}

Now finally the 'find' function. In that function, I first take the input element say 769 for example. I go through the 'index' array and find index[i]>769. Thus, now I pass head = index[i-1] and tail = index[i] to the 'find' function. It will then search between a short range of 23 elements for 769. Thus, I calculated that it takes a total of 43 jumps (including the array jumps and the node=node.next jumps) to find the element I wanted which otherwise would have taken 769 jumps.

Please Note: I consider the code to create index array NOT a part of searching, thus I do not add its time complexitiy(which is terrible) with the 'find' function's time complexity. I assume that this creation of index should be done as a separate function after a list has been created, OR, do it timely. Just like it takes time for a webpage to show up on google searches. Also, this question was asked in a Microsoft interview and I wonder if the solution I provided would be any good or would I look like a fool for providing such kind of a solution. The solution has been written in Java. Waiting for your feedback.

Upvotes: 0

Views: 1239

Answers (1)

Stephen C
Stephen C

Reputation: 718768

It is difficult to make out what problem it is that you are trying to solve here, or how your solution is supposed to work. (Hint: complete working code would help with both!)

However there are a couple of general things we can say:

  • You can't search a list data structure (e.g. find i in the list) in better that O(N) unless some kind of ordering has been placed on it. For example, sorting the elements.

  • If the elements of the list are sorted and your list is indexable (i.e. getting the element at position i is O(1)), then you can use binary search and find an element in O(logN).

  • You can't get the element at position i of a linked list in better that O(N).

If you add secondary data (indexes, whatever), you can potentially get better performance for certain operations ... at the expense of more storage space, and making certain other operations more expensive. However, you no longer have a list / linked list. The entire data structure is "something else".

Upvotes: 1

Related Questions