removing duplicates in a linked list

Question

void List::removeDup()
{
    Node *after = NULL;
    Node *dup = NULL;

    curr = head;

    while(curr->next != NULL)
    {
       after = curr->next; //node after current one
       while(after != NULL) 
       {
          if(curr->data == after->data) //if dup found
          {
             dup = after; 
             curr->next = after->next;
             delete dup;
          }
          else
          {
             after = after->next;
          }//if no dup found, advance after node
       }
          curr = curr->next; //advance curr node
    }
}

This code uses the first node and compares with the rest to find duplicates. If found, it is deleted. The error I'm getting is

pointer being freed was not allocated. Does anyone know what this means?

Any help would be appreciated

Paradise228 · Answer 1 · 2014-03-16T03:55:37.497

If you are on linux try to run valgrind to see what's actually happening in memory

Secondly there is a problem with your code: When you find a duplicate, you break your linked list

|Current| => |Node| => |Node| => |Duplicate| => |Next|

If you find a duplicate your code makes current's next point to the duplicate's next and you break it all

I think you have to do an other simpler function to remove 1 element of your list and call it when you find a duplicate

Teodor Ciuraru · Answer 2 · 2015-10-19T21:12:02.947

I created this simple and clean approach that works.

The idea is to check the if the current node's data is equal to the next one's.

If the answer is affirmative, jump over the next one and delete it (deallocate it).

If there is no duplicate at a given position, just parse the linked list as usual (the else statement).

Node* RemoveDuplicates(Node *head)
{
    if (head == nullptr) return nullptr;

    Node *curr = head;
    Node *aux;

    while (curr->next != nullptr) {
      if (curr->data == curr->next->data) {
          aux = curr->next->next;
          delete curr->next;
          curr->next = aux;
      }
      else {
          curr = curr->next;
      }  
  }
  return head;
}

score 0 · Answer 3 · edited May 23 '17 at 12:07

0

I don't know c++ that well but I think its because you never allocate dup. This might help you: Deleting a pointer in C++

edited May 23 '17 at 12:07

Community

1
1

answered Mar 16 '14 at 03:35

uesports135

1,083
2
16
25

score 0 · Answer 4 · answered Dec 20 '15 at 08:53

I am almost doing the same operations: choose the first, compare it with following items and if any following item is duplicated, break its link. and so on...

Here is my implementation:

template<typename T>
void LinkedList<T>::removeDuplicates() {
    Node<T> * current = head;
    while (current) {
        Node<T> * forward_head = current->next;
        Node<T> * forward_tail = current;
        while (forward_head) {
            if (forward_head->data == current->data) {
                // duplicated item found.
                forward_tail->next = forward_head->next;
            }
            else
                forward_tail = forward_tail->next;
            forward_head = forward_head->next;
        }
        current = current->next;
    }
}

Expected output is:

before removing: 2, 2, 2, 2, 3, 2, 1, 3, 8, 3, 2, 4, 4

after removing: 2, 3, 1, 8, 4

removing duplicates in a linked list

4 Answers4