링크 리스트 형식이면서 이진 검색을 적용하려면 어떻게 해야하는지요?

데이터를 넘겨 받고, 그 데이터 중에서도 필요한 데이터를 추스르고 검색을 합니다.
데이터를 추스를때마다 malloc으로 메모리를 할당해서 링크리스트 형식으로 만들었는데요.
넘겨 받은 데이터가 너무 많아지고 그와 함께 추스른 데이터도 너무 많아지면, 처음부터 끝까지 훑어보는 검색이 너무 시간이 걸리더군요.
이진검색을 적용하자니 인덱스가 없는 링크리스트 형식으로 추스른 것 자체가 잘못 된 것같습니다.
임시로, 넘겨 받은 데이터를 한번 훑고, 추스를 데이터 갯수 세고, 필요한 갯수만큼 메모리를 할당해서 ( 구조체 배열형식이 되겠네요. )...
다시 넘겨 받은 데이터를 읽으면서 생성된 메모리 배열에 값을 삽입했습니다.
이렇게 해서 이진 검색을 적용시켰는데요. 넘겨받은 데이터를 꼭 두번 읽어야하더군요.
돌아가는데 문제는 없지만, 넘겨 받은 데이터 읽는 것을 한번에 끝낼 수 있는 방법이 없을까합니다.