Si tu lista es lineal y encadenada simple y además está desordenada, definitivamente la búsqueda debe ser lineal y no hay de otra.
Puedes implementar algunos trucos en base al tamaño de los nodos de tu lista pero no siempre resulta seguro por desconocer las direcciones de los nodos al momento de crear la variables.
