How do you search for a target key in a linked list?

Web Development
,
#1

To find the target key in a linked list, you have to apply sequential search. Each node is traversed and compared with the target key, and if it is different, then it follows the link to the next node. This traversal continues until either the target key is found or if the last node is reached.

#2

If the set is presented by linked list, and you have access only to its head, you cannot access k-th element faster than in Θ(k) time. During it you have access to all proceeding elements … so there are very few possibilities what to do on linked lists.

If you have more direct access to “list” internal nodes, you could start optimisations.