# 24. Динамические структуры данных. Двусвязные списки. Алгоритмы их обработки. **Динамические структуры данных** - составные структуры данных, динамически меняющие свой размер во время выполнения программы. ## Двусвязный список **Двунаправленный (двусвязный) список** – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы. При этом два соседних элемента должны содержать взаимные ссылки друг на друга. 
typedef struct node{
    int value; // значение
    struct node* prev; // указатель на предыдущий элемент
    struct node* next; // указатель на следующий элемент
} node;
`type` – тип информационного поля элемента списка; `*next, *prev` – указатели на следующий и предыдущий элементы этой структуры соответственно. ```c struct node* list = malloc(sizeof(struct node)); list->value = 1; list->next = NULL; list->prev = NULL; ``` ## Основные операции * создание списка; * печать (просмотр) списка; * вставка элемента в список; * удаление элемента из списка; * поиск элемента в списке; * проверка пустоты списка; * удаление списка. #### :warning:Многие коды представлены на С++. Меняйте вывод и выделение памяти. ## Создание двунаправленного списка Для того, чтобы создать список, нужно создать сначала первый элемент списка, а затем при помощи функции добавить к нему остальные элементы. Добавление может выполняться как в начало, так и в конец списка. Реализуем рекурсивную функцию. ```cpp node* listInit(int value) { node* new_list = (node*)malloc(sizeof(node)); new_list->value = value; new_list->prev = NULL; new_list->next = NULL; return new_list; } ``` ### Добавление элемента в начало списка ( listPush ): ```c void listPush(node** list_ptr, int value) { node* new_node = (node*)malloc(sizeof(node)); new_node->value = value; new_node->prev = NULL; if (*list_ptr != NULL) (*list_ptr)->prev = new_node; new_node->next = *list_ptr; *list_ptr = new_node; } ``` ### Добавление элемента в конец списка ( listPushBack ): 
void listPushBack(node** list_ptr, int value){
    node* new_node = (node*)malloc(sizeof(node));
    new_node->value = value;
    new_node->next = NULL;
    
    if (*list_ptr != NULL) {
        node* last = *list_ptr;
        for(; last->next != NULL; last = last->next);
        
        last->next = new_node;
        new_node->prev = last;
    } else {
        new_node->prev = NULL;
        *list_ptr = new_node;
    }
}
### Удаление элемента из начала списка c получением его значения(listPop): 
int listPop(node** list_ptr)
{
    if (*list_ptr != NULL) {
        node* next = (*list_ptr)->next;
        int value = (*list_ptr)->value;
        
        free(*list_ptr);
        
        if (next != NULL)
            next->prev = NULL;
        *list_ptr = next;
        
        return value;
}
    else
        exit(-1);
}
### Удаление элемента из конца списка с получением его значения (listPopBack ): ```c int listPopBack(node** list_ptr) { if (*list_ptr != NULL) { node* last = *list_ptr; for(; last->next != NULL; last = last->next); node* prev = last->prev; int value = last->value; free(last); if (prev != NULL) prev->next = NULL; else *list_ptr = NULL; return value; } else exit(-1); } ``` #### Печать (просмотр) двунаправленного списка Операция печати списка для двунаправленного списка реализуется абсолютно аналогично соответствующей функции для однонаправленного списка. Просматривать двунаправленный список можно в обоих направлениях. 
//печать двунаправленного списка
void Print_Double_List(Double_List* Head) {
  if (Head != NULL) {
    cout << Head->Data << "\t";
    Print_Double_List(Head->Next);
    //переход к следующему элементу
  }
  else cout << "\n";
}

//или

void listPrint(node** list_ptr)
{
  for (node* current_node = *list_ptr; current_node != NULL; current_node =
    current_node->next)
      printf("%d\n", current_node->value);
}
#### Вставка элемента в двунаправленный список В динамические структуры легко добавлять элементы, так как для этого достаточно изменить значения адресных полей. Операция вставки реализовывается аналогично функции вставки для однонаправленного списка, только с учетом особенностей двунаправленного списка ![Добавление элемента в двунаправленный список](https://intuit.ru/EDI/28_11_18_2/1543357168-6234/tutorial/909/objects/29/files/29_05.png) ```cpp //вставка элемента с заданным номером в двунаправленный список Double_List* Insert_Item_Double_List(Double_List* Head, int Number, int DataItem){ Number--; Double_List *NewItem=new(Double_List); NewItem->Data=DataItem; NewItem->Prior=NULL; NewItem->Next = NULL; if (Head == NULL) {//список пуст Head = NewItem; } else {//список не пуст Double_List *Current=Head; for(int i=1; i < Number && Current->Next!=NULL; i++) Current=Current->Next; if (Number == 0){ //вставляем новый элемент на первое место NewItem->Next = Head; Head->Prior = NewItem; Head = NewItem; } else {//вставляем новый элемент на непервое место if (Current->Next != NULL) Current->Next->Prior = NewItem; NewItem->Next = Current->Next; Current->Next = NewItem; NewItem->Prior = Current; Current = NewItem; } } return Head; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/24.-dinamicheskie-struktury-dannykh.-dvusvyaznye-spiski.-algoritmy-ikh-obrabotki..md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.