0

So I decided to learn C language this week, and I thought that implementing a linked list in C blindly is a good way to learn it(probably not), but now I'm stuck on this problem.

In my C code, I have an append() function that adds an element to the linked list and a remove_index() function that removes element on a certain index of the linked list, all seems to work fine when adding and removing element when I display the current linked list elements, but when I started to look at the memory usage of my program... after I delete and free() some of the index/node of the liked list using my remove_index() function, the memory of my program doesn't seems to go down... what am I doing wrong here?

below is my code

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

typedef struct linkedlist * int_list;
#define new_int_list() (struct linkedlist*) malloc(sizeof(struct linkedlist))

struct node
{
    int value;
    struct node *next;
};

struct linkedlist 
{
    size_t length;
    struct node *head;
    struct node *tail;
};

void append(struct linkedlist *list, int value)
{
    struct node *newnode = (struct node*) malloc(sizeof(struct node));
    newnode->value = value;
    newnode->next = NULL;

    if(list->head==NULL)
    {
        list->head = newnode;
        list->tail = newnode;
        list->tail->next = NULL;
        list->length = 1;
    }
    else{
        list->tail->next = newnode;
        list->tail = newnode;
        list->tail->next = NULL;
        list->length++;
    }
}

void remove_index_raw(const char* srcs, size_t line, struct linkedlist *list, size_t index)
{
    if(list->length==0) return;
    else if(index<0 || index>=list->length)
    {
        printf("\n\nError in file '%s' on line %ld:\n\tindex provided value is (%ld)\n\tList size is(%ld)\n\tindex overflow\n\n", srcs,line,index,list->length);
        exit(2);
    }
    else if(index==0 && list->length==1){
        free(list->head);
        list->head == NULL;
        list->tail == NULL;
        list->length = 0;
        return;
    }
    else if(index==0){
        struct node *delete_first = list->head;
        list->head = list->head->next;
        free(delete_first);
        list->length--;
        return;
    }

    struct node *iterator = list->head;
    while(--index) iterator = iterator->next;

    struct node *delete_node = iterator->next;
    iterator->next = iterator->next->next;
    free(delete_node);
    list->length--;
}
#define remove_index(list,index) remove_index_raw(__FILE__,__LINE__,list,index)

void display_list(struct linkedlist *list)
{
    size_t iterate = list->length;
    if(list->length==0) return;
    struct node* start = list->head;
    while(iterate){
        --iterate;
        printf("%d ",start->value);
        start = start->next;
    }
    printf("\n");
}

void init_list(struct linkedlist *list)
{
    list->head = NULL;
    list->tail = NULL;
    list->length = 0;
}

void main()
{
    int MAX = 10000000;

    int_list largelist = new_int_list();
    init_list(largelist);
    
    for(size_t i=0; i<MAX; ++i) append(largelist,i);

    char pause;
    printf("allocated");
    scanf("%c",&pause);

    for(size_t i=0; i<MAX; ++i) remove_index(largelist,0);
    
    printf("deallocated");
    scanf("%c",&pause);
    scanf("%c",&pause);
}
  • 1
    Irrelatively to your question your program has undefined behavior because the allocated object of the type linkedlist is not initialized. Also the function remove_index can invoke undefined behavior and moreover it does not allow to remove the first node. And even the function display_list also can invoke undefined behavior. – Vlad from Moscow Apr 25 '21 at 08:38
  • @VladfromMoscow "your program has undefined behavior because the allocated object of the type linkedlist is not initialized." how do you do that in C? do i pass it to a function that initialize values?, "does not allow to remove the first node", I'm aware of this one, "remove_index can invoke undefined behavior" what causes this?, I'm sorry I came from C++ and just use OOP all the time –  Apr 25 '21 at 09:07
  • 1
    calling malloc malloc(sizeof(struct linkedlist)) does not result in initializations of data members head, tail and length. Within the function remove_index you have to check whether a list is empty or the specified index is greater than the length of the list. And as I already pointed the function is unable to remove the first node. – Vlad from Moscow Apr 25 '21 at 09:11
  • 1
    Pay attention to that the user can pass to the function remove_index an index equal to 0. In this case the expression --index will yield the maximum value of an object of the type size_t. – Vlad from Moscow Apr 25 '21 at 09:33
  • @VladfromMoscow I edited the code and add some, how about that? –  Apr 25 '21 at 14:15
  • 1
    Notwithstanding the various program flaws that Vlad pointed out, I suspect the question is based on a faulty premise: `free`ing an allocated object makes the memory available for reallocation, but it does not necessarily return the memory to the operating system. As viewed by the OS, the memory in use by the program does not necessarily decrease. – John Bollinger Apr 25 '21 at 14:20
  • @JohnBollinger so in this case ```free```ing still works?, because I have tried to reallocated an array in heap in C assigned values to it and free it, and the memory usage decrease, but for this one it's not, how do we decrease it though? I'm so lost –  Apr 25 '21 at 14:25
  • @NateEldredge hey I think that is the answer, because I have tried to ```append()``` the same size of elements again after I have deleted each elements using ```remove_index()``` and then the memory stays the same it didn't double. Thank you. –  Apr 25 '21 at 14:36
  • @himynameisjm, As long as your program's behavior is defined in the first place, `free()` *always* works when its argument is a pointer value that was previously returned by one of the allocation functions and not subsequently freed. This is why `free()` does not need to return anything. – John Bollinger Apr 25 '21 at 14:37

0 Answers0