cppadvanced15 minutes

Fix Memory Leak and Logic Bug in Custom Linked List Implementation

Identify and fix the memory management and logic bugs in a custom singly linked list class implemented in C++. The list supports insertion and search operations but has subtle issues causing memory leaks and incorrect behavior.

Challenge prompt

You are given a partial implementation of a singly linked list class in C++, which manages integer values. The class supports insertion at the head and a method to check whether a value exists in the list. However, the current implementation contains memory leaks and logical errors that prevent it from working correctly under some conditions. Your task is to identify and fix all such bugs, including but not limited to memory management, pointer handling, and method logic, to make the class robust and leak-free.

Guidance

• Check the destructor and methods that allocate or deallocate memory to ensure no leaks occur.
• Verify that the search method correctly traverses the entire list and returns the expected result.
• Ensure all edge cases (e.g., empty list, single-node insertions) are handled properly.

Hints

• Remember to delete all nodes in the destructor to prevent memory leaks.
• Watch for missing return statements or infinite loops in your traversal method.
• Check if the inserted nodes correctly update the head pointer without losing access to existing nodes.

Starter code

class LinkedList {
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    ~LinkedList() {
        // Intended to free all nodes
        while (head != nullptr) {
            head = head->next; // BUG: leaks memory!
        }
    }
    void insert(int val) {
        Node* n = new Node(val);
        n->next = head;
        head = n;
    }
    bool contains(int val) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data = val) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

Expected output

After fixing, inserting values and searching should produce correct results without memory leaks. For example: LinkedList list; list.insert(10); list.insert(20); list.insert(30); searching for 20 returns true searching for 40 returns false On destruction, no memory is leaked.

Core concepts

Memory managementPointers and dynamic allocationLinked list traversalDestructor implementation

Challenge a Friend

Send this duel to someone else and see if they can solve it.