Removing duplicates in linked list in C language

Question

I'm trying to create a removeDuplicates function that finds the duplicate values in a linked list, calls and passes in the index of which these duplicate values are found into the removeNode function (which will remove these duplicate values). The removeDuplicates function also returns the count of duplicate values removed.

But there are some error in my code, the program has to be force stopped after I choose option 3, which is the option that calls removeDuplicates function.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;

typedef struct _linkedlist 
{
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

// FUNCTION PROTOTYPES
void createLinkedList(LinkedList *ll);
void printList(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int insertSorted (LinkedList *ll, int value);
int removeDuplicates(LinkedList *ll);
int removeNode(LinkedList *ll, int index);

int main()
{
    int choice, value = 0;
    LinkedList l;
    l.head = 0;
    l.size = 0;

    printf("\n1: createLinkedList\n");
    printf("2: insertSorted\n");
    printf("3: removeDuplicates\n");
    printf("4: quit\n");

    do
    {
        printf("\nChoose an option: ");
        scanf("%d", &choice);
        fflush(stdin);

        switch (choice)
        {

            case 1:
                      createLinkedList(&l);
                      printList(&l);
                      break;
            case 2:
                      insertSorted(&l, value);
                      break;

            case 3:
                      printf("%d numbers were removed from the list", removeDuplicates(&l));
                      break;
        }
    } while (choice < 4);
    return 0;
}

.
.
.
(Other functions)
.
.
.

int removeDuplicates(LinkedList *ll)
{
    int index = 0;
    int count = 0;
    ListNode *pre, *cur;
    ListNode *temp = ll->head;

    if (temp == NULL)
        return;

    pre = ll->head;
    cur = pre->next;

    while (temp != NULL)
    {
        if ((pre->item == cur->item) && index < ll->size)
        {
            count++;
        }

        pre = cur->next;
        index++;

        if ((pre->item == cur->item) && index < ll->size)
        {
            count++;
        }

        cur = pre->next;
        index++;

        removeNode(&ll, index);
    } 
    printList(ll);
    return count;
}

int removeNode(LinkedList *ll, int index)
{

    ListNode *pre, *cur;

    // Highest index we can remove is size-1
    if (ll == NULL || index < 0 || index >= ll->size)
        return -1;

    // If removing first node, need to update head pointer
    if (index == 0)
    {
        cur = ll->head->next;  
        free(ll->head);        
        ll->head = cur;        
        ll->size--;            

        if (ll->size == 0)     
            ll->tail = 0;

        return 0;
    }

    // Find the nodes before and after the target position
    // Free the target node and reconnect the links
    if ((pre = findNode(ll, index - 1)) != NULL)
    {   

        // Removing the last node, update the tail pointer
        if (index == ll->size - 1)
        {
            ll->tail = pre;     
            free(pre->next);    
            pre->next = NULL;   

        else      
        {
            cur = pre->next->next;   
            free(pre->next);         
            pre->next = cur;         
        }
        ll->size--;      
        return 0;
    }

    return -1;
}

Deduplicator · Accepted Answer · 2014-04-15 16:08:17Z

1

Follow these simple steps:

Copy all values into an array.
Sort the array (qsort).
Write all unique values back into the list (easy, just skip if the previous value is the same).
Remove all non-overwritten nodes.

answered Apr 15, 2014 at 16:08

Deduplicator

46k7 gold badges73 silver badges125 bronze badges

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

Comments

LearningC · Accepted Answer · 2014-04-15 15:57:06Z

0

see this while loop in removeDuplicates function,

 while (temp != NULL)
    {
        if ((pre->item == cur->item) && index < ll->size)
        {
            count++;
        }

        pre = cur->next;
        index++;

        if ((pre->item == cur->item) && index < ll->size)
        {
            count++;
        }

        cur = pre->next;
        index++;

        removeNode(&ll, index);
    }

this loop never ends since you are not modifying the value of temp. so code to end the loop properly.

answered Apr 15, 2014 at 15:57

LearningC

3,1621 gold badge15 silver badges19 bronze badges

Comments

EvilTeach · Accepted Answer · 2014-04-15 16:04:13Z

0

Consider

Copying the elements into an array.

Sort the array.

Iterate the array, picking out the non duplicates and using them to construct a new list.

Delete the elements in the old list.

Point the head of the old list to the new list.

answered Apr 15, 2014 at 16:04

EvilTeach

29.1k21 gold badges89 silver badges144 bronze badges

Comments

DecPK · Accepted Answer · 2018-03-15 10:15:26Z

0

    void removeDuplicates ( )
{
    Node *current, *prev, *next, *ptp;
    ptp = current = prev = next = root;
    while ( current != NULL)
    {
        ptp = prev = next = current;
        next = next -> link;
        while ( next != NULL)
        {
            if ( next -> data == current -> data )
            {
                prev = next;
                next = next -> link;
                free (prev);`enter code here`
                prev = ptp;
                ptp -> link = next;
            } else
            {
                prev = next;
                ptp = next;
                next = next -> link;
            }
        }
        current = current -> link;
    }
}

answered Mar 15, 2018 at 10:15

DecPK

25.4k6 gold badges32 silver badges46 bronze badges

1 Comment

Nico Haase Over a year ago

Can you give some more context? This question is nearly four years old and with enter code here in between, your answer looks strange to me

Collectives™ on Stack Overflow

Removing duplicates in linked list in C language

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related