index<--

C Collections

Collections in C are data structures that group multiple values together. Unlike some higher-level languages, C doesn't have built-in "collections" but relies on fundamental types like arrays and structs, along with pointers, to build more complex data structures.

Linked Lists
Dynamic Arrays

Linked Lists

A linked list is a fundamental dynamic data structure where elements are not stored in contiguous memory locations. Instead, each element (a "node") contains a value and a pointer to the next node in the sequence. Some lists have also a pointer to previous element. A list has first element (head) and last element (tail). You can add elements at the beginning, at the end or insert new elements with the same speed.

Linked List

Anatomy of a Node:


struct Node {
    int data;
    struct Node* next; // Pointer to the next node
};

Example:

This example demonstrates how to create a simple singly linked list with three nodes.


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

struct Node {
    int data;
    struct Node* next;
};

int main() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    second->data = 2;
    second->next = NULL;
    head->next = second; // Link the first node to the second

    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    third->data = 3;
    third->next = NULL;
    second->next = third; // Link the second node to the third

    // Traverse and print the list
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    // Clean up memory
    free(head);
    free(second);
    free(third);
    
    return 0;
}

Expected Output:

1 -> 2 -> 3 -> NULL

Note:

Access of the element is in sequence, from tail to head or from head to tail. Therefore access of elements in large lists is considered slow. For better performance developers preffer binary tree, that has better performance.

Dynamic Arrays

Unlike C's built-in static arrays, you can create dynamic arrays using pointers and memory allocation functions like malloc() and realloc(). This allows the array's size to be determined at runtime and resized as needed.

Array Elements

Example:

We'll create a dynamic array, add elements, and then resize it using realloc().


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

int main() {
    int initial_size = 3;
    int* dynamic_array = (int*)malloc(initial_size * sizeof(int));

    if (dynamic_array == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }

    // Initialize elements
    for (int i = 0; i < initial_size; i++) {
        dynamic_array[i] = (i + 1) * 10;
    }

    // Print initial array
    printf("Initial array: ");
    for (int i = 0; i < initial_size; i++) {
        printf("%d ", dynamic_array[i]);
    }
    printf("\n");

    // Resize the array to a new size
    int new_size = 5;
    dynamic_array = (int*)realloc(dynamic_array, new_size * sizeof(int));
    if (dynamic_array == NULL) {
        printf("Memory reallocation failed!\n");
        return 1;
    }

    // Add new elements
    dynamic_array[3] = 40;
    dynamic_array[4] = 50;

    // Print resized array
    printf("Resized array: ");
    for (int i = 0; i < new_size; i++) {
        printf("%d ", dynamic_array[i]);
    }
    printf("\n");

    // Clean up memory
    free(dynamic_array);
    
    return 0;
}

Access to array elements is faster than the access of linked-list elements. The oroblem is you need the element index for this, and if you want to search by value stored for element, you have to access all elements from the beginning until you find the value you are looking for.

Expected Output:

Initial array: 10 20 30 
Resized array: 10 20 30 40 50

Return: Index