При подготовке к сертификации я решил заготовить «бомбы» какие-то стандартные  не сложные вещи, которые скорей всего пригодятся мне во время решения теста и на которые не хотелось бы тратить время. И первое с чего я бы хотел начать это односвязный список. Односвязный список будет очень полезен для реализации обхода дерева как в глубину, так и в ширину, точней он необходима для итеративной реализации, потому что на нем можно реализовать как стек, так и очередь.

Немного информации из википедии:

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.^[1]Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера^[2], а порядок обхода списка всегда явно задаётся его внутренними связями.

 

 

/* Определяем элемент списка */
typedef struct list_node {
    struct list_node *next;
    void *data;
} list_node_t;

/* Определяем сам список */
typedef struct list {
    /* 
     * Размер списка хранить не обязательно, 
     * он нужен для упрощения работы 
     */
    int size;
    /* начало списка */
    list_node_t *head;
    /* конец списка */
    list_node_t *tail;
} list_t;

/* Инициализация массива */
list_t * create_list(void)
{
    list_t *lt = malloc(sizeof(list_t));

    lt->size = 0;
    lt->head = NULL;
    lt->tail = lt->head;

    return lt;
}

/* Добавляем элемент в начало списка */
void list_push(list_t *lt, void * data)
{
    list_node_t * node = malloc(sizeof(list_node_t));
    node->data = data;
    node->next = lt->head;

    lt->head = node;
    lt->size += 1;
}

/* Извлекаем элемент из начала списка */
void * list_pop(list_t *lt)
{
    if(lt->size == 0){
        /* Список пуст */
        return NULL;
    }

    list_node_t *node = lt->head;
    void * ret_val = node->data;

    lt->size -= 1;
    lt->head = node->next;

    free(node);

    if(lt->size == 0){
        /* Это был последний элемент */
        lt->head = NULL;
        lt->tail = NULL;
    }

    return ret_val;
}

/* Добавляем элемент в конец списка */
void list_push_back(list_t *lt, void * data)
{
    list_node_t * node = malloc(sizeof(list_node_t));
    node->data = data;
    if(lt->tail != NULL)
        lt->tail->next = node;
    else {
        lt->head = node;
    }

    lt->tail = node;
    lt->size += 1;
}

Теперь можно использовать этот список и как очередь и как стек.

Пример использования как стек:

list_t *st = create_list();
int data = 0, *ptr;

/* Добавляем в начало списка */
list_push(st, &data);
/* Извлекаем из начала списка*/
ptr = (int *)list_pop(st);

А вот пример использования как очереди:

list_t *queue = create_list();
int data = 0, *ptr;

/* Добавляем в конец списка */
list_push_back(queue, &data);
/* Извлекаем из начала списка*/
ptr = (int *)list_pop(queue);