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 · Accepted Answer · 2014-03-16 03:55:37Z

2

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

edited Mar 16, 2014 at 3:55

answered Mar 16, 2014 at 3:40

Paradise228

7173 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Teodor Ciuraru · Accepted Answer · 2015-10-19 21:12:02Z

1

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;
}

edited Oct 19, 2015 at 21:12

answered Oct 19, 2015 at 21:00

Teodor Ciuraru

3,4871 gold badge34 silver badges40 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 12:07:25Z

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, 2017 at 12:07

CommunityBot

11 silver badge

answered Mar 16, 2014 at 3:35

uesports135

1,1233 gold badges17 silver badges26 bronze badges

Comments

Muatik · Accepted Answer · 2015-12-20 08:53:06Z

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

Collectives™ on Stack Overflow

removing duplicates in a linked list

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related