> For the complete documentation index, see [llms.txt](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/24.-dinamicheskie-struktury-dannykh.-dvusvyaznye-spiski.-algoritmy-ikh-obrabotki..md).

# 24. Динамические структуры данных. Двусвязные списки. Алгоритмы их обработки.

**Динамические структуры данных** - составные структуры данных, динамически меняющие свой размер во время выполнения программы.

## Двусвязный список

**Двунаправленный (двусвязный) список** – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы. При этом два соседних элемента должны содержать взаимные ссылки друг на друга.

<figure><img src="/files/liOkB2bfEP4Pcyx69qYT" alt=""><figcaption></figcaption></figure>

<pre class="language-c"><code class="lang-c">typedef struct node{
    int value; // значение
    struct node* prev; // указатель на предыдущий элемент
<strong>    struct node* next; // указатель на следующий элемент
</strong>} node;
</code></pre>

`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 ):

<pre class="language-c"><code class="lang-c">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;
<strong>    } else {
</strong><strong>        new_node->prev = NULL;
</strong>        *list_ptr = new_node;
    }
}
</code></pre>

### Удаление элемента из начала списка c получением его значения(listPop):

<pre class="language-c"><code class="lang-c">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;
}
<strong>    else
</strong>        exit(-1);
}
</code></pre>

### Удаление элемента из конца списка с получением его значения                      (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);
}
```

#### Печать (просмотр) двунаправленного списка

Операция печати списка для двунаправленного списка реализуется абсолютно аналогично соответствующей функции для однонаправленного списка. Просматривать двунаправленный список можно в обоих направлениях.

<pre class="language-cpp"><code class="lang-cpp">//печать двунаправленного списка
void Print_Double_List(Double_List* Head) {
  if (Head != NULL) {
    cout &#x3C;&#x3C; Head->Data &#x3C;&#x3C; "\t";
    Print_Double_List(Head->Next);
    //переход к следующему элементу
  }
  else cout &#x3C;&#x3C; "\n";
}

<strong>//или
</strong>
void listPrint(node** list_ptr)
{
  for (node* current_node = *list_ptr; current_node != NULL; current_node =
<strong>    current_node->next)
</strong>      printf("%d\n", current_node->value);
}
</code></pre>

#### Вставка элемента в двунаправленный список

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

![Добавление элемента в двунаправленный список](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; 
}
```