sublist_search.cpp File Reference

Implementation of the Sublist Search Algorithm More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for sublist_search.cpp:

Go to the source code of this file.

Classes
struct	search::sublist_search::Node
	A Node structure representing a single link Node in a linked list. More...
class	TestCases
	class encapsulating the necessary test cases More...

Namespaces
namespace	search
	for std::assert
namespace	sublist_search
	Functions for the Sublist Search implementation.

Functions
void	search::sublist_search::printLinkedList (Node *start)
	A simple function to print the linked list.
Node *	search::sublist_search::makeLinkedList (const std::vector< uint64_t > &data)
	Give a vector of data, it adds each element of vector in the linked list and return the address of head pointer.
void	search::sublist_search::deleteList (Node *const root)
bool	search::sublist_search::sublistSearch (Node *sublist, Node *mainList)
	Main searching function.
static void	test ()
	Self-test implementations.
int	main (int argc, char *argv[])
	Main function.

Detailed Description

Implementation of the Sublist Search Algorithm

Algorithm

• Sublist search is used to detect a presence of one list in another list.
• Suppose we have a single-node list (let's say the first list), and we want to ensure that the list is present in another list (let's say the second list), then we can perform the sublist search to find it.
• For instance, the first list contains these elements: 23 -> 30 -> 41, and the second list contains these elements: 10 -> 15 -> 23 -> 30 -> 41 -> 49. At a glance, we see that the first list presents in the second list.

Working

• The sublist search algorithm works by comparing the first element of the first list with the first element of the second list.
• If the two values don't match, it goes to the next element of the second list. It does this until the two values match.

Author

Nitin Sharma

Definition in file sublist_search.cpp.

Function Documentation

deleteList()

void search::sublist_search::deleteList

(

Node *const

root

)

Definition at line 101 of file sublist_search.cpp.

                                  {
    if (root != NULL) {
        deleteList(root->next);
        delete root;
    }
}

main()

int main	(	int	argc,
		char *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

< Main list in which sublist is to be searched

< Sublist to be searched

< Main list in which sublist is to be searched

< boolean to check if the sublist exists or not

Definition at line 360 of file sublist_search.cpp.

                                 {
    test();  // run self-test implementations
 
    std::vector<uint64_t> mainlistData = {
        2, 5, 6, 7, 8};  
    std::vector<uint64_t> sublistData = {6, 8};  
 
    search::sublist_search::Node *mainlistLL =
        search::sublist_search::makeLinkedList(mainlistData);
    search::sublist_search::Node *sublistLL =
        search::sublist_search::makeLinkedList(
            sublistData);  
 
    bool exists = search::sublist_search::sublistSearch(
        sublistLL,
        mainlistLL);  
 
    std::cout << "Sublist: " << std::endl;
    search::sublist_search::printLinkedList(sublistLL);
 
    std::cout << "Main list: " << std::endl;
    search::sublist_search::printLinkedList(mainlistLL);
    std::cout << std::endl;
 
    if (exists) {
        std::cout << "[TRUE] - sublist found in main list\n";
    } else {
        std::cout << "[FALSE] - sublist NOT found in main list\n";
    }
 
    deleteList(mainlistLL);
    deleteList(sublistLL);
    return 0;
}

makeLinkedList()

Node * search::sublist_search::makeLinkedList

(

const std::vector< uint64_t > &

data

)

Give a vector of data, it adds each element of vector in the linked list and return the address of head pointer.

Parameters

data	A vector of "int" containing the data that is supposed to be stored in nodes of linked list.

Returns

Node* A head pointer to the linked list.

This is used in test cases for rapidly creating linked list with 100+ elements, instead of hard-coding 100 elements in test cases.

Definition at line 74 of file sublist_search.cpp.

                                                      {
    Node *head = nullptr;
    Node *tail = nullptr;
    for (int i : data) {
        Node *node = new Node;
        node->data = i;
        node->next = nullptr;
        if (head == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = tail->next;
        }
    }
    return head;
}

printLinkedList()

void search::sublist_search::printLinkedList

(

Node *

start

)

A simple function to print the linked list.

Parameters

start

The head of the linked list

Returns

void

Definition at line 58 of file sublist_search.cpp.

                                  {
    while (start != nullptr) {
        std::cout << "->" << start->data;
        start = start->next;
    }
    std::cout << std::endl;
}

sublistSearch()

bool search::sublist_search::sublistSearch	(	Node *	sublist,
		Node *	mainList )

Main searching function.

Parameters

sublist	A linked list which is supposed to be searched in mainList.
mainList	A linked list in which sublist will be searched.

Returns

true if the sublist is found

false if the sublist is NOT found

Initialize target pointer to the head node of sublist.

Initialize main pointer to the current node of main list.

If the data of target node and main node is equal then move to the next node of both lists.

Is target pointer becomes null that means the target list is been traversed without returning false. Which means the sublist has been found and return ture.

set the target pointer again to stating point of target list.

set the main pointer to the next element of the main list and repeat the algo.

If the main list is exhausted, means sublist does not found, return false

Definition at line 115 of file sublist_search.cpp.

                                                  {
    if (sublist == nullptr || mainList == nullptr) {
        return false;
    }
 
    Node *target_ptr = sublist;
 
    while (mainList != nullptr) {
        Node *main_ptr = mainList;
 
        while (target_ptr != nullptr) {
            if (main_ptr == nullptr) {
                return false;
 
            } else if (main_ptr->data == target_ptr->data) {
                target_ptr = target_ptr->next;
                main_ptr = main_ptr->next;
 
            } else {
                break;
            }
        }
 
        if (target_ptr == nullptr) {
            return true;
        }
 
        target_ptr = sublist;
 
        mainList = mainList->next;
    }
 
    return false;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 349 of file sublist_search.cpp.

                   {
    TestCases tc;
    tc.runTests();
}