Implementing and using a dynamic array in C

Question

I'm trying to make a list of students that stores structs using a dynamically allocated array. For this I have the following structs:

typedef struct s_student 
{ 
    char name[64];     
    int matrikelNummer; 
} student; 

typedef struct s_studentList 
{ 
    student* students;
    int numberOfStudents; 
} studentList;

This is how I use them so far:

int main(int argc, char** argv) {

    studentList* list = NULL;
    list = (studentList*) malloc(sizeof(studentList));

    list->numberOfStudents =1;
    //list->students->matrikelNummer = 1;
    //strcpy(list->students->name , "karim");

    printf("numberOfStudents : %d\n" , list->numberOfStudents );
    //printf("matrikelNummer   : %d\n" , list->students->matrikelNummer);
    //printf("name             : %d\n" , list->students->name);

    free(list);

    return 0;
}

That seems to work with no problems. But when I try to assign data to the students (matrikelNummer or name) as outlined in the commented lines, I receive a Segmentation fault.

What am I doing wrong?

The `malloc` function does not initialize the memory it allocated. The `list->students` pointer is uninitialized and *indeterminate*. Attempting to dereference it without making it point somewhere valid leads to [*undefined behavior*](https://en.wikipedia.org/wiki/Undefined_behavior). — Some programmer dude, Jan 09 '18 at 14:48
You've not allocated memory for `list->students` to point to. It's garbage and will give you undefined behavior, which in your case is a segmentation fault. — Sean, Jan 09 '18 at 14:48
As for the secondary problem, about making a *list*. Go search the Internet. There are many tutorials on how to create linked lists. Either that, or use a dynamically allocated array. — Some programmer dude, Jan 09 '18 at 14:49
`list->students` is never initialized. Thus, attempting to access a member of `student` here will cause a segfault. — Zinki, Jan 09 '18 at 14:49
That means you're code is probably in C++. C and C++ are very different things and what works in C++ does not always work in C and vice versa. You should look up the differences and see which one you want to use. — zee, Jan 09 '18 at 14:51
If you're really programming in C++, then I suggest you [get a good beginners book or two](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to read, and learn it *properly*. That means you will never have to write a linked list or a dynamic array as those already exists in the C++ standard library. In your specific case all you need is `std::vector`. — Some programmer dude, Jan 09 '18 at 14:55
Step 0: Find out how to configure your IDE to use a C compiler. [And remove the cast to malloc.](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — moooeeeep, Jan 09 '18 at 15:09
Almost a duplicate of https://stackoverflow.com/questions/37549594/crash-or-segmentation-fault-when-data-is-copied-scanned-read-to-an-uninitializ — Lundin, Jan 09 '18 at 15:40

Piotr Styczyński · Accepted Answer · 2018-01-09T16:16:51.597

Not allocated pointers

The problem is that you do:

// list points to null after that line
studentList* list = NULL;

// allocate memory for the list struct
list = (studentList*) malloc(sizeof(studentList));

// set field inside list struct
list->numberOfStudents =1;

// list->students is a pointer, but pointers should point to something valid
// So the question is:  Was list->students set to NULL?
// Or was it mallocated?
list->students->matrikelNummer = 1;

So you access list->students that is a pointer.
List itself was allocated via malloc so its fine.
But malloc reserves space for only the list object you want. It does not mallocate anything else.

So list->students is a pointer that is not mallocated - that's why we get the segmentation fault error.

Solution to this problem is pretty straightforward - we have to allocate not only a list but all pointers we use (in this case its students member):

// That was earlier there:
studentList* list = NULL;
list = (studentList*) malloc(sizeof(studentList));

// After allocating place for list also allocate place for list->students:
list->students = (student*) malloc(sizeof(student));

Detection of invalid memory usage

In a case when you get segmentation faults or memory leaks it's good to know that there are plenty of tools to help programmers detect such a nasty errors.

One of them is Valgrind

Valgrind is available for Linux (and probably for Windows but buggy and untested).

It's awesome tools that can traverse your program and notify you about any leaks, invalid frees and usage of forbidden memory addresses.

Example usage of Valgrind:

# Compile your code
gcc list.c -o list
# Use Valgrind
valgrind --tool=memcheck ./list

And what valgrind shows:

==26761== Memcheck, a memory error detector
==26761== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==26761== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==26761== Command: ./list
==26761==
==26761== Use of uninitialised value of size 8
==26761==    at 0x4006A1: main (in /home/students/inf/p/ps386038/stack/list)
==26761==
==26761== Invalid write of size 4
==26761==    at 0x4006A1: main (in /home/students/inf/p/ps386038/stack/list)
==26761==  Address 0x40 is not stack'd, malloc'd or (recently) free'd
==26761==
==26761==
==26761== Process terminating with default action of signal 11 (SIGSEGV)
==26761==  Access not within mapped region at address 0x40
==26761==    at 0x4006A1: main (in /home/students/inf/p/ps386038/stack/list)
==26761==  If you believe this happened as a result of a stack
==26761==  overflow in your program's main thread (unlikely but
==26761==  possible), you can try to increase the size of the
==26761==  main thread stack using the --main-stacksize= flag.
==26761==  The main thread stack size used in this run was 8388608.
==26761==
==26761== HEAP SUMMARY:
==26761==     in use at exit: 16 bytes in 1 blocks
==26761==   total heap usage: 1 allocs, 0 frees, 16 bytes allocated
==26761==
==26761== LEAK SUMMARY:
==26761==    definitely lost: 0 bytes in 0 blocks
==26761==    indirectly lost: 0 bytes in 0 blocks
==26761==      possibly lost: 0 bytes in 0 blocks
==26761==    still reachable: 16 bytes in 1 blocks
==26761==         suppressed: 0 bytes in 0 blocks
==26761== Rerun with --leak-check=full to see details of leaked memory
==26761==
==26761== For counts of detected and suppressed errors, rerun with: -v
==26761== Use --track-origins=yes to see where uninitialised values come from
==26761== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

So it shows that you access invalid address in function main:

==26761== Invalid write of size 4
==26761==    at 0x4006A1: main (in /home/students/inf/p/ps386038/stack/list)
==26761==  Address 0x40 is not stack'd, malloc'd or (recently) free'd

And says the address (pointer is not even allocated)!

Correct C list implementation

If you want to implement a pointers structure that holds list of students then one common approach is to put a pointer to the next student (next on the list) into the s_student structure.

And pointers to the first and last student into the student list.

One working example is the following I wrote myself:

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

typedef struct s_student student;

struct s_student 
{ 
  char name[64];     
  int matrikelNummer; 
  // This will point to the next student on the list
  student* nextStudent;
}; 

typedef struct s_studentList 
{ 
  student* student;
  // This will point to the last available student
  student* lastStudent;
  // This will point to the first available student
  student* firstStudent;
  int numberOfStudents; 
} studentList;

// Allocates the list
void allocStudentsList(studentList** list) {
    if(list == NULL) return;
    *list = (studentList*) malloc(sizeof(studentList));
    (*list)->lastStudent = NULL;
    (*list)->firstStudent = NULL;
}

// To add the student to the list
void addStudentToList(studentList* list, student studentData) {

    if(list == NULL) return;

    // Allocate a place for the next student
    student* st = (student*) malloc(sizeof(student));

    // If it's first student in the list
    if(list->lastStudent == NULL) {
        list->lastStudent = st;
        list->firstStudent = st;
    } else {
        // The next student after the current last student will be the newly created one
        list->lastStudent->nextStudent = st;
    }

    // Fill the student data
    *st = studentData;
    st->nextStudent = NULL;

    // Set the last available student to the one created
    list->lastStudent = st;

}

// To recurisvely free the students
void freeStudent(student* stud) {
    if(stud->nextStudent != NULL) {
        // Free next student recursively
        freeStudent(stud->nextStudent);
    }
    free(stud);
}

// To free the students list
void freeStudentsList(studentList* list) {
    if(list != NULL) {
        freeStudent(list->firstStudent);
        free(list);
    }
}

// Function that prints single student and returns next one (after him on the list)
student* printStudent(student* stud) {
    if(stud == NULL) return NULL;
    printf("  * Student { matrikelNummer = %d }\n", stud->matrikelNummer);
    // Return next student
    return stud->nextStudent;
}

// Function that prints students list
void printStudentsList(studentList* list) {
    if(list == NULL) return;

    printf("StudentsList [\n");

    student* current_student = list->firstStudent;
    while(current_student != NULL) {
        current_student = printStudent(current_student);
    }

    printf("]\n");
}

int main(int argc, char** argv) {

  studentList* list = NULL;
  allocStudentsList(&list);

  // Create some student data
  student st1;
  st1.matrikelNummer = 1;

  // Another student...
  student st2;
  st2.matrikelNummer = 2;

  // Put them into the list (allocates students and take care of everything)
  addStudentToList(list, st1);
  addStudentToList(list, st2);

  // Print the list
  printStudentsList(list);

  // Free the list (recursively free's all students and take care of all the nasty stuff)
  freeStudentsList(list);

  return 0;
}

There are plenty of tutorials how to write C-style lists structures on the web. You can find one yourself.

One of the tutorial is there: Learn-c linked list tutorial

OP is not implementing a linked list, but a dynamic array. – moooeeeep Jan 10 '18 at 10:32 — moooeeeep, Jan 10 '18 at 10:32

score 0 · Answer 2 · answered Jan 09 '18 at 14:50

0

in your s_studentlist struct you have a pointer called students, you never used malloc on this member so its just a pointer to a random chunk in memory, allocate it the same way you did with your list variable

answered Jan 09 '18 at 14:50

zee

2,933
2
16
28

score 0 · Answer 3 · answered Jan 09 '18 at 14:57

you need to allocate memory for the student. When using malloc you only allocate memory for the list type, which includes a pointer to a student-type but not memory for the student type:

studentList* list = NULL;
list = (studentList*) malloc(sizeof(studentList));
list->students = (student*) malloc(sizeof(student));

Another Problem with you list is that I don't know how it is designed to work. A list normally contains a pointer to the next element:

typedef struct s_student {
    struct s_student* next;
    char name[64];
    int matrikelNummer; 
} student;

Another approach would be to store a list of students as an array in studentList, but hten you would need to allocate memory for more than one student:

list->students = (student*) malloc(list->numberOfStudents * sizeof(student));

This would be no list, but an array and you would access entries with

list->students[0].matrikelNummer

Implementing and using a dynamic array in C

3 Answers3

Not allocated pointers

Detection of invalid memory usage

Correct C list implementation