Segmentation fault while returning a Node Linkedlist

Question

In find(T item) function I am checking if the data inputted is a string then I am handling it separately and for other data types I am handling it in else case, because I am using the string function compare() to check for the match. The program runs fine when there is a matching string in the linked list and returns the node and prints the node data, but when matching string is not found then instead of returning an empty tmp node the programs crashes and say "Segmentation fault (core dumped)". Is there a way I can fix it?

#include <iostream>
#include <typeinfo>
using namespace std;

template <typename T>
class Node {
public:
    T data;
    Node *next;
    Node *prev;

    Node(){};
};

template <typename T>
class LinkedList {
private:
    Node<T> *head;
    Node<T> *tail;

public:
    LinkedList(){
        head = NULL;
        tail = NULL;
    }

    void insertHead(T item){
        Node<T> *tmp = new Node<T>();
        if (head == NULL){
            head = tmp;
            head->prev = NULL;
            head->data = item;
            head->next = NULL;
            tail = tmp;
        } else {
            tmp->next = head;
            tmp->data = item;
            tmp->prev = NULL;
            head->prev = tmp;
            head = tmp;
        }
    }

    void insertLast(T item){
        Node<T> *tmp = new Node<T>();
        tmp->data = item;
        if (head == NULL){
            head = tmp;
            head->prev = NULL;
            head->next = NULL;
            tail = tmp;
        } else {
            tmp->prev = tail;
            tail->next = tmp;
            tmp->next = NULL;
            tail = tmp;
        }
    }

    Node<T>* find(T item){
        Node<T> *tmp = head;
        if (typeid(item) == typeid(string)){
            string s, d;
            s = item;
            d = tmp->data;
            while(tmp != NULL){
                if(s.compare(d) == 0){
                    return tmp;
                }
                tmp = tmp->next;
                d = tmp->data;
            }
            Node<string> *tmp = new Node<string>();
            tmp->data = "";
            return tmp;
        } else {
            while(tmp != NULL){
                if(tmp->data == item){
                    return tmp;
                }
                tmp = tmp->next;
            }

            tmp = new Node<T>();
            tmp->data = -1;
            return tmp;
        }
    }

    void print(){
        Node<T> *tmp;
        tmp = head;
        while (tmp != NULL){
            cout << tmp->data << "->";
            tmp = tmp->next;
        }
        cout << endl;
    }
};

int main(){

    LinkedList<string> l;
    l.insertHead("Abc");
    l.insertHead("def");
    l.insertHead("ghi jk");

    Node<string>* tmp = new Node<string>();
    tmp = l.find("ghi");
    cout << tmp << endl;

    l.print();
}

Answer 1

For starters the member function find can invoke undefined behavior in the very beginning

Node<T>* find(T item){
    Node<T> *tmp = head;
    if (typeid(item) == typeid(string)){
        string s, d;
        s = item;
        d = tmp->data;
        ^^^^^^^^^^^^^
        //

because in general head can be equal to nullptr.

In the while loop you also are not checking whether the pointer tmp is equal to nullptr.

tmp = tmp->next;
d = tmp->data;

Creating a dummy node

Node<string> *tmp = new Node<string>();
tmp->data = "";
return tmp;

is a bad idea and can lead to a memory leak. It is better to return a null pointer.

This allocation of a node in main

Node<string>* tmp = new Node<string>();
tmp = l.find("ghi");

produces a memory leak.

The function can be declared and defined at least the following way

Node<T> * find( const T &item )
{
    Node <T> *result = head;

    while ( result && result->data != item ) result = result->next;

    return result;
}

Moreover it can be overloaded the following way

template <typename BinaryPredicate>
Node<T> * find( const T &item, BinaryPredicate binary_predicate )
{
    Node <T> *result = head;

    while ( result && not binary_predicate( result->data, item ) ) result = result->next;

    return result;
}