Home / Questions / 27074
Accepted
NaCl
Asked: 2020-10-12 10:50:51 +0800 CST 2020-10-12 10:50:51 +0800 CST

Remove an item from a "list"

  • 772

Good,

I'm learning to work with pointers in C and I have a question about an algorithm I'm implementing that makes extensive use of malloc, reallocand free, this is the code:

List.h

#ifndef _LIST_H_
#define _LIST_H_

typedef struct {
    int    Count;
    void **Elements;
} List;

List *list_new();
void  list_insert(List *l, void *elem);
void *list_getelem(List *l, int offset);
void  list_removeoffset(List *l, int elem);
void  list_free(List *l);
int   list_get_count(List *l);

#endif

List.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

List *list_new() {
    List *ptr = malloc(sizeof(List));
    ptr->Elements = malloc(sizeof(void*));
    ptr->Count = 0;
    return (ptr) ? ptr : NULL;
}
void list_insert(List *l, void *elem) {
    if (l->Count == 0) 
        l->Elements = realloc(l->Elements, sizeof(void*));
    else 
        l->Elements = realloc(l->Elements, (sizeof(void*) * l->Count));
    l->Elements[l->Count] = elem;
    l->Count++;
}
void *list_getelem(List *l, int offset) {
    if (offset < 0 || offset >= l->Count) return NULL;
    return l->Elements[offset];
}
void list_removeoffset(List *l, int elem) {
    if (elem < 0 || elem >= l->Count) return;
    l->Elements[elem] = NULL; 
    l->Count--; 
    l->Elements = realloc(l->Elements, sizeof(void*) * l->Count);   
}
void list_free(List *l) {
    if (l) {
        free(l->Elements); free(l);
    }
}
int list_get_count(List *l) {
    return l->Count;
}

My problem arises within the method declaration list_removeoffset(...)I can't remove an element at a position offsetin the pointer array.

main():

List *MyList = list_new();

list_insert(MyList, (int*)3416); printf("List Count Now: %d\n", list_get_count(MyList));
list_insert(MyList, (char*)"hello world"); printf("List Count Now: %d\n", list_get_count(MyList));
list_insert(MyList, (int*)5); printf("List Count Now: %d\n", list_get_count(MyList));

This is the result I get with the above code:

List Count Now: 1
List Count Now: 2
List Count Now: 3
Element at position 1: hello world

It sure works, but when trying the following code to remove the elements:

list_removeoffset(MyList, 1); // Intento remover el elemento en la posicion 1.

Apparently it is deleted, but, in the same way, it frees the memory of the other elements that are after this one and shows me the result 0.

How can I remove or release just one item and not all the ones after it?

c

3 Answers

  1. Best Answer

    First of all, your implementation is quite inefficient in computational time for the amount of reallocyou are using. Note that in the worst case it realloccopies memory blocks. So, an operation that on a linked list is O(1)on your list ends up being O(n). I recommend keeping a physical and a logical size in your list and only resize the vector "up" when the logical size is very close to the physical and "down" when the logical size is very small relative to the physical.

    Moving on to your question, reallocit does reduce the size of the memory block it uses but only that. It is your responsibility as the implementer to "advance" the remaining list items before the free space. Schematically, something like this happens:

    original vector:

    ------------------------
0: ptr to 3416
1: ptr to "hello world"
2: ptr to 5
------------------------

    After reallocating l->Countand l->Elements[1]:

    ------------------------
0: ptr to 3416
1: NULL
2: ptr to 5
------------------------

    After realloc:

    ------------------------
0: ptr to 3416
1: NULL
------------------------
2: ptr to 5 <<< Fuera del bloque, y la memoria ya no le pertenece a tu programa

    In short, what happens is not that all the data of the vector from which you are deleting are released, but that the last one is lost. In your particular case, since the array has only three elements, the last element is also "all elements from delete".

    What you should do is, instead of assigning NULLto Elements[1], copy the contents of Elements[2](and from [3]to [2], from [4]to [3]and so on) to it. In this way, before reallocyou would have the vector like this:

    ------------------------
0: ptr to 3416
1: ptr to 5 <<< Copiado de [2]
2: ptr to 5
------------------------

    And after the realloc:

    ------------------------
0: ptr to 3416
1: ptr to 5
------------------------
2: ptr to 5
    • 2

  2. By doing the deletion you are setting the element elemto NULL and then realloc, thus losing the last element. This is the thing withlist_removeoffset(MyList, 1); 

    Count = 3                                 Count = 2
Elem 0 : (void*) 3416                     (void*) 3416
Elem 1 : (void*) "hello world"   =====>   (void*) NULL
Elem 2 : (void*) 5

    And this is what you want to get:

    Count = 3                                 Count = 2
Elem 0 : (void*) 3416                     (void*) 3416
Elem 1 : (void*) "hello world"   =====>   (void*) 5
Elem 2 : (void*) 5

    To do this you have to reassign all elements from elem+1to the end to a lower position in the array:

    void list_removeoffset(List *l, int elem) {
    int i;
    if (elem < 0 || elem >= l->Count) return;
    --(l->Count);
    for( i=elem; i<l->Count; ++i ) {
      l->Elements[i] = l->Elements[i+1];
    }
    l->Elements = realloc(l->Elements, sizeof(void*) * l->Count);   
}

    Notice that you list_inserthave an error. When Count is equal to 1, size is reserved for one element but it should be reserved for two; 1 for the one that already exists and one for the new one. The same happens for larger values. The correct way would be :

    void list_insert(List *l, void *elem) {
    l->Elements = realloc(l->Elements, sizeof(void*)*(l->Count+1));
    l->Elements[l->Count] = elem;
    ++l->Count; 
}
    • 1

  3. I think the problem is that you are doing a realloc at a smaller size. This C function is low level and doesn't take nulls into account, so it's just removing things from the end of the array. By the way, shrinking has no defined behavior, so you might as well remove the elements from the beginning.

    What you want to achieve, which is to use fair memory, is achieved with linked lists. The only bad thing is that iterating over them is slower since they are not in contiguous memory locations (cache misses). But more "spectacular" approximations can be made that allocate memory by blocks.

    • 0