Hello 0x00sec! Today, I’ll be going over search(...), as promised.
Basic Algorithm Description
search(...) will take one parameter q of type T, the value to look for in a linked list. The function returns a node<T>* (a pointer to a node in the list) if q is found; or nullptr if q is not found.
This implementation of search(...) will at most traverse the entire linked list. Thus, it has O(n) complexity.
The Code
template <class T>
node<T>* List<T>::search(const T& q) {
node<T>* h = root;
while(h != nullptr && h->d() != q)
h = h->next;
// d() is a member function of `node` is the
// getter for the attribute `data` of a `node`
return h;
}
The first thing we do is use h to store the pointer to the root of our linked list. We then traverse the list, stopping only when we have reached the end OR have found the value for which we are looking.
Whatever h is at that point, we return.
Example
#include <node.h>
#include <node.cpp>
#include <list.h>
#include <list.cpp>
#include <iostream>
int main() {
List<int> mylist;
for (int i =0; i<10; i++) mylist.append(i);
// append() tacks the value passed to it onto the end of the linked list
if (mylist.search(5) != nullptr)
std::cout << "found 5 in mylist\n";
else
std::cout << "didn't find 5 in mylist\n";
if (mylist.search(12) != nullptr)
std::cout << "found 12 in mylist\n";
else
std::cout "did not find 12 in mylist\n";
}
This code should read out:
found 5 in mylist
did not find 12 in mylist
Conclusion
In its current state, you could use this search(...) to interact with nodes. I’m now debating whether I should have returned an index instead. Ah, oh well. It still is a search function though. And it works.
Bai,
oaktree
P.S. If you have any suggestions, go ahead and comment or PM me! After all, I’m no node-it-all.
