CODEWITHSUNDEEP
csearchlinked-list
Mitch
Mitch

Reputation: 3418

Efficiently search a linked list

I have a sorted linked list, one function takes the root pointer and an Id and searches through the list to delete the item, however this takes linear time.

Is there any way to efficiently search through the linked list without doing it linearly using the fact that its sorted? The assignment hints heavily that their is a better way but I can't think of a way to do it without being terribly inefficient or just using a linear search.

Upvotes: 0

Views: 3028

Answers (1)

dbush
dbush

Reputation: 223739

Each node in a linked list only contains a pointer to the next node (and optionally the previous node), so without any other constructs the only way to search the list is linearly.

However, since you sort the list, you could build a binary tree in the process. Then you can use that tree to search the list with a time complexity of O(log n) instead of O(n).

Upvotes: 2

Related Questions