Data Structures in C

Arrays

An array is a homogeneous collection of data stored in a contiguous segment of memory.

The array’s name, in most expressions, automatically converts (“decays”) to a pointer to its first element of type T *. This is because all that such as assignment will do is pass around pointers: C deems this unsafe.

Note: Arrays themselves are not assignable: int a[5], b[5]; a = b; is illegal, but copying via memcpy or loops is fine. Instead, we need to copy all the elements of one array into another.

Here is example code that illustrates how we can initializing arrays:

int a[5] = {1,2,3,4,5};

If we initialize the array at the same time we declare it, we can choose to omit the number of elements in the array. So in the above example int a[] = {1,2,3,4,5}; will be equally acceptable.

Note that it is also possible to initialize less elements in the array initialization than declared in the array. It is just the other way that is not allowed. Here is an example:

int a[5] = {1,4}; // Only the first two elements are initialised. The rest are not the same.

If you partially initialize an array, remaining elements are zeroed. So in the above example, the array will be \({1,4,0,0,0}\).

The most important property of arrays in C is the Array–to–pointer conversion. Mastering this is required to deal with arrays effectively. Here is a more detailed exploration of this important subject: Pointer Arithmetic. Also refer to Hence, although the array variable behaves like a pointer, it is not a pointer. Consider two variables s and t in the code below. We will compare their behaviour:.

To really master arrays in C, practice these patterns:

• Always pass array length explicitly, unless using a fixed‑size array parameter (int (*a)[N]) or VLA parameters.
• Use sizeof only on arrays in the same scope, never on “array parameters” or generic pointers.
• Distinguish carefully between:
  • T *p; (pointer)
  • T a[N]; (array)
  • T (*p)[N]; (pointer to array)
  • T *a[M]; (array of pointers)
• Use structs with embedded arrays or flexible array members for more complex buffer‑carrying abstractions.

Multidimensional Arrays

C’s multi‑dimensional arrays are arrays of arrays, stored in row‑major order.

int m[2][3] = { {1,2,3}, {4,5,6} };  // 2 rows, 3 columns [web:7]
int (*row)[3] = m;                   // pointer to array of 3 int
int *flat = &m[0][0];                // pointer to first int

Key details:

• m decays to int (*)[3], a pointer to an array of 3 int.
• m[i] has type int[3] and decays to int * when used as an expression; your function parameters must match these types exactly.

Now you might be confused about what the int (*row) is talking about. To clarify that, here is a differentiation between array and pointers in declarations.

• int *a[10]; is an array of 10 pointers to int.
• int (*a)[10]; is a pointer to an array of 10 int.

Strings

C is more low-level than most other languages, so instead of strings, it normally uses something similar: an array of single characters. However, there are a number of C extensions that do give you strings.

Note that strings are enclosed in double quotes while characters are enclosed in single quotes.

Each of the characters in the string is just an element in an array, which is why you can refer to the individual characters in the string by using an index, like s[0] and s[1].

Now, we go more in depth into how the exact representation of a string looks like in memory because this defined properties of how the contents of a string can be read:

Storing strings

Now, in a lot of languages, the computer keeps pretty close track of the size of an array, but C is more low-level than most languages and can’t always work out exactly how long an array is.

If C is going to display a string on the screen, it needs to know when it gets to the end of the character array. And it does this by adding a sentinel character.

This is what differentiates a string from a normal array of characters.

The following examples exemplifies how a string is stored in memory:

s = "Shatner" // Equivalently:
s = {'S', 'h', 'a', 'n', 't', 'e', 'r'};

The sentinel character is an additional character at the end of the string that has the value \0 (ASCII character with value 0).

Note that if you perform string manipulations then you need to add the null terminator at the end manually so that C still treats the list of characters as a string.

As a result, if we want to store n characters in a string, we define a character array with length n+1.

It is possible to store an array of strings in C as follows. Here, we know that each string has a maximum length of 79 characters:

char tracks[][80] = {
"I left my heart in Harvard Med School",
"Newark, Newark - a wonderful town",
"Dancing with a Dork",
"From here to maternity",
"The girl from Iwo Jima",
};

There is another approach that can be used to store an array of strings. This is storing an array of pointers. This is a list of memory addresses stored in an array. It’s very useful if you want to quickly create a list of string literals. Here is how we can define one:

char *names_for_dog[] = {"Bowser", "Bonza", "Snodgrass"};

String Literals

Note however that you don’t need to define strings as arrays of characters. You can define them using quotes which will lead to a string literal.

However, string literals are immutable. They are stored in a read-only section of memory.

The string literal is stored in the segment of memory for read only information. Only the pointer is stored on the heap.

If you try to change individual characters once they are created, there will typically be a bus error which means that the program cannot update that piece of memory.

char *cards = "JQK"; // This is a string literal
cards[1] = cards[2];

This for example will result in a bus error. This is why when using declarations of the format char *chars = ... it is advisable to put const in front so that a compilation error is produced instead of a failure at runtime.

To fix it, the following change can be made:

char cards[] = "JQK"; // Even if this is a very minor change, this is not a string literal anymore
cards[1] = cards[2];

This works because now cards is an array.

If you declare an array called cards and then set it to a string literal, the cards array will be a completely new copy. The variable isn’t just pointing at the string literal in the read only memory segment. It’s a brand-new array that contains a fresh copy of the string literal.

Note: You still need to be careful about cases where the array decays to a pointer.

Structures

Structures allows the grouping of heterogeneous members in one data type. Unlike an array, a structure can contain many different data types (int, float, char, etc.).

Each variable in the structure is known as a member of the structure. The grouping of data is called a structure type.

You can create a structure by using the struct keyword and declare each of its members inside curly braces.

Definition

In C, when defining a structure, you typically need to use the struct keyword every time you declare a variable. typedef allows you to create a shorthand for the structure type, eliminating the need for the struct keyword. 

// Without typedef
struct Student {
    char name[50];
    int id;
};
struct Student s1; // Must use 'struct Student'

// With typedef
typedef struct {
    char name[50];
    int id;
} Student;
Student s2; // Can use 'Student' directly

To access the structure, you must create a variable of it. This is because a data type is not a variable: however, we can create a variable of a data type.

Initialisation

Here is how we declare and initialise structure variables:

struct Person {
    char name[50];
    int age;
    float height;
};

struct Person person1 = {"Alice", 30, 5.9};
// Alternatively, we can do this:
struct Person person2 = { .age = 25, .name = "Bob", .height = 6.1 };
// If we only have some data:
struct Person person3 = { .age = 40 }; // name and height are zero-initialized

There are different ways in which initialisation can be done as illustrated above.

Access

After declaring the variable, you can assign values to members individually using the member access operator (.). This is done inside a function.

struct Person person4;
person4.age = 22;
person4.height = 5.8;

If we use a structure variable’s name, we are referring to the entire structure. Unlike arrays, we may do assignments with structures:

person2 = person1;

This sets all the properties of person2 to the corresponding properties of person1.

This means that structures are pass by value. They are not like arrays which are pass by reference. Thus, be careful when trying to modify a struct within a function. Here is an example of how this can be done:

// 1. Define the structure
struct Person {
    char name[50];
    int age;
};

// 2. Declare a function that accepts a pointer to the structure
void update_person_age(struct Person *person_ptr) {
    // 3. Access members using the arrow operator (->)
    person_ptr->age = 30;
    // The arrow operator is a shorthand for (*person_ptr).age.
}

Note that we need to do two things to modify values of a struct:

• Dereference the struct (done using *person_ptr)
• Reference the elements using the dot notation (*person_ptr.age)

However, we need to be very careful with this because the priority of the dot notation is higher than the de-reference operator so we cannot write *person_ptr.age. This would throw an error because the pointer is not struct.

To avoid the confusion, C introduces syntactic sugar where we can write person_ptr->age instead, significantly simplifying the referencing code.

Storage

When you create a struct in C, the compiler may add some extra bytes of padding between members.

This is done to make the program run faster on your computer, because most CPUs read data more efficiently when it's properly aligned in memory.

Let's look at a simple struct:

struct Example {
  char a; // 1 byte
  int b;  // 4 bytes
  char c; // 1 byte
};

int main() {
  printf("Size of struct: %zu bytes\n", sizeof(struct Example));
  return 0;
}

You might expect the size to be 1 + 4 + 1 = 6 bytes - but it will usually print 12 bytes! The compiler adds padding bytes so that the int member (b) starts at a memory address that's a multiple of 4. This helps the CPU read it faster.

Here's how memory is actually arranged:

Total = 1 + 3 + 4 + 1 + 3 = 12 bytes.

The most portable way to minimize padding is to list struct members from largest to smallest. This allows smaller types to fill the alignment gaps left by larger ones. 

• Inefficient Order: char a; int b; char c; (often 12 bytes because of gaps after each char).
• Optimized Order: int b; char a; char c; (often 8 bytes because a and c fit together after b).