Find an Element in a Linked List

Question

The find function is designed to start at the given node and return the index of the node with the value valueInput (indices start at 0). Return -1 if valueInput does not exist. How can this code be improved, optimized and free of potential runtime errors? Please note I am new to data structures and algorithms.

#include <iostream>


class Node {
    public:
        int value;
        Node* next = NULL;
};

void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = 
            (struct Node*) malloc(sizeof(struct Node)); 

    /* put in the data */
    new_node->value = new_data; 

    /* link the old list off the new node */
    new_node->next = (*head_ref); 

    /* move the head to point to the new node */
    (*head_ref) = new_node; 
}

int find(struct Node *head, int n) 
{ 
    int count = 1; 

    //if count equal too n return node->data 
    if(count == n) 
    return head->value; 

    //recursively decrease n and increase  
    // head to next pointer  
    return find(head->next, n-1);  
} 

int main() 
{ 
    struct Node* head = NULL; 

    push(&head, 1); 
    push(&head, 4); 
    push(&head, 1); 
    push(&head, 12); 
    push(&head, 1);   

    printf("Element at index 3 is %d", find(head, 3));   
    getchar(); 
    return 0;
} 

Answer 1

Overall

You don't use encapsulation. Which makes your list vulnerable to incorrect initialization and accidental incorrect modification from outside the list.

You use several C based style choice rather than C++ style which make your codde harder to read.

Code Review

Only a list of int?

class Node {
    public:
        int value;          // int only
        Node* next = NULL;
};

---

Passing a pointer to a pointer. You can simplify this by passing a reference.

void push(struct Node** head_ref, int new_data) 

---

In C++ you don't need to use struct keyword when using struct types.

void push(struct Node** head_ref, int new_data) 

---

A better declaration would have been:

void push(Node*& head_ref, int new_data) 

---

C++ you should always use new (rather than the malloc family).

    /* allocate node */
    struct Node* new_node = 
            (struct Node*) malloc(sizeof(struct Node)); 

There are two reasons for this:

1. If your code combines both C and C++ memory allocation you need to track which is which and use the correct de-allocation method. Thus it is best to simply use one allocation method then you always know how to deallocate it.

2. Using new calls the constructor to initialize the object.
   Remember this line from your class declaration.

       Node* next = NULL;
   

This is not going to happen if you call malloc() you must use new to get that to happen.

3. Its also simpler to write:

   Node* new_node = new Node{new_data, *head_ref};
   

---

Your find returns the nth index of the list. But your index is 1 based. Most C based languages use a zero based index. But if I pass 0 to find() this function will recurse for ever.

---

In recursive funtions always check for the end of the recursion first. So as the first check in find you should check that the list pointer is not nullptr.

---

This is not modified.

    int count = 1; 

So this should be a constexpt. The whole point of using a named type is to make the code more expressive. A better name would help the code be more expressive.

---

Don't leave redundant code commented out. Delete it.

    //if count equal too n return node->data 

Source control system allow you to keep older versions of the code around

It is now easy to install git on all machines learn to use it.

---

Use better indentation

    if(count == n) 
    return head->value; 

---

In C++ we use nullptr rather than NULL.

    struct Node* head = NULL; 

The difference is that nullptr is correctly typed as a pointer, while NULL is a macro (bad) for an integer (bad type). Thus you can not incorrectly use nullptr while NULL can be abused.

---

In C++ we use the C++ streams std::cout.

    printf("Element at index 3 is %d", find(head, 3));   

The C++ streams have a more advanced type checking system that prevents accidents.

    std::cout << "Element at index 3 is " << find(head, 3);

Beter implementation

template<typename T>
class LinkedList
{
    struct Node {
            T value;
            Node* next;
    };
    Node*   root;

    public:
        LinkedList()
            : root(nullptr)
        {}
        ~LinkedList() {
            while(root) {
                Node* next = root->next;
                delete root;
                root = next;
            }
        }
        LinkedList(LinkedList const&)            = delete;
        LinkedList& operator=(LinkedList const&) = delete;

        void push(T const& new_data) 
        {
            root= new Node{new_data, root};
        }

        int find(int n) 
        { 
            Node* result = findElement(root, n);
            if (result == nullptr) {
                throw std::runtime_error("message"); 
            }
            return result->value;
        }
    private:
        Node* findElement(Node* n, int n) {
            if (n == nullptr) {
                return nullptr;
            }

            if (n == 0) {
                return n;
            }
            return findElement(n->next, n-1);
        } 
}

Main.cpp

int main() 
{ 
    LinkedList<int> list; 

    list.push(1); 
    list.push(4); 
    list.push(1); 
    list.push(12); 
    list.push(1);   

    std::cout << "Element at index 3 is " << find(head, 2) << "\n";   
    getchar(); 
} 

Answer 2

1. You never check if head was assigned a valid pointer before dereferencing it here:

int find(struct Node *head, int n) 
{ 
    int count = 1; 

    //if count equal too n return node->data 
    if(count == n) 
    return head->value; // <--- here

    //recursively decrease n and increase  
    // head to next pointer  
    return find(head->next, n-1); // <--- here 
} 

2. Why are you using malloc in c++ code?

 (struct Node*) malloc(sizeof(struct Node));

3. Missing functions from your stack interface

Where are the functions like pop() and an appropriate destructor to free memory, and remove single nodes from the stack?