Linked list search function modifying list

Question

I am trying to implement a doubly linked list in C++ and the add function is working properly but the find node function is modifying the list. All other function like insertAfter, delete depend on this find function and hence they are also not working as expected.

I am new to C++, so I don't completely understand pointers. I simply tried to replicate my Java program in C++. I know for sure that in the find function the pointer to the head node is causing the problem but I don't completely understand how.

Below is my code :

struct Node{
int data;
Node* next;
Node* prev;


Node(int d) {
    data = d;
  };
};


struct DLL {
    Node* head;
    Node* tail;
    int size;

//Adding a Node to the Doubly LL
void addNode(Node* n) {
    //If LL is empty add the first Node
    if (tail == NULL) {
        tail = n;
        head = n;
    }
    //Else add add node to the tail. Connect n to the tails next and make n the tail
    else {
        tail->next = n;
        n->prev = tail;
        tail = n;
        tail->next = NULL;
    }

    size++;
};

//Finding a random Node in the linked List
//It will return the Node with the FIRST occurrence where data = d
Node* findNode(int d) {
//We will start at the head and then traverse through the entire list to find a Node where data = d
    Node* start = head;
     if (start == NULL) {
         cout<<"No element in the List" <<endl;
         return NULL;
     }
    // If head is the Node we are looking for
    if (start->data = d) {
        cout<< "Node found with matching data : " << start << endl;
        return start;
    }
    //While next pointer is not null, traverse to search for a match.s
    while (start->next != NULL) {
        start = start->next;
        if (start->data == d) {
            cout<< "Node found with matching data : " << start << endl;
            return start;
        }
    }

    cout << "No node found with matching data = " << d <<endl;
    return NULL;
};
};

Answer 1

This is a good time to learn about constness.

Node* findNode(int d) {
//We will start at the head and then traverse through the entire list to find a Node where data = d
    Node* start = head;
     if (start == NULL) {
         cout<<"No element in the List" <<endl;
         return NULL;
     }
    // If head is the Node we are looking for
    if (start->data = d) {
        cout<< "Node found with matching data : " << start << endl;
        return start;
    }

This function has write access to the list, and you don't want that. Unfortunately, you abuse this access in the last if statement:

    if (start->data = d) {

this code assigns the value of d to start->data and then tests if the value assigned to it was not null.

We can mark this function as const easily:

//////////////////////vvvvv/////////////////
Node* findNode(int d) const {
//We will start at the head and then traverse through the entire list to find a Node where data = d
    Node* start = head;
     if (start == NULL) {
         cout<<"No element in the List" <<endl;
         return NULL;
     }
    // If head is the Node we are looking for
    if (start->data = d) {
        cout<< "Node found with matching data : " << start << endl;
        return start;
    }

and now the if will generate a compiler error.

A cleaned up version of your code might look something like the following:

#include <iostream>

struct Node {
    int data_;
    Node* next_ { nullptr };
    Node* prev_ { nullptr };

    Node(int data) : data_(data) {}
};


struct DLL {
    Node* head_ { nullptr };
    Node* tail_ { nullptr };
    int size_ { 0 };

    //Adding a Node to the Doubly LL
    void addNode(Node* node) {
        //If LL is empty add the first Node
        if (tail_ == nullptr) {
            tail_ = node;
            head_ = node;
            node->prev_ = node->next_ = nullptr;
        }
        //Else add add node to the tail. Connect n to the tails next and make n the tail
        else {
            tail_->next_ = node;
            node->prev_ = tail_;
            tail_ = node;
            node->next_ = nullptr;
        }

        size_++;
    }

    //Finding a random Node in the linked List
    //It will return the Node with the FIRST occurrence where data = d
    Node* findNode(int data) const {
        //We will start at the head and then traverse through the entire list to find a Node where data = d
        //While next pointer is not null, traverse to search for a match.s
        for (Node* start = head_; start != nullptr; start = start->next_) {
            if (start->data_ == data) {
                std::cout << "Node found with matching data : " << start << '\n';
                return start;
            }
        }

        std::cout << "No node found with matching data = " << data << '\n';
        return nullptr;
    }
};

int main()
{
    DLL dll;

    Node n1(1), n3(3), n5(5);
    dll.addNode(&n1);
    dll.addNode(&n3);
    dll.addNode(&n5);

    if (dll.findNode(1) != &n1)
        std::cerr << "wrong result for findNode(1)\n";
    if (dll.findNode(2) != nullptr)
        std::cerr << "wrong result for findNode(2)\n";
    if (dll.findNode(3) != &n3)
        std::cerr << "wrong result for findNode(3)\n";
    if (dll.findNode(4) != nullptr)
        std::cerr << "wrong result for findNode(4)\n";
    if (dll.findNode(5) != &n5)
        std::cerr << "wrong result for findNode(5)\n";
}

Live demo: http://ideone.com/X34EgY

Answer 2

start->data = d

This line in your second if block is assigning d to start->data rather than comparing the two.