CODEWITHSUNDEEP
searchbinarylinked-list
user280105
user280105

Reputation: 33

can we perform binary search on linked lists?

there was a reputed site which claimed that we cannot do binary search on linked list but I know for a fact that we can perform merge sort( which uses divide and conquer just like binary search) on a linked list so we must be able to perform binary search on a linked list as well right??

Upvotes: 1

Views: 2105

Answers (1)

D.Shawley
D.Shawley

Reputation: 59583

Purely in the abstract, a linked list does not support direct indexing. The only way to get to the third element is by starting at the first element, following the next link to the second element, then following it's next link to the third element.

If the implementation allows for indexing (e.g., java.util.LinkedList), it is possible to implement a binary search by calling get(index) when you need an element. If the underlying data structure is a simple linked list without an auxiliary lookup structure, then this will perform very poorly. As an example, the following is the code from the OpenJDK java.util.LinkedList.get method.

package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    public E get(int index) {
        return node(index).item;
    }

    Node<E> node(int index) {
        if (index < (size >> 2)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
}

When list.get(5) is called to get the sixth element in a list of more than 11 elements, it iterates over the first five elements before returning the sixth. The generic interface provides indexed access into the sequence but makes no guarantees on its performance.

Upvotes: 1

Related Questions