Lesson 15

Memory Allocation

• We normally use void pointer (void *) to be able to pass data around as function parameters

• Void pointer is not a pointer to nothing, it’s a pointer to void.

• We also use size_t which is an unsigned integer to represent data sizes as parameters

• We have 4 functions, 3 of which allocate memory:

  • void *malloc(size_t size); allocates size amount of memory for the program

    • void * is to allow developers determine the type of data we are passing

    • size_t size is the size in bytes

  • void *calloc(size_t nitems, size_t size); clears and allocates nitems of a specific size returning a void *

    • void * is to allow developers determine the type of data we are passing

    • size_t nitems is to determine the number of items to

    • size_t size

  • int realloc(void * ptr, size_t nitems); changes the size of a specific pointer.

    • void * ptr the pointer already initialized

    • size_t nitems is the new number of elements assigned to a specific

  • free(void * ptr); frees a pointer’s memory

    • void * ptr the pointer to free.

Dynamic Data Structures

• These are self referential dynamic data structures:

  • Linked Lists

  • Stacks

  • Queues

  • Binary Trees

    #include <stdio.h>

    typedef struct node node;
    struct node {
        int value;
        node *next;
    };

    int main(int argc, char *argv[]) {
        node n4 = {4, 0};
        node n3 = {20, &n4};
        node n2 = {2, &n3};
        node n1 = {1, &n2};

        /* OR */
        node *n4 = malloc();

        return 0;
    }

Linked List

• It’s a linear data structure

  • Head → Node1 → Node2 → 0

• Its main structure is a node

• It’s accessed via pointer to its first node

• First pointer is 0 if the list is empty

• Each subsequent node gets access via pointer on its predecessor

• We can traverse the linked list using the single pointer traversal idiom when doing operations that do not require changing the head

    // ... data setup
    for (node *current = head; head != 0; current = current->head ){
        // logic
    }
  

• We can traverse the linked list using the double pointer traversal idiom when doing operations that require changing the head

    node **tracer;
    for(tracer = phead; *tracer != 0; tracer = &(*tracer)->next) {
        // logic
    }
  

• Destroying a link list, we have to destroy each referenced node - in this case we cannot use current after freeing a node so we need to introduce an additional variable.

    // ... data setup
    node *current, *next;
    for(current = head; current != 0; current = next) {
        next = current->next;
        free(current);
    }
  

Exercises i’ve done with linked list

#ifndef LL_FLAG

#define LL_FLAG

typedef struct inode inode;
struct inode {
    int value;
    inode *next;
};

/**
 * Prints all elements in a linked list
 */
void print_ill(const inode* head);

/**
 * Creates a new node and sets it as
 * the head of the link list. Returns
 * 1 if it was successful, 0 otherwise.
 */
int append(inode** phead, int value);

/**
 * Creates a new node and adds it to the
 * end of the link list. Returns
 * 1 if it was successful, 0 otherwise.
 */
int prepend(inode* head, int value);

/**
 * Creates a new node and adds it
 * ensuring the link list is sorted
 * ascendingly (from lowest to largest)
 * Returns 1 if successful, 0 otherwise
 */
int add_asc_sorted(inode ** phead, int value);

/**
 * Creates a new node and adds it
 * ensuring the link list is sorted
 * descendingly (from largest to lowest)
 * Returns 1 if successful, 0 otherwise
 */
int add_desc_sorted(inode ** phead, int value);

/**
 * Removes the first node found with a specific
 * value.
 */
void remove_one_by_val(inode ** phead, int value);

#endif

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

void print_ill(const inode* head) {
    for (const inode *current = head; current != 0; current = current->next) {
        printf("%d", current->value);

        if(current->next != 0) {
            printf(" -> ");
        }
    }
    printf("\n");
}

int append(inode** phead, int value) {
    inode* new_node = malloc(sizeof(inode));
    if (new_node == 0) {
        return 0;
    }

    new_node->value = value;
    new_node->next = *phead;
    *phead = new_node;
    return 1;
}

int prepend(inode* head, int value) {

    inode* new_node = malloc(sizeof(inode));
    if (new_node == 0) {
        return 0;
    }
    new_node->value = value;
    new_node->next = 0;

    for (inode* current = head; current != 0; current = current->next) {
        if (current->next == 0) {
            current->next = new_node;
            break;
        }
    }

    return 1;
}

int add_asc_sorted(inode ** phead, int value) {
    inode **tracer;
    inode* new_node = malloc(sizeof(inode));
    if (new_node == 0) {
        return 0;
    }
    new_node->value = value;
    new_node->next = 0;

    for (tracer = phead; *tracer != 0; tracer = &(*tracer)->next) {
        if (value <= (*tracer)->value) {
            break;
        }
    }

    new_node->next = *tracer;
    *tracer = new_node;

    return 1;
}

int add_desc_sorted(inode ** phead, int value) {

    inode * new_node = malloc(sizeof(inode));
    if (new_node == 0) {
        return 0;
    }

    inode **tracer;
    for (tracer = phead; *tracer != 0; tracer = &(*tracer)->next) {
        if (value <= (*tracer)->value) {
            break;
        }
    }

    new_node->next = *tracer;
    *tracer = new_node;

    return 1;
}

void remove_one_by_val(inode ** phead, int value) {
    inode **tracer;

    for(tracer = phead; *tracer != 0; tracer = &(*tracer)->next) {
        if ((*tracer)->value == value) {
            break;
        }
    }
    inode *tmp = *tracer;
    *tracer = tmp->next;
    free(tmp);
}