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

linkedlist
c++
datastructures

(oaktree) #1

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.


#2

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

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.


(oaktree) #3

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.


#4

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


(oaktree) #5

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


(pico) #6

I haven’t manage myself :slight_smile:

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!


(oaktree) #7

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