0

I want to delete all duplicates from a linked list. I know there is an exact program on GeeksForGeeks which is very similar to mine and I could use that, but I want to understand why mine is not working.

Code:

class Node {
    public:
        int data;
        Node *next;
 
};

void removeDuplicatesAlpha(Node* start)
{
    Node* ptr1 = start;
    Node* ptr2 = NULL;
    Node* dup = NULL;
    int i = 0;

    /* Pick elements one by one */
    while (ptr1 != NULL && ptr1->next != NULL)
    {
        ptr2 = ptr1->next;
        //0 1 2 3 4
        /* Compare the picked element with rest
           of the elements */
        while (ptr2 != NULL && ptr2->next != NULL)
        {
            cout << i;
            i++;

            /* If duplicate then delete it */
            if (ptr1->data == ptr2->data)
            {
                /* sequence of steps is important here */
                dup = ptr2;
                ptr2 = ptr2->next;
                delete(dup);
            }
            else /* This is tricky */
                ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}

int main()
{
    Node* head = NULL;

    push(&head, 3);
    push(&head, 3);
    push(&head, 20);
    push(&head, 14);
    push(&head, 9);
    push(&head, 20);
    push(&head, 20);

    printList(head);

    //removeDuplicates(head);
    removeDuplicatesAlpha(head);

    printList(head);

    deleteList(&head);

    return 0;
}

The last i printed is 4.

This is the error: Exception thrown: read access violation. ptr2 was 0xDDDDDDDD.

I'm so sorry if this is a dumb question but I just started working with Data Structures in C++.

Alexandru Manolache
  • 31
  • 3
  • Please extract and provide a [mcve]. For this kind of programs, it also helps if you step through it with a debugger or create a diagram of your data structures. As a new user here, also take the [tour] and read [ask]. – Ulrich Eckhardt Jan 30 '21 at 15:25
  • `0xDDDDDDDD` your debugger is trying to tell you something. Related: [https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations](https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations) `0xDDDDDDDD` means freed heap memory. – drescherjm Jan 30 '21 at 15:25

1 Answers1

1
            dup = ptr2;
            ptr2 = ptr2->next;
            delete(dup);

This deletes one of the Nodes.

If you review your what's in your Node class, you will see that each Node has a next pointer, that links to the next node in the list.

The above code deletes the actual Node, but it does nothing, whatsoever, to any of the next pointers in the linked list. The previous Node in the linked list: it's next is still pointing to this Node. You just deleted this Node. It no longer exists. Attempting to use and dereference the previous Node's next, that was pointing to the deleted Node becomes undefined behavior. This must be the reason for your crash.

You will need to update your logic in order to update the next pointers in your linked list accordingly.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • If the code is otherwise correct, the only thing that needs fixing, is to change ```ptr2 = ptr2->next``` to ```ptr1 = ptr2->next```. That way you make the previous pointer point past the deleted node, and to the next. – cptFracassa Jan 30 '21 at 15:55
  • I'm aware that the code deletes the actual node, but it does delete the node that I want to ignore, because I changed ptr2 to point past the node that I delete. I'm imagining something like this: ptr2 -> data1, ptr2.next ptr2.next -> data2, ptr2.next.next ```dup = ptr2; ptr2 = ptr2->next; delete(dup); ``` ptr2->data2, ptr2.next.next – Alexandru Manolache Jan 30 '21 at 16:20
  • 1
    You can set ptr1, ptr2 to anything you want. That's not going to do anything to the actual linked list nodes. C++ does not work this way. – Sam Varshavchik Jan 30 '21 at 16:27
  • You need to change the next pointer of the node that points to the one you delete. – drescherjm Jan 30 '21 at 16:39