# Data Structures (Part 1.2): Linked Lists [search()]

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";
}
``````

found 5 in mylist
did not find 12 in mylist

# Conclusion

In its current state, you could use this `search(...)` to interact with `node`s. 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.

4 Likes

Another well written post! For your next algorithm, how about you solve P = NP?

I would like to see some posts on algorithms and their real life uses, as that would be pretty cool. Although sorting itself is pretty useful.

I’ll be writing up a Dijkstra’s Algorithm tutorial, @Sea, but I’ll wrap up this Linked List series first. Lol if I solve P = NP I’d like my million-dollar check payed to the order of @oaktree.

1 Like

Fyi Dijkstra’s Algorithm is being used in routing protocols. Looking forward to it oakey.

That’s exactly why I’m doing it!!! Also GPS…

I haven’t manage myself

In case somebody do not know what you are talking about, or wants to try:

http://www.claymath.org/millennium-problems/p-vs-np-problem

You would be contributing to mankind!

1 Like

This topic was automatically closed after 30 days. New replies are no longer allowed.