Dynamic 2D Array Implementation Using Linked Lists in C

Introduction

When trying to implement a 2D array dynamically in C, and you do not know the size until runtime, using a linked list is often a more flexible approach. This is because arrays in C require a fixed size known at compile time, whereas linked lists can grow and shrink as needed.

Handling Dynamically Sized Arrays

Let's consider a scenario where you want to read data from a file or user input and dynamically construct a 2D array without knowing the number of rows and columns in advance. This involves creating a structure to represent each row, which then forms a linked list. The linked list allows you to add new rows as needed, effectively creating a 2D structure on the fly.

Linked List Structure

Here’s the definition of the structure for each row:

struct row {    int numbers[40];    struct row *next;};

The structure contains an array of integers and a pointer to the next row in the list. The list is initialized to `NULL`, meaning there are no rows in the list initially.

Creating Rows in the List

To add a new row to the list, you need to:

Create a new row using `malloc`. Read in the column data. Check if the input is valid. Set the `next` pointer to `NULL`. Either set the new row as the head of the list if there are no existing rows, or append it to the end.

Here is the code snippet for creating rows in the list:

struct row *read_a_row(void) {    struct row *r  malloc(sizeof(struct row));    // read in the column data and store in r->numbers    // if readf fails or the input is invalid, return NULL    if (readf(r->numbers, sizeof(int) * 40, 1) ! 1) {        free(r);        return NULL; // Last row or bad data    }    // Since this is the end of the list, set r->next to NULL    r->next  NULL;    if (rows  NULL) { // If no data, set last and rows to this node        last  rows  r;    } else { // Put on the end        last->next  r;    }    last  r; // Set new last    return last; // Just in case you want to do something with it}

The `read_a_row` function dynamically reads and adds a new row to the list. This function is safe and ensures that the last row is up-to-date after each insertion.

Iterating Over the Linked List

Once you have constructed the linked list of rows, you can iterate over it to process each row. Here’s how you can do it:

while (read_a_row()) {    // Iterating over list    struct row *r  rows;    for (r  rows; r  rows; r  r-next) {        do_something_with_row(r);    }}

This loop reads data until no more rows can be added. Then, it iterates over the list and processes each row as needed.

Conclusion

By using a linked list to dynamically manage a 2D array, you can handle scenarios where the size is not known in advance. Instead of dealing with the complexities of dynamic 2D arrays, linked lists provide a simpler and more flexible solution.

Key Points

Dynamic Allocation: Linked lists allow for dynamic memory allocation, making them suitable for cases where the size of the data structures is not fixed. Flexibility: They can grow or shrink as needed, adapting to the amount of data being processed. Memory Management: With `malloc` and `free`, linked lists handle memory allocation and deallocation automatically.

References

Dynamically allocate 2D array in C

Dynamic array in C