Thread: Need some linked list help

The if(pos==1)
*do this*

portion works. I just can't get the second half to work.

Hello there,


You can try the following (assuming that list element indexes start at 0)

Code:

#include <stdio.h>

/*
 * Definition of the data structure for linked list.
*/
typedef struct items item_t;
struct items
{
    int value;
    item_t *next;
};


/*
 * Prints the element in a LinkedList
 * The function returns if the list is empty.
*/
void printList(item_t *items)
{
    item_t *tmplist = items;
    while (tmplist != NULL)
    {
        printf("%d, ", tmplist->value);
        tmplist = tmplist->next;
    }
    printf("\n");
}


/*
 * Returns the number of elements in a LinkedList
 * Within this context a NULL list has 0 elemnt. 
*/
int getSize(item_t *items)
{
    item_t *tmplist = items;
    int size = 0;
    while (tmplist != NULL)
    {
        tmplist = tmplist->next;
        ++size;
    }
    
    return size;
}


/*
 * Deletes the element at the given position.
*/
item_t* deleteAtPosition(item_t *items, int const pos)
{
    if (items == NULL)
        return NULL;
    else if ((pos < 0) || (pos > getSize(items) - 1))
    {
        printf("Error: IndexOutOfRange\n");
        return items;
    }
    else if (pos == 0)
        return items->next;
    else
    {
        item_t *tmpList = items;     
        int counter = 0;
        while (counter < pos - 1)
        {
            tmpList = tmpList->next;
            ++counter;
        }
        
        item_t **ptr = &tmpList;
        (*ptr)->next = tmpList->next->next;
        
        return items;
    }
}


int main(int argc, char *argv[])
{
    item_t l1 = {12, NULL};
    item_t l2 = {13, NULL};
    item_t l3 = {14, NULL};
    item_t l4 = {15, NULL};
    item_t l5 = {16, NULL};
    item_t l6 = {17, NULL};
    
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = &l5;
    l5.next = &l6;
    
    item_t *linkedList = &l1;
    printf("size = %d\t", getSize(linkedList));
    printList(linkedList);

    linkedList = deleteAtPosition(linkedList, 4);

    printf("size = %d\t", getSize(linkedList));
    printList(linkedList);
    

    return 0;
}

Code:

$ gcc -Wall testscript.c -o testscript
$ ./testscript 
size = 6        12, 13, 14, 15, 16, 17, 
size = 5        12, 13, 14, 15, 17, 
$

Regards,
Dariyoosh

And here is a second version as a void function which takes as parameter a pointer of pointer

Code:

/*
 * Deletes the element at the given position.
*/
void deleteAtPosition(item_t **items, int const pos)
{
    if (items == NULL)
        return ;
    else if ((pos < 0) || (pos > getSize(*items) - 1))
    {
        printf("Error: IndexOutOfRange\n");
        return ;
    }
    else if (pos == 0)
        *items = (*items)->next;
    else
    {
        item_t *tmpList = *items;     
        int counter = 0;
        while (counter < pos - 1)
        {
            tmpList = tmpList->next;
            ++counter;
        }
        
        item_t **ptr = &tmpList;
        (*ptr)->next = tmpList->next->next;
    }
}

Using this version
instead of

Code:

linkedList = deleteAtPosition(linkedList, 4);

You write

Code:

deleteAtPosition(&linkedList, 4);

Regards,
Dariyoosh

As far as I can tell you have a memory leak since you over write the value of the node pointer you want to delete delete. There is also an issue if you attempt to remove the last node, in that case prev->next should be NULL, so attempting to dereference it using prev->next->next should segfault.