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

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

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

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

typedef struct node{
    int value; // значение
    struct node* prev; // указатель на предыдущий элемент
    struct node* next; // указатель на следующий элемент
} node;

type – тип информационного поля элемента списка;

*next, *prev – указатели на следующий и предыдущий элементы этой структуры соответственно.

struct node* list = malloc(sizeof(struct node));
list->value = 1;
list->next = NULL;
list->prev = NULL;

Основные операции

• создание списка;

• печать (просмотр) списка;

• вставка элемента в список;

• удаление элемента из списка;

• поиск элемента в списке;

• проверка пустоты списка;

• удаление списка.

⚠️Многие коды представлены на С++. Меняйте вывод и выделение памяти.

Создание двунаправленного списка

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

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

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

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);
}

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

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

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

//вставка элемента с заданным номером в двунаправленный список
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; 
}