Linked List Replacement Function with Head, Tail, and Size Management

Question

I'm working on a SinglyLinkedList class in C++, where I maintain pointers to both the head and tail of the list, as well as an integer size to track the number of nodes. My goal is to implement a replace(int x) function that replaces each occurrence of the value x in the linked list with x number of nodes, each containing the value 1. For example, if the linked list is 4 -> 5 -> 3 -> 8 -> 5 and I call replace(3), the expected output should be 4 -> 5 -> 1 -> 1 -> 1 -> 8 -> 5. Additionally, if the value x does not appear in the list, the list should remain unchanged. The interface is:

struct SinglyLinkedList
{
    Node* head, * tail;
    int size;

    SinglyLinkedList() :head(nullptr), tail(nullptr), size(0) {}; // Default constructor
  
    void replace(int X);
};

My try:

void SinglyLinkedList::replace(int X)
{
    Node dummyHead(0, head);
    Node* curr = head, * prev = &dummyHead;
    while (curr)
    {
        if (curr->value == X)
        {
            Node* nextNode = curr->next;
            for (int i = 0; i < X; i++)
            {
                prev->next = new Node(1);
                size++;
                prev = prev->next;
            }
            if (curr == tail)
            {
                tail = prev;
            }
            prev->next = nextNode;
            curr = nextNode;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummyHead.next;
}

The basic intuition behind my approach is to traverse the linked list while maintaining pointers to the current node (curr) and the previous node (prev). When I find a node containing the value x, I replace it by inserting x new nodes, each with the value 1. I use a dummy head to simplify the insertion logic, especially when handling edge cases such as replacing the head of the list. After inserting the new nodes, I properly connect the remainder of the list and ensure that the size is updated accordingly.

Since I am working on a larger assignment in my Data Structures and Algorithms course that includes tests, I have been able to identify that the problem lies within this function. Could I get help in pinpointing the issue? Is there anything obvious that won't work? Perhaps I am not updating the tail correctly in all cases?

Answer 1

I believe your code doesn't handle deletion of original linked list nodes and maintaining accurate size. Consider explicitly deleting replaced nodes to avoid memory leaks

void SinglyLinkedList::replace(int X)
{
    Node dummyHead(0, head);
    Node* curr = head, * prev = &dummyHead;
    while (curr)
    {
        if (curr->value == X)
        {
            Node* nextNode = curr->next;
            for (int i = 0; i < X; i++)
            {
                prev->next = new Node(1);
                prev = prev->next;
            }
            size += X-1;
            if (curr == tail)
            {
                tail = prev;
            }
            delete curr; // free memory of original node
            prev->next = nextNode;
            curr = nextNode;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummyHead.next;
}