Create Fixed Size Linked List in C

Question

I have created a linked list in C that is used to store data which is then modified as required. In creating the linked list I have used the following

struct car_elements
{
  char car_rego[7];
  double time_parked;
  struct car_elements *next;
};

typedef struct car_elements car;

/* Defined as global variable to hold linked list */
car *head = NULL;

car *SetupCars()
{
  car *ptr = head;
  car *new_car = NULL;

  new_car = (car*) malloc(sizeof(car));
  if (!new_car)
  {
    printf("\nUnable to allocate memory!\n");
    exit(1);
  }

  strcpy(new_car->car_rego, "empty");
  new_car->time_parked = time(NULL);
  new_car->next = NULL;

  if (ptr == NULL)
  {
    return (new_car);
  }
  else
  {
    while (ptr->next)
    {
      ptr = ptr->next;
    }
    ptr->next = new_car;
    return (head);
  }
}

From main I call the following to create the linked list

for(int i = 0; i<TOTAL_CARS; i++) {
   head = SetupCars(head);       
}

The problem is that now I have a memory leak - Is there a better way to create a fixed size linked list. At the end of the program running I can

free(head);

However I cannot call within SetupCars method

free(new_car);

I could create new_car as a global variable I guess and free it at the end of the program but I cannot help but feel there is a better way to do it. I don't think global variables are evil if used properly however I would appreciate some advice.

First of all - use valgrind with: valgrind --leak-check=full --track-origins=yes ... — mousomer
– mousomer, Commented Sep 8, 2013 at 7:22

Manoj Pandey · Accepted Answer · 2013-09-08 07:23:33Z

4

WHy not just free it at the end? SOmething like this:

car *tofree;
car *ptr = head;
while(ptr) {
    tofree = ptr;
    ptr = ptr->next;
    free(tofree);
}

answered Sep 8, 2013 at 7:23

Manoj Pandey

4,6661 gold badge20 silver badges18 bronze badges

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

Comments

Basile Starynkevitch · Accepted Answer · 2013-09-08 07:43:05Z

3

You need a function to free the entire list, like:

void free_cars(car*p)  {
   while (p != NULL) {
      car* nextp = p->next;
      free (p);
      p = nextp;
   }
}

So you would call

free_cars (head);
head = NULL;

Perhaps even by having a macro

#define DELETE_CARS(CarsVar) do { \
   free_cars(CarsVar); CarsVar = NULL; } while(0)

then just write DELETE_CARS(head); later in your code.

And indeed, manual memory management is painful, you need to avoid memory leaks. Tools like valgrind can be helpful. And you could consider instead to use Boehm's garbage collector, so use GC_MALLOC instead of malloc and don't bother freeing memory.... Read more about garbage collection.

edited Sep 8, 2013 at 7:43

answered Sep 8, 2013 at 7:23

Basile Starynkevitch

231k18 gold badges323 silver badges578 bronze badges

1 Comment

smuzoen Over a year ago

Checked with valgrind and no memory leaks - you guys are great. Cheers

Community · Accepted Answer · 2017-05-23 12:05:11Z

1

Keep car *head as a global var. For SetupCars:

void SetupCars() /* void will do, unless you want a copy of the new "car" */
{
  car *new_car = NULL;
  new_car = malloc(sizeof *new_car); /* don't need to cast return value of malloc */

  /* do checks and setup new_car... */

  if (head == NULL) /* first element */
  {
     head = new_car;
  }
  else /* easier to add new_car as the FIRST element instead of last */
  { 
     new_car->next = head;
     head = new_car;
  }
}

From main you create the linked list the same way:

for(int i = 0; i<TOTAL_CARS; i++) {
   SetupCars(); /* without any arguments */
}

Then at the end, you loop through the list and free the objects. As Manoj Pandey posted in his answer:

car *tofree;
car *ptr = head;
while(ptr) {
    tofree = ptr;
    ptr = ptr->next;
    free(tofree);
}

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Sep 8, 2013 at 9:05

James Chong

2,0531 gold badge17 silver badges14 bronze badges

1 Comment

smuzoen Over a year ago

Fantastic - checked with valgrind and no memory leaks - All heap blocks were freed - no leaks are possible. I still have a lot to learn but I really appreciate your help. Perfect solution to the problem I was having.

Collectives™ on Stack Overflow

Create Fixed Size Linked List in C

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related