Searching a Linked List
A linked list is searched by value because its elements are not accessed by subscript the way vector elements are.
Why You Cannot Jump Straight to an Entry
Suppose you have a collection of phone book entries and you want the fourth one. With a vector, this is easy: you ask for the element at a position, such as v[3], and the program goes straight to it. A linked list does not work that way. You cannot ask for its fourth entry directly by position, so the question changes from which entry sits at position 3 to which entry has the name you want.
This is why a linked list is searched by value. Instead of asking for an element by its place in the sequence, you look through the list for an element that has a particular value. A phone book is a good picture of the task: you already know the name you want, and you scan the entries one at a time until you find it.
Searching by Value and Visiting in Order
A search is possible because a list is a sequence. Its elements can be visited one after another, in order, from the beginning. The search does not need to know any position in advance. It starts at the first element, checks whether that element is the one wanted, and moves on to the next element if it is not. This visiting-in-order property is what makes the search work.
A range-for loop gives a clean way to perform this visit. Each time the loop runs, a name refers to the next element of the list, so the search logic can be written as a short function. The function asks one question of every entry: is this the name we want? The first entry that answers yes provides the number.
Tracing a Search Through the Phone Book
Before reading how the loop moves through the list, try to predict the result. Assume the phone book holds three entries in this order: Ann with number 5550101, Bo with number 5550182, and Cy with number 5550199. These entries are an invented example written for this article.
What do you think happens?
What does get_number("Bo") return for the phone book described above?
Reveal answer
5550182
The search starts at Ann, whose name is not Bo, so the loop moves on. Bo is the second entry, and its name matches, so the function returns Bo's number, 5550182, immediately.
Notice that Cy is never examined in this trace. The return inside the loop ends the function as soon as the match is found, so the search does not continue past Bo. This matters when a name appears only once, because the first match is the answer. It also means the function does no extra work after it has found what it needs.
A Name That Is Not in the List
Now trace a name that is not in the list, such as get_number("Dee"). Each of the three entries fails the test, because none of their names is Dee. The loop runs out of elements without ever reaching a return inside the loop, so execution falls through to the final return 0. The caller receives the not-found signal rather than a phone number.
The Search Function in Code
The function takes a name and returns the matching phone number. It works over an object called phone_book, whose elements have a name field and a number field. The code below follows that description. Its entries are an invented example written for this article.
int get_number(const std::string& s)
{
for (const auto& x : phone_book) {
if (x.name == s) {
return x.number;
}
}
return 0;
}- 1The function signature names the search and states that it takes a name and returns a number.
- 2The loop header for (const auto& x :
phone_book) says that x takes on each element ofphone_bookin turn. The const and & parts mean x refers to the element itself without copying it, and the loop does not change the list. - 3The if statement asks, for the current element, whether its name equals the name we are searching for. Equality is checked exactly, with ==.
- 4When the test is true, the return statement inside the loop sends back that element's number and ends the function.
- 5If the loop finishes without a match, execution reaches the final return 0, which is the not-found signal.
- The parameter s holds the name being searched for.
- The loop header visits each element of
phone_bookin turn. - The comparison
x.name== s checks equality exactly. - The return inside the loop sends back the matching number.
- The final return 0 runs only if no element matched.
Two Exits from the Search Loop
The search starts at the beginning of the list and proceeds until the wanted name is found or the end of phone_book is reached. That sentence describes two possible exits. The first exit happens when an element's name equals the search name, and the return inside the loop sends back that element's number. The second exit happens when the loop has examined every element without a match, and execution falls through to the final return 0.
Read the flowchart as the loop's life cycle. Each pass asks whether there are more elements, then asks whether the current name matches. A yes on the match question leaves through the return of the number. A no sends the search back around for the next element. When no elements remain, the search leaves through return 0 instead.
Edge Cases: Empty Lists and First Entries
If the list is empty, the loop body never runs, so the function immediately returns 0. If the wanted name is the very first entry, the search finishes after a single comparison. In both cases the function still returns a value, so the caller never has to deal with a loop that fails to finish.
Mistakes When Searching by Value
Common mistake Looking up an entry by position, as if the list were a vector
What it looks likeWriting phone_book[3] to get the fourth entry
Why it failsA linked list is not accessed by subscript the way vector elements are, so the fourth entry cannot be requested directly by position.
Do this insteadSearch by value: loop through the entries and compare each name with the one you want.
Common mistake Treating the returned 0 as a real phone number
What it looks likeUsing the result of get_number("Dee") to dial a number without checking it
Why it failsThe function returns 0 to signal that no entry matched, so 0 is not a phone number.
Do this insteadCheck for 0 after calling the function and handle the not-found case before using the value.
Common mistake Expecting the search to keep going after a match
What it looks likeAssuming Cy is examined after Bo has been found
Why it failsThe return inside the loop ends the function at the first match, so later elements are not visited.
Do this insteadExpect the first matching entry to be the answer, and do not rely on later entries being checked.
Common mistake Using a single equals sign where equality is meant, since the comparison is checked exactly with ==
Predicting Search Results for Different Names
Using the phone book with Ann at 5550101, Bo at 5550182, and Cy at 5550199, predict the return value of get_number("Cy"), get_number("Ann"), and get_number("Dee"). For each call, say which element the loop examines last and whether the function returns from inside the loop or after it.
Hints
- Ann is the first entry, so a search for Ann finishes after a single comparison.
- Cy is the last entry, so the loop must examine Ann and Bo before reaching it.
- Dee is not in the list, so every entry fails the test and the function returns 0.
Key Takeaways
- A linked list is searched by value because its elements are not accessed by subscript the way vector elements are.
- A range-for loop visits the elements of a list in order, starting at the beginning, so the search can check each entry until it finds the wanted name.
- The search has two exits: a return of the matching number when a name matches, and a return of 0 when the loop ends without a match.
- Because 0 signals not found, callers must check for it rather than treating it as a phone number.
- An empty list and a match at the first entry both still produce a returned value, so the loop always finishes.