CODEWITHSUNDEEP
clinked-list
unintendedjoy
unintendedjoy

Reputation: 289

Removing duplicates in linked list in C language

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

Upvotes: 0

Views: 1304

Answers (4)

DecPK
DecPK

Reputation: 25401

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

Upvotes: 0

Deduplicator
Deduplicator

Reputation: 45704

Follow these simple steps:

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

Upvotes: 1

EvilTeach
EvilTeach

Reputation: 28882

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.

Upvotes: 0

LearningC
LearningC

Reputation: 3162

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.

Upvotes: 0

Related Questions