:::: MENU ::::

Связанные списки (linked lists)

Часто при программирование необходимо выполнять действия над связанными списками — обычно в них присутствует добавление и удаление элементов, поиск первого и последнего элемента. Простая реализация работы со списками приведена далее:

Ниже код для двунаправленного связанного списка, последний и первый элементы, которого указывают сами на себя.

typedef struct _link_init
{
   struct _link_init * prev;
   struct _link_init * next;
} link_init;

Инициализация и добавление первого элемента в связанный список.

void init_queue_first_el(link_init *link)
{
        link->prev = link;      
        link->next = link;
}

Сброс связанного списка. Проход по всем элементам и сброс следующего и предыдущего элемента (указывает сам на себя).

void reset_queue(link_init *link)
{
    link_init *temp_link;

    temp_link = find_first_el_que(link);

    while((*temp_link).next != temp_link)
    {
        temp_link->prev = temp_link;        
        temp_link = temp_link->next;
        (temp_link->prev)->next =  temp_link->prev;
    }       
}

Поиск первого элемента связанного списка (признак 1-го элемента — указывает сам на себя как предыдущий элемент).

link_init* find_first_el_que(link_init *link)
{
    link_init *temp_link;

    temp_link = link;
    while((*temp_link).prev != temp_link)
        temp_link = temp_link->prev;

    return(temp_link);
}

Поиск последнего элемента связанного списка (признак последнего элемента — указывает сам на себя как следующий элемент).

link_init* find_end_el_que(link_init *link)
{
    link_init *temp_link;

    temp_link = link;
    while((*temp_link).next != temp_link)
        temp_link = temp_link->next;

    return(temp_link);
}

Добавление нового элемента в конец связанного списка.

void add_el_to_end_que(link_init *que, link_init *link)
{
    link_init *temp_link;

    temp_link = find_end_el_que(que);

    temp_link->next = link;
    link->prev = temp_link;
    link->next = link;
}

Добавление нового элемента в начало связанного списка.

void add_el_to_begin_que(link_init *que, link_init *link)
{
    link_init *temp_link;

    temp_link = find_first_el_que(que);

    temp_link->prev = link;
    link->prev = link;
    link->next = temp_link;
}

Пример:

link_init que_1;
link_init que_2;
link_init que_3;
link_init que_4;
link_init que_5;

init_queue_first_el(&que_1);

add_el_to_end_que(&que_1, &que_2);
add_el_to_end_que(&que_2, &que_3);
add_el_to_end_que(&que_1, &que_4);
add_el_to_end_que(&que_4, &que_5);

reset_queue(&que_2);