How can I implement an interpolation search on a linked list?

[Williams2222]

I need to implement an interpolation search on a linked list, I have some code but I'm getting errors whenever I search anything that isn't the first element. Even if the element I'm searching for is in the list, if it isn't the first one it returns a -1.

int ListaS::interpolationSearch(int id){
    NodoS* low = head;
    NodoS* mid = low;
    NodoS* high = tail;


    int lowest = 0;
    int middle;
    int highest = getLength()-1;
    int counter = 0;


    while (low->getData()->getId() <= id && high->getData()->getId() >= id){
        middle = lowest + (id - low->getData()->getId()) * (highest - lowest) /
            (high->getData()->getId() - low->getData()->getId());
            getIndex(mid, middle);  

        if (mid->getData()->getId() < id)
            {
                low = mid;
            } 

        else if (mid->getData()->getId() > id)
            {
                high = mid;
            } 

        else
            {
                return 1;
            }

        if (low->getData()->getId() == id)
            {
                return 1;
            } 

        else
            {
                return -1;
            }
    }
}

[Banfa]

The answer is you probably can't with any efficiency. The thing is to perform an interpolation you have to have random access to your data, that is you need to be able to directly address an member of the data. In a linked list you don't have random access, you have to start with the head or tail pointer.

So for example I would guess your function getIndex returns a member at a given index by starting at the head pointer and moving down the list by the index you are looking for in a loop. I imagine that on average (may be even always) the number of items you iterate through the loop in getIndex is the same or greater than the number of iterations you would make on a straight loop searching for the id instead of trying to do an interpolation.

Interpolations work well on arrays which does have random access or any other contain that has random access.

You equation at line 14 is looks like it is trying to a weighted interpolation (rather than say a binary chop) of the current index (lowest and highest) by the sort parameter (id). However you never change either lowest or highest so it gets middle wrong every time after the first, lowest and highest should probably be altered at lines 20 and 25 respectively.

The if statement line 33 can never be true unless the id supplied was the first id in the list, it would be worth checking the head and tail list ids before ever entering the loop. The reason that it is never true is that in the if/else if/else above either low was altered to mid and the id of mid was < id and so not equal to id, or high was set to mid so presumably the right entery has not been found yet.

Since the if statement at line 3 is never true the function always exits at line 40. The else clause is just wrong, if line 33 is false your algorithm needs to keep looping.

In fact the way it is written the loop can not have more than 1 iteration if it doesn't end at line 30 it must end between line 33-41.

[Ancient Dragon]

One way to do it is to create an array of pointers, each pointer points to a node in the linked list. Then sort that array of pointers, swapping the data in the nodes of the linked list, not the pointers. If each node contains several data items then change the node to use a structure so that the structures can be swapped all in one shot instead of swapping each data item individually. The array can be destroyed after sorting is complete.

[Banfa]

Since this is a search not a sort to create an array of pointers to the linked list you will have to iterate over the list and if you are going to do that you may as well just do your search as you do that iteration rather than fill in an array with pointers :D

[Ancient Dragon]

Yes, I lost my mind there for awhile :) Use of an array would be more efficient only if the search were required more than one time. Once the array is built it could be searched as often as needed.