Динамические структуры данных: Списковые структуры как основа эффективного управления памятью и алгоритмов

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

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

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

Теоретические основы динамических структур данных

Определение и основные характеристики динамических структур данных

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

Ключевые характеристики, отличающие динамические структуры:

• Изменяемый размер: Они могут менять не только количество элементов, но и характер связей между ними. Это означает, что их размерность не фиксируется заранее и может динамически расширяться или сужаться.
• Отсутствие физической смежности: Элементы динамических структур не обязательно располагаются в последовательных ячейках памяти. Доступ к ним осуществляется не по индексу, а по указателю — адресу их текущего расположения. Это позволяет эффективно использовать фрагментированную память и избегать дорогостоящих операций по сдвигу данных при вставке или удалении.
• Управление через указатели: Поскольку элементы могут быть разбросаны по памяти, каждый элемент (или узел) содержит не только свои данные, но и один или несколько указателей, ссылающихся на другие элементы структуры. Это формирует логическую связь между элементами, которая не зависит от их физического расположения.

Преимущества динамических структур:

• Гибкость: Их размер ограничивается только доступным объемом оперативной памяти, что делает их идеальными для работы с данными, объем которых заранее неизвестен или сильно меняется.
• Эффективное использование памяти: Они позволяют использовать память более рационально, выделяя ровно столько, сколько требуется в данный момент, без резервирования избыточных объемов.
• Простота модификации: При изменении логической последовательности элементов (например, при вставке или удалении) часто достаточно лишь скорректировать указатели, не перемещая сами данные, что значительно быстрее, чем в статических массивах.

Недостатки динамических структур:

• Накладные расходы на указатели: Каждый элемент, помимо полезных данных, должен хранить указатели, что требует дополнительной памяти. На 32-разрядных системах указатель обычно занимает 4 байта, а на 64-разрядных системах — 8 байт.
• Менее эффективный доступ по времени: Доступ к произвольному элементу динамической структуры часто требует последовательного обхода по указателям, что может быть медленнее, чем прямой доступ по индексу в массиве (O(n) против O(1)).
• Сложность управления памятью: Неправильное управление динамически выделяемой памятью может привести к серьезным проблемам, таким как «утечки памяти» или «фрагментация».

Классификация динамических структур данных

Мир динамических структур данных удивительно разнообразен, словно экосистема, где каждый вид занимает свою нишу и адаптирован для решения определенных задач. Их классификация основывается на двух основных критериях: способе связи отдельных элементов и наборе допустимых операций, которые можно над ними выполнять. Эта классификация помогает ориентироваться в многообразии инструментов и выбирать наиболее подходящий для конкретной задачи.

Основные категории динамических структур данных включают:

• Линейные структуры: Элементы расположены в последовательности, где каждый элемент имеет одного или двух «соседей».
  • Списки: Это универсальные структуры, элементы которых образуют цепочку. Каждый узел содержит данные и ссылки на другие узлы. Списки могут быть:
    • Однонаправленные (односвязные): Каждый узел указывает только на следующий.
    • Двунаправленные (двусвязные): Каждый узел указывает как на следующий, так и на предыдущий.
    • Циклические (кольцевые): Последний узел указывает на первый, образуя замкнутый круг. Они также могут быть односвязными или двусвязными.
  • Стек (Stack): Линейная структура, работающая по принципу LIFO (Last In, First Out – «последним пришел, первым ушел»). Представьте стопку тарелок: чтобы взять нижнюю, нужно снять все верхние.
  • Очередь (Queue): Линейная структура, работающая по принципу FIFO (First In, First Out – «первым пришел, первым ушел»). Это как очередь в магазине: кто первый встал, тот первый и обслуживается.
  • Дек (Deque – Double-ended Queue): Двусторонняя очередь, позволяющая добавлять и удалять элементы как с начала, так и с конца.
• Нелинейные структуры: Элементы могут иметь более двух связей или сложную иерархическую структуру.
  • Деревья: Иерархические структуры, состоящие из узлов, связанных между собой. У каждого узла есть родитель (кроме корневого) и может быть несколько потомков. Наиболее распространены бинарные деревья, где у каждого узла не более двух потомков.
  • Графы: Наиболее общие структуры, состоящие из вершин (узлов) и ребер (связей) между ними. Графы могут быть ориентированными (связи имеют направление) и неориентированными.

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

Списковые структуры данных: принципы организации и базовые операции

Однонаправленные (односвязные) списки

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

Однонаправленный (односвязный) список — это последовательность элементов, называемых узлами (или компонентами), каждый из которых состоит как минимум из двух полей:

1. Информационное поле (поле данных): Здесь хранится собственно полезная информация (значение, ключ, объект), которую мы хотим сохранить в списке. Ключ обычно является уникальным идентификатором элемента, будь то целое число, строка или более сложная структура.
2. Адресное поле (указатель): Это ссылка (указатель) на следующий элемент в последовательности. Именно этот указатель обеспечивает логическую связь между узлами, даже если они физически разбросаны в памяти.

Ключевым аспектом организации однонаправленного списка является то, что последний элемент в последовательности имеет указатель на следующий элемент, равный NULL (или nullptr, nil в зависимости от языка программирования). Это значение служит маркером конца списка. Для доступа ко всему списку мы храним указатель на его первый элемент (так называемый «головной» или head). Если этот указатель равен NULL, это означает, что список пуст.

Визуальная схема организации однонаправленного списка

Ниже представлена схематическая иллюстрация однонаправленного списка, состоящего из трех элементов:

+------------+     +------------+     +------------+
|  Данные 1  |     |  Данные 2  |     |  Данные 3  |
|  Next ---->|---->|  Next ---->|---->|  Next ---->|----> NULL
+------------+     +------------+     +------------+
  ^
  |
 HEAD (указатель на первый элемент)

Каждый прямоугольник представляет собой узел, стрелка Next символизирует указатель на следующий узел. HEAD — это указатель, который всегда указывает на начало списка.

Основные операции с однонаправленными списками и их алгоритмы

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

1. Создание списка (CreateList)
   • Описание: Инициализирует пустой список, устанавливая указатель HEAD в NULL.
   • Псевдокод:

     FUNCTION CreateList()
         HEAD = NULL
         RETURN HEAD
     END FUNCTION
     

2. Проверка пустоты списка (IsEmpty)
   • Описание: Определяет, содержит ли список элементы.
   • Псевдокод:

     FUNCTION IsEmpty(HEAD)
         IF HEAD == NULL THEN
             RETURN TRUE
         ELSE
             RETURN FALSE
         END IF
     END FUNCTION
     

3. Вставка элемента в начало списка (InsertAtBeginning)
   • Описание: Создает новый узел и делает его первым элементом списка.
   • Псевдокод:

     FUNCTION InsertAtBeginning(HEAD, value)
         newNode = CreateNode(value)
         newNode.Next = HEAD
         HEAD = newNode
         RETURN HEAD
     END FUNCTION
     

     *Здесь CreateNode(value) создает новый узел с заданным значением и Next = NULL.*

4. Вставка элемента в конец списка (InsertAtEnd)
   • Описание: Добавляет новый узел в конец списка. Требует обхода списка.
   • Псевдокод:

     FUNCTION InsertAtEnd(HEAD, value)
         newNode = CreateNode(value)
         IF HEAD == NULL THEN
             HEAD = newNode
             RETURN HEAD
         END IF
         current = HEAD
         WHILE current.Next != NULL DO
             current = current.Next
         END WHILE
         current.Next = newNode
         RETURN HEAD
     END FUNCTION
     

5. Вставка элемента после заданного (InsertAfter)
   • Описание: Вставляет новый узел после узла с определенным значением или указателем. Для этого нужно выбрать узел, после которого следует сделать вставку, сохранить значение его указателя на следующий узел, присвоить указатель на следующий узел у выбранного адресу вставляемого узла, и присвоить указатель на следующий узел у вставляемого сохраненному значению.
   • Псевдокод:

     FUNCTION InsertAfter(HEAD, targetValue, value)
         current = HEAD
         WHILE current != NULL AND current.Data != targetValue DO
             current = current.Next
         END WHILE
         IF current != NULL THEN
             newNode = CreateNode(value)
             newNode.Next = current.Next
             current.Next = newNode
         ELSE
             // Элемент targetValue не найден
             PRINT "Элемент для вставки не найден."
         END IF
         RETURN HEAD
     END FUNCTION
     

6. Удаление элемента из начала списка (DeleteFromBeginning)
   • Описание: Удаляет первый элемент списка.
   • Псевдокод:

     FUNCTION DeleteFromBeginning(HEAD)
         IF HEAD == NULL THEN
             PRINT "Список пуст."
             RETURN NULL
         END IF
         temp = HEAD
         HEAD = HEAD.Next
         FreeNode(temp) // Освободить память
         RETURN HEAD
     END FUNCTION
     

7. Удаление элемента по значению (DeleteByValue)
   • Описание: Удаляет первый найденный элемент с заданным значением. Требует обхода списка для нахождения предыдущего элемента.
   • Псевдокод:

     FUNCTION DeleteByValue(HEAD, value)
         IF HEAD == NULL THEN
             PRINT "Список пуст."
             RETURN NULL
         END IF
         IF HEAD.Data == value THEN
             temp = HEAD
             HEAD = HEAD.Next
             FreeNode(temp)
             RETURN HEAD
         END IF
         current = HEAD
         WHILE current.Next != NULL AND current.Next.Data != value DO
             current = current.Next
         END WHILE
         IF current.Next != NULL THEN
             temp = current.Next
             current.Next = temp.Next
             FreeNode(temp)
         ELSE
             PRINT "Элемент не найден."
         END IF
         RETURN HEAD
     END FUNCTION
     

8. Поиск элемента (Search)
   • Описание: Ищет элемент с заданным значением и возвращает указатель на него (или NULL, если не найден).
   • Псевдокод:

     FUNCTION Search(HEAD, value)
         current = HEAD
         WHILE current != NULL AND current.Data != value DO
             current = current.Next
         END WHILE
         RETURN current // Вернет NULL, если элемент не найден
     END FUNCTION
     

9. Обход (печать) списка (PrintList)
   • Описание: Проходит по всем элементам списка и выводит их значения.
   • Псевдокод:

     FUNCTION PrintList(HEAD)
         current = HEAD
         IF current == NULL THEN
             PRINT "Список пуст."
             RETURN
         END IF
         WHILE current != NULL DO
             PRINT current.Data
             current = current.Next
         END WHILE
     END FUNCTION
     

10. Удаление всего списка (DeleteList)
    • Описание: Освобождает память, занимаемую всеми узлами списка.
    • Псевдокод:

      FUNCTION DeleteList(HEAD)
          current = HEAD
          WHILE current != NULL DO
              temp = current
              current = current.Next
              FreeNode(temp) // Освободить память для текущего узла
          END WHILE
          HEAD = NULL
          RETURN HEAD
      END FUNCTION
      

Двунаправленные (двусвязные) списки

Однонаправленный список, подобно дороге с односторонним движением, позволяет двигаться только вперед. Однако во многих сценариях требуется возможность перемещаться по данным в обоих направлениях. Здесь на сцену выходит двунаправленный (двусвязный) список — более гибкая, но и более сложная структура.

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

1. Next (или Fwd): Указатель на следующий элемент в последовательности.
2. Prior (или Prev, Bwd): Указатель на предыдущий элемент в последовательности.

Ключевая особенность двунаправленного списка заключается в том, что два соседних элемента должны содержать взаимные ссылки друг на друга. То есть, если узел A указывает на узел B как на следующий (A.Next = B), то узел B должен указывать на узел A как на предыдущий (B.Prior = A).

Как и в однонаправленном списке, маркеры конца и начала играют важную роль:

• У последнего узла указатель Next содержит значение NULL.
• У первого узла указатель Prior содержит значение NULL.

Для удобства работы с двунаправленным списком часто используются два указателя: HEAD (или first), указывающий на первый элемент, и TAIL (или last), указывающий на последний элемент.

Визуальная схема организации двунаправленного списка

Ниже представлена схематическая иллюстрация двунаправленного списка, состоящего из трех элементов:

      NULL <----Prior----   +------------+   ----Next----> +------------+   ----Next----> +------------+   ----Next----> NULL
HEAD ----->   +------------+ <----Prior----   +------------+ <----Prior----   +------------+ <----Prior----
              |  Данные 1  |                 |  Данные 2  |                 |  Данные 3  |
              | Next ----> |<----------------| Next ----> |<----------------| Next ----> |<----------------
              | Prior <----|---------------->| Prior <----|---------------->| Prior <----|
              +------------+                 +------------+                 +------------+
                                                                                               ^
                                                                                               |
                                                                                           TAIL (указатель на последний элемент)

Каждый прямоугольник — это узел. Стрелки Next и Prior обозначают указатели на следующий и предыдущий узлы соответственно. Обратите внимание на взаимные связи. HEAD и TAIL указывают на первый и последний элементы.

Основные операции с двунаправленными списками и их алгоритмы

При выполнении операций включения/исключения элемента в двунаправленном списке надо изменять больше связей (указателей), чем в однонаправленном, но это обеспечивает большую гибкость, особенно при удалении и обходе.

1. Начальное формирование списка (CreateDoublyList)
   • Описание: Инициализирует пустой двунаправленный список.
   • Псевдокод:

     FUNCTION CreateDoublyList()
         HEAD = NULL
         TAIL = NULL
         RETURN (HEAD, TAIL)
     END FUNCTION
     

2. Проверка пустоты списка (IsEmptyDoubly)
   • Описание: Определяет, содержит ли двунаправленный список элементы.
   • ��севдокод:

     FUNCTION IsEmptyDoubly(HEAD)
         IF HEAD == NULL THEN
             RETURN TRUE
         ELSE
             RETURN FALSE
         END IF
     END FUNCTION
     

3. Добавление элемента в конец списка (AddAtEndDoubly)
   • Описание: Создает новый узел и добавляет его в конец списка.
   • Псевдокод:

     FUNCTION AddAtEndDoubly(HEAD, TAIL, value)
         newNode = CreateDoublyNode(value) // Создает узел с Data=value, Next=NULL, Prior=NULL
         IF IsEmptyDoubly(HEAD) THEN
             HEAD = newNode
             TAIL = newNode
         ELSE
             TAIL.Next = newNode
             newNode.Prior = TAIL
             TAIL = newNode
         END IF
         RETURN (HEAD, TAIL)
     END FUNCTION
     

4. Вставка элемента в начало списка (InsertAtBeginningDoubly)
   • Описание: Создает новый узел и делает его первым элементом списка.
   • Псевдокод:

     FUNCTION InsertAtBeginningDoubly(HEAD, TAIL, value)
         newNode = CreateDoublyNode(value)
         IF IsEmptyDoubly(HEAD) THEN
             HEAD = newNode
             TAIL = newNode
         ELSE
             newNode.Next = HEAD
             HEAD.Prior = newNode
             HEAD = newNode
         END IF
         RETURN (HEAD, TAIL)
     END FUNCTION
     

5. Вставка элемента перед заданным узлом (InsertBeforeNode)
   • Описание: Вставляет новый узел перед указанным существующим узлом. Эта операция становится простой благодаря наличию ссылки на предыдущий узел.
   • Псевдокод:

     FUNCTION InsertBeforeNode(HEAD, TAIL, targetNode, value)
         IF targetNode == NULL THEN
             PRINT "Целевой узел не может быть NULL."
             RETURN (HEAD, TAIL)
         END IF
         IF targetNode == HEAD THEN // Вставка в начало
             RETURN InsertAtBeginningDoubly(HEAD, TAIL, value)
         END IF
         newNode = CreateDoublyNode(value)
         newNode.Next = targetNode
         newNode.Prior = targetNode.Prior
         targetNode.Prior.Next = newNode
         targetNode.Prior = newNode
         RETURN (HEAD, TAIL)
     END FUNCTION
     

6. Удаление элемента (если известен указатель на элемент) (DeleteNode)
   • Описание: Удаляет узел из списка, если известен указатель на этот узел. Благодаря наличию двух указателей, можно удалить узел без необходимости обхода всего списка, так как легко доступны адреса тех элементов, указатели которых направлены на изменяемый элемент.
   • Псевдокод:

     FUNCTION DeleteNode(HEAD, TAIL, nodeToDelete)
         IF nodeToDelete == NULL OR IsEmptyDoubly(HEAD) THEN
             PRINT "Узел для удаления недействителен или список пуст."
             RETURN (HEAD, TAIL)
         END IF
         IF nodeToDelete == HEAD THEN
             HEAD = nodeToDelete.Next
             IF HEAD != NULL THEN
                 HEAD.Prior = NULL
             ELSE // Список стал пустым
                 TAIL = NULL
             END IF
         ELSE IF nodeToDelete == TAIL THEN
             TAIL = nodeToDelete.Prior
             IF TAIL != NULL THEN
                 TAIL.Next = NULL
             ELSE // Список стал пустым
                 HEAD = NULL
             END IF
         ELSE
             nodeToDelete.Prior.Next = nodeToDelete.Next
             nodeToDelete.Next.Prior = nodeToDelete.Prior
         END IF
         FreeNode(nodeToDelete)
         RETURN (HEAD, TAIL)
     END FUNCTION
     

7. Чтение элемента (поиск по значению) (SearchDoubly)
   • Описание: Ищет элемент с заданным значением. Аналогично однонаправленному списку, но может быть реализован и с обходом с конца, если известен TAIL.
   • Псевдокод:

     FUNCTION SearchDoubly(HEAD, value)
         current = HEAD
         WHILE current != NULL AND current.Data != value DO
             current = current.Next
         END WHILE
         RETURN current // Вернет NULL, если элемент не найден
     END FUNCTION
     

8. Обход списка в прямом направлении (PrintForward)
   • Описание: Проходит по всем элементам списка от начала до конца.
   • Псевдокод:

     FUNCTION PrintForward(HEAD)
         current = HEAD
         IF IsEmptyDoubly(HEAD) THEN
             PRINT "Список пуст."
             RETURN
         END IF
         WHILE current != NULL DO
             PRINT current.Data
             current = current.Next
         END WHILE
     END FUNCTION
     

9. Обход списка в обратном направлении (PrintBackward)
   • Описание: Проходит по всем элементам списка от конца до начала. Это уникальная операция для двунаправленных списков.
   • Псевдокод:

     FUNCTION PrintBackward(TAIL)
         current = TAIL
         IF IsEmptyDoubly(TAIL) THEN
             PRINT "Список пуст."
             RETURN
         END IF
         WHILE current != NULL DO
             PRINT current.Data
             current = current.Prior
         END WHILE
     END FUNCTION
     

10. Удаление всего списка (DeleteDoublyList)
    • Описание: Освобождает память, занимаемую всеми узлами двунаправленного списка.
    • Псевдокод:

      FUNCTION DeleteDoublyList(HEAD)
          current = HEAD
          WHILE current != NULL DO
              temp = current
              current = current.Next
              FreeNode(temp)
          END WHILE
          HEAD = NULL
          TAIL = NULL
          RETURN (HEAD, TAIL)
      END FUNCTION
      

Сравнительный анализ и эффективность списковых структур

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

Преимущества и недостатки однонаправленных списков

Преимущества:

• Простота реализации: Однонаправленные списки являются самой простой формой связных списков, что делает их относительно легкими для понимания и кодирования.
• Легкость вставки и удаления узлов в начале списка: Эти операции выполняются за константное время (O(1)), поскольку требуется лишь перенаправить указатель HEAD.
• Экономия памяти на указателях: Каждый узел хранит только один указатель на следующий элемент, что делает их более компактными по сравнению с двунаправленными списками.

Недостатки:

• Ограниченный доступ к узлам по индексу: Нельзя индексировать элементы напрямую, как в массиве. Для доступа к N-му элементу необходимо последовательно пройти (N-1) элементов, начиная от головного. Это делает доступ по индексу операцией с линейной сложностью (O(N)).
• Невозможность узнать адрес предыдущего элемента: Опираясь на содержимое текущего узла, невозможно получить доступ к предыдущему элементу, так как нет указателя Prior. Это усложняет операции, требующие обратного обхода или удаления произвольного элемента (кроме первого), так как для этого приходится искать предыдущий элемент, начиная с HEAD.
• Медленная вставка/удаление в конец или середину: Для выполнения этих операций требуется обход списка до нужной позиции или до предпоследнего элемента, что также имеет линейную сложность O(N).

Преимущества и недостатки двунаправленных списков

Преимущества:

• Возможность обхода в обоих направлениях: Наличие двух указателей (Next и Prior) позволяет легко перемещаться по списку как вперед, так и назад. Это удобно для многих алгоритмов и функций (например, "отмена/повтор").
• Более быстрое удаление узла: Если известен указатель на узел, который нужно удалить, операция занимает константное время (O(1)). Это связано с тем, что легко доступны адреса как предыдущего, так и следующего элементов, что позволяет быстро перенастроить их указатели. В однонаправленном списке для удаления произвольного элемента требовался бы обход списка для нахождения предыдущего элемента.
• Простота перестановки элементов: Возможность быстро изменять связи в обоих направлениях упрощает операции по переупорядочиванию элементов.
• Эффективная реализация стеков и очередей: Двунаправленные списки обеспечивают эффективную реализацию этих структур, позволяя добавлять и удалять элементы с любого конца за O(1).

Недостатки:

• Увеличенное потребление памяти: Каждый узел двунаправленного списка хранит два указателя, что означает, что он занимает больше памяти, чем узел однонаправленного списка.
  • На 32-битной системе однонаправленный список требует 4 байта на каждый узел для хранения указателя Next. Двунаправленный список требует 8 байт (4 байта для Next и 4 байта для Prior) на каждый узел.
  • На 64-битной системе однонаправленный список требует 8 байт на каждый узел для указателя Next. Двунаправленный список требует 16 байт (8 байт для Next и 8 байта для Prior) на каждый узел.
• Требуется больше операций с указателями при модификации списка: При вставке или удалении элемента необходимо обновить четыре указателя (два у нового/удаляемого узла и по одному у соседних), тогда как в однонаправленном списке — два (у нового/удаляемого узла и у предыдущего). Это делает код более сложным и подверженным ошибкам.
• Сложный код: Из-за большего количества указателей и необходимости поддерживать взаимные связи, реализация операций с двунаправленными списками обычно более сложна, чем с однонаправленными.

Временная и пространственная сложность операций

Для выбора оптимальной структуры данных крайне важно понимать, как ее характеристики влияют на производительность (временную сложность) и потребление ресурсов (пространственную сложность).

Таблица сравнительной сложности операций

Операция	Однонаправленный список (временная)	Двунаправленный список (временная)	Массив (временная)
Доступ к элементу по индексу	O(N)	O(N)	O(1)
Поиск элемента по значению	O(N)	O(N)	O(N)
Вставка в начало	O(1)	O(1)	O(N)
Вставка в конец	O(N) (без TAIL)	O(1)	O(1) (если есть место), O(N) (если нужна переаллокация)
Вставка в середину	O(N)	O(N) (если нужно искать) / O(1) (если известен указатель)	O(N)
Удаление из начала	O(1)	O(1)	O(N)
Удаление из конца	O(N)	O(1)	O(1) (логическое), O(N) (физическое)
Удаление из середины	O(N)	O(N) (если нужно искать) / O(1) (если известен указатель)	O(N)

Пространственная сложность:

• Однонаправленный список: O(N) для хранения N элементов, плюс N указателей. Дополнительная память: 4/8 байт на каждый узел (для Next).
• Двунаправленный список: O(N) для хранения N элементов, плюс 2N указателей. Дополнительная память: 8/16 байт на каждый узел (для Next и Prior).
• Массив: O(N) для хранения N элементов. Дополнительная память минимальна или отсутствует, если массив не хранит указатели на объекты.

Сравнение списковых структур с массивами

Выбор между связным списком и массивом часто является одним из первых важных архитектурных решений при работе с коллекциями данных.

1. Гибкость размера:
   • Списки: Обладают высокой гибкостью. Могут динамически изменять свой размер во время выполнения программы, увеличиваясь или уменьшаясь по мере добавления/удаления элементов. Размер ограничивается только доступной оперативной памятью.
   • Массивы: Имеют фиксированный размер, определенный на этапе компиляции или инициализации. Изменение размера массива (например, в C/C++) означает создание нового массива большего размера и копирование всех элементов из старого массива, что является дорогостоящей операцией O(N). В языках высокого уровня (Python, Java ArrayList) динамические массивы скрывают эту сложность, но по сути делают то же самое "под капотом".
2. Эффективность использования памяти:
   • Списки: Более эффективно работают с памятью, когда размер данных заранее неизвестен или сильно колеблется. Они выделяют память только для реально существующих элементов. Однако расходуют дополнительную память на указатели. Например, на 64-битной системе двунаправленный список будет требовать на 16 байт больше памяти на каждый узел только для хранения указателей по сравнению с массивом, который может хранить сами данные.
   • Массивы: Более эффективны по памяти, если размер данных известен и стабилен, так как не имеют накладных расходов на указатели (если не хранят указатели на объекты). Элементы расположены компактно.
3. Скорость вставки/удаления:
   • Списки: Вставка и удаление элементов в начало или конец (для двунаправленных списков) могут быть очень быстрыми (O(1)), так как требуется только изменение нескольких указателей. В середине списка это может быть O(N), если требуется поиск элемента.
   • Массивы: Вставка или удаление элемента в середину или начало массива требует сдвига всех последующих элементов, что является операцией с линейной сложностью O(N). Вставка в конец массива может быть O(1), если есть свободное место, но O(N), если требуется переаллокация.
4. Доступ к элементам:
   • Списки: Доступ к произвольному элементу требует последовательного обхода списка от начала (или конца для двунаправленных), что имеет линейную сложность O(N).
   • Массивы: Доступ к произвольному элементу по индексу является операцией с константной сложностью O(1), что делает их идеальными для задач, требующих частого и быстрого доступа к элементам по их позиции.

Вывод: массивы подходят, когда важен быстрый произвольный доступ по индексу, размер данных известен и относительно стабилен, а операции вставки/удаления в середину списка редки. Однонаправленные списки хороши, когда требуется частая вставка/удаление в начало, а доступ к элементам в основном последовательный или поиск некритичен по времени. Двунаправленные списки являются лучшим выбором, когда необходим обход в обоих направлениях, быстрые вставки/удаления в любой точке списка (при наличии указателя на элемент), и повышенное потребление памяти на указатели допустимо.

Управление памятью при работе с динамическими структурами данных

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

Механизмы динамического распределения памяти

Когда программа запускается, операционная система выделяет ей определенный объем памяти, который делится на несколько сегментов: код, статические данные, стек и куча (heap). Именно куча является тем "резервуаром", из которого выделяется память для динамических структур данных. В отличие от стека, который управляется автоматически (LIFO) и используется для локальных переменных и вызовов функций, куча предоставляет более гибкий, но и более ответственный механизм.

Процесс динамического выделения памяти:

1. Запрос: Программа отправляет запрос операционной системе (через специальные функции или операторы языка программирования) на выделение блока памяти определенного размера.
2. Выделение: Операционная система и ее менеджер памяти ищут свободный блок подходящего размера в куче. Если такой блок найден, он резервируется для программы, а ей возвращается указатель (адрес) на начало этого блока.
3. Использование: Программа использует выделенную память для хранения данных динамической структуры (например, узла списка).
4. Освобождение: Когда память больше не нужна, программа должна явно указать операционной системе, что этот блок можно вернуть обратно в кучу для дальнейшего использования.

В языках программирования, таких как C/C++, для управления динамическим выделением и освобождением памяти используются следующие функции стандартной библиотеки:

• malloc() (memory allocation): Выделяет непрерывный блок памяти указанного размера в байтах и возвращает указатель типа void* на начало выделенной области. Память не инициализируется.
  • Пример: int *ptr = (int *)malloc(10 * sizeof(int)); — выделяет память для 10 целых чисел.
• calloc() (contiguous allocation): Выделяет память под определенное количество элементов (передается количество элементов и размер одного элемента) и инициализирует все выделенные байты нулями. Также возвращает указатель типа void*.
  • Пример: int *ptr = (int *)calloc(10, sizeof(int)); — выделяет память для 10 целых чисел и обнуляет ее.
• realloc() (reallocation): Позволяет изменить размер ранее выделенного блока памяти. Может либо расширить/сузить текущий блок, либо выделить новый блок в другом месте, скопировать туда данные и освободить старый блок.
  • Пример: ptr = (int *)realloc(ptr, 20 * sizeof(int)); — изменяет размер блока, на который указывает ptr, до 20 целых чисел.
• free(): Освобождает ранее выделенный блок памяти, возвращая его в кучу. Принимает в качестве аргумента указатель на начало блока памяти. Крайне важно освобождать память, когда она больше не нужна.
  • Пример: free(ptr); — освобождает память, на которую указывает ptr.

В других языках, таких как Java, Python, C#, управление памятью осуществляется автоматически с помощью сборщика мусора (garbage collector). Программисту не нужно явно вызывать функции free(), сборщик мусора самостоятельно определяет, какие объекты больше не используются, и освобождает занимаемую ими память. Это значительно упрощает разработку, но не исключает проблем, связанных с неэффективным использованием памяти.

Проблемы управления памятью: утечки и фрагментация

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

1. Утечки памяти (Memory Leaks):
   • Что это: Утечка памяти происходит, когда программа выделяет память в куче, но по какой-либо причине забывает ее освободить, когда она перестает быть нужной. Этот блок памяти остается "занятым" до завершения работы программы, хотя фактически не используется.
   • Как возникают: Типичные сценарии включают:
     • Потерю указателя на выделенный блок памяти (например, присвоение указателю нового значения без предварительного free()).
     • Выход из функции, в которой был выделен блок памяти, без его освобождения.
     • Ошибки в логике обработки исключений, когда ветка кода с free() не выполняется.
   • Последствия: Накопление утечек памяти приводит к постепенному исчерпанию доступной оперативной памяти. В конечном итоге программа (или даже вся система) может замедлиться, начать работать нестабильно, а затем аварийно завершиться из-за нехватки ресурсов. В долг��живущих приложениях (серверы, операционные системы) это является критической проблемой.
2. Фрагментация памяти (Memory Fragmentation):
   • Что это: Фрагментация памяти возникает, когда в куче, несмотря на наличие достаточного общего объема свободной памяти, не оказывается непрерывного блока памяти подходящего размера для удовлетворения нового запроса. Куча становится похожей на швейцарский сыр, где много маленьких дырок (свободных блоков), но нет одной большой дыры, необходимой программе.
   • Как возникает: Активное выделение и освобождение блоков памяти различного размера приводит к образованию свободных областей (дыр) между занятыми блоками. Когда программа запрашивает большой блок, который не помещается ни в одну из этих "дыр", запрос может быть отклонен, даже если суммарно свободной памяти достаточно.
   • Последствия:
     • Внутренняя фрагментация: Происходит, когда выделенный блок памяти немного больше, чем фактически запрошено (из-за особенностей работы менеджера памяти). Неиспользуемое пространство внутри блока.
     • Внешняя фрагментация: Свободная память разбросана по множеству мелких, несмежных блоков. Это более серьезная проблема, так как она может привести к невозможности выделить большие блоки, даже если суммарно памяти достаточно.
     • Фрагментация снижает эффективность использования памяти и может замедлять работу программы, поскольку менеджеру памяти приходится тратить больше времени на поиск подходящего блока или уплотнение (дефрагментацию) памяти.

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

Временная и пространственная сложность операций со списками

Понимание временной и пространственной сложности операций является краеугольным камнем анализа эффективности алгоритмов и структур данных. Эти метрики позволяют оценить, насколько быстро алгоритм будет работать (время) и сколько памяти ему потребуется (пространство) в зависимости от размера входных данных. Мы используем нотацию "О-большое" (O-notation) для описания асимптотической сложности.

Однонаправленные списки

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

• Вставка элемента в начало списка: O(1)
  • Для этой операции достаточно создать новый узел, установить его указатель Next на текущий HEAD и обновить HEAD так, чтобы он указывал на новый узел. Количество шагов не зависит от размера списка.
• Удаление элемента из начала списка: O(1)
  • Аналогично, требуется лишь сохранить указатель на следующий элемент после HEAD, освободить память HEAD и обновить HEAD на сохраненный указатель. Константное время.
• Вставка/удаление элемента в конец или середину списка: O(N)
  • Эти операции требуют предварительного обхода списка от HEAD до нахождения нужной позиции или предыдущего элемента. В худшем случае (конец списка) придется пройти все N элементов.
• Доступ к N-му элементу (поиск по индексу) / Поиск элемента по значению: O(N)
  • Чтобы добраться до N-го элемента, необходимо последовательно пройти N узлов, начиная с HEAD. Это делает произвольный доступ неэффективным. Поиск по значению также требует последовательного обхода до нахождения элемента или конца списка.
• Пространственная сложность: O(N)
  • Для хранения N элементов требуется память пропорциональная N. Помимо самих данных, каждый узел хранит один указатель. Дополнительная память на указатели составляет:
    • 4 байта на 32-битных системах на каждый узел.
    • 8 байт на 64-битных системах на каждый узел.

Двунаправленные списки

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

• Вставка элемента в начало/конец списка: O(1)
  • Благодаря наличию указателей HEAD и TAIL, а также Prior у первого элемента и Next у последнего, вставка в любой из концов списка требует лишь изменения нескольких указателей, что занимает константное время.
• Удаление элемента (если известен указатель на элемент): O(1)
  • Если у нас уже есть прямой указатель на узел, который нужно удалить, мы можем легко перенастроить указатели Next его предыдущего соседа и Prior его следующего соседа. Это значительно быстрее, чем в однонаправленном списке, где всегда приходилось бы искать предыдущий элемент.
• Вставка узла перед заданным узлом (если известен указатель на элемент): O(1)
  • Аналогично удалению, наличие Prior указателя у targetNode позволяет напрямую получить доступ к предыдущему элементу и выполнить вставку за константное время.
• Поиск элемента (по значению или по индексу): O(N)
  • Как и в однонаправленных списках, если не используются дополнительные структуры, для поиска элемента требуется последовательный обход. Хотя можно начать обход с TAIL для элементов, расположенных ближе к концу, в худшем случае все равно придется пройти N элементов.
• Пространственная сложность: O(N)
  • Для хранения N элементов требуется память пропорциональная N. Каждый узел хранит два указателя. Дополнительная память на два указателя составляет:
    • 8 байт на 32-битных системах на каждый узел.
    • 16 байт на 64-битных системах на каждый узел.

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

Практические применения списковых структур данных

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

Реализация других структур данных

Списки часто служат фундаментом для построения более сложных и абстрактных структур данных:

• Стеки (Stacks): Принцип работы стека (LIFO – Last In, First Out) идеально реализуется с помощью однонаправленного списка. Операции push (добавление) и pop (удаление) выполняются в начале списка за O(1), что соответствует требованиям стека.
• Очереди (Queues): Принцип работы очереди (FIFO – First In, First Out) также эффективно реализуется на списках. С помощью однонаправленного списка можно реализовать добавление в конец (O(N) без TAIL, O(1) с TAIL) и удаление из начала (O(1)). Двунаправленный список упрощает реализацию, позволяя выполнять обе операции за O(1), если есть указатели на HEAD и TAIL.
• Деки (Deques – Double-Ended Queues): Двусторонние очереди, позволяющие добавлять и удалять элементы с обоих концов, естественно реализуются на двунаправленных списках, обеспечивая O(1) сложность для всех базовых операций.
• Деревья и Графы: Хотя эти структуры имеют более сложную топологию, их внутреннее представление часто использует связные списки. Например, список смежности для графа — это набор однонаправленных списков, где каждый список хранит соседей одной вершины. В узлах деревьев ссылки на потомков по сути являются указателями, аналогичными тем, что используются в списках.

Применение в операционных системах и файловых системах

Операционные системы, как сложные программные комплексы, активно используют списковые структуры для управления своими внутренними ресурсами:

• Управление процессами: ОС поддерживают списки активных, готовых и заблокированных процессов. Каждый элемент списка содержит информацию о процессе (PID, состояние, приоритет), а ссылки позволяют эффективно добавлять, удалять и перемещать процессы между списками.
• Управление памятью: Свободные блоки оперативной памяти часто организуются в связные списки. Когда процесс запрашивает память, ОС ищет подходящий блок в списке свободных, выделяет его, а остаток (если блок больше запрошенного) возвращает в список. При освобождении памяти, блок добавляется обратно в соответствующий список.
• Файловые системы: Связные списки являются фундаментальной частью некоторых файловых систем.
  • FAT (File Allocation Table): Классический пример использования однонаправленных списков. Таблица FAT представляет собой массив, где каждый элемент указывает на следующий кластер файла. По сути, это массив указателей, формирующий однонаправленные списки для каждого файла.
  • NTFS (New Technology File System): Хотя NTFS является более сложной файловой системой и основана на B+ дереве, B+ деревья сами по себе являются примером реализации, где узлы на уровне листьев часто организованы как двусвязный список для эффективного последовательного доступа.

Применение в пользовательских интерфейсах и других задачах

Помимо системного программирования, списки находят широкое применение и в прикладных областях:

• Функции "Отмена/Повтор" (Undo/Redo): Двунаправленные списки идеально подходят для реализации истории действий в текстовых редакторах, графических программах или IDE. Каждая операция (ввод символа, изменение форматирования) сохраняется как узел в двунаправленном списке. Функция "отмена" перемещает указатель назад по списку, "повтор" — вперед.
• Динамические списки в пользовательских интерфейсах (UI): В сложных корпоративных системах (например, 1С:Предприятие), когда необходимо отображать огромные объемы данных (списки клиентов, документов, товаров), используются динамические списки. Эти списки загружают данные порциями по мере навигации пользователя (например, при прокрутке), избегая загрузки всего объема в память, что повышает производительность и отзывчивость интерфейса.
• Редактирование текста: При обработке текста, когда требуется вставить или удалить символы/слова в произвольном месте без дорогостоящего сдвига, как в массивах, связные списки могут быть эффективны.
• Пользовательские аллокаторы памяти: В высокопроизводительных приложениях или встроенных системах разработчики могут создавать свои собственные менеджеры памяти, которые используют связные списки для отслеживания свободных блоков памяти и оптимизации выделения/освобождения.
• Представление многочленов: В математических вычислениях многочлены могут быть представлены как связные списки, где каждый узел содержит коэффициент и степень члена. Это позволяет эффективно выполнять операции сложения, вычитания или умножения многочленов переменной длины.
• Слайд-шоу и галереи изображений: Однонаправленные или циклические списки могут использоваться для организации последовательности изображений, позволяя пользователю перемещаться вперед или назад по галерее.

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

Заключение

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

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

Не менее важным аспектом исследования стало управление памятью. Мы рассмотрели механизмы динамического выделения и освобождения памяти, такие как malloc, calloc, realloc и free, и подробно разобрали критические проблемы, связанные с этим процессом: утечки памяти и фрагментация, которые могут привести к серьезным сбоям в работе программ.

Наконец, курсовая работа осветила широкий спектр практических применений списковых структур данных – от реализации фундаментальных структур, таких как стеки и очереди, до их использования в ядре операционных систем (файловые системы FAT, NTFS), в высоконагруженных пользовательских интерфейсах (1С:Предприятие) и для реализации таких повседневных функций, как "отмена/повтор".

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

Список использованной литературы

1. Айен Синклер. Большой толковый словарь компьютерных терминов. М., 1998.
2. Архангельский А. Я. Программирование в Delphi 4. М., 1999.
3. Архангельский А. Я. Программирование в C++. М., 2000.
4. Бабушкина И.А., Бушмелева Н.А., Окулов С.М., Черных С.Ю. Конспекты по информатике. Киров, 1997.
5. Вирт Н. Алгоритмы и структуры данных. Москва: Мир, 1989.
6. Вирт Н. Алгоритм + структура данных = программа.
7. Давыдов В.Г. Программирование и основы алгоритмизации. 2-е изд., стер. М.: Высш. шк., 2005. 447 с.
8. Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. М.: Мир, 1988.
9. Гудмэн Д. Управление памятью для всех. Киев, 1995.
10. Зубов В. С. Справочник программиста. М., 1999.
11. Информатика и образование. 1999. №5.
12. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976.
13. Кормен Т. и другие. Алгоритмы построения и анализ. М., 2000.
14. Культин Н. Б. C++ Builder в задачах и примерах. Санкт-Петербург: ХВ-Петербург, 2005.
15. Мюррей У., Паллас К. VisualC++. М.: BHV, 1996.
16. Подласый И. П. Учебник для студентов высших педагогических учебных заведений. М.: Просвещение, 1996.
17. Райнтли. Абстракция и структура данных.
18. Усова А. В. Формирование у школьников понятий в процессе обучения. М.: Педагогика, 1986.
19. Уэйт М., Прата С. Язык Си. М.: МИР, 1988.
20. Хабибуллин И.Ш. Программирование C++. 3-е изд. СПб.: БХВ-Петербург, 2006. 512 с.
21. Структуры и алгоритмы компьютерной обработки данных. Лекция 29: Динамические структуры данных. URL: https://www.intuit.ru/studies/courses/22/22/lecture/610 (дата обращения: 01.11.2025).
22. В чем разница между статическими и динамическими структурами данных? URL: https://www.geeksforgeeks.org/difference-between-static-and-dynamic-data-structures/ (дата обращения: 01.11.2025).
23. Динамические структуры данных. URL: https://www.intuit.ru/studies/courses/22/22/lecture/611 (дата обращения: 01.11.2025).
24. Глава 13. Динамические структуры данных. URL: http://www.cmc.msu.ru/node/1487 (дата обращения: 01.11.2025).
25. Динамические структуры данных. URL: http://edu.sfu-kras.ru/sites/edu.sfu-kras.ru/files/metodichka_po_c_chast_2.pdf (дата обращения: 01.11.2025).
26. Шаг 1. Динамические структуры данных. URL: https://www.citforum.ru/programming/pascal/step01.shtml (дата обращения: 01.11.2025).
27. Динамические структуры данных. URL: https://die.info/blog/dynamicheskie-structury-dannyh/ (дата обращения: 01.11.2025).
28. Классификация динамических структур данных. URL: http://www.tech.kstu.ru/files/text/metod/s_dan/1_1.htm (дата обращения: 01.11.2025).
29. Классификация динамических структур данных. URL: http://ikt.ulstu.ru/wp-content/uploads/2019/11/2-%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F-%D0%90%D0%B8%D0%A1%D0%94.docx (дата обращения: 01.11.2025).
30. В чем заключаются основные преимущества двунаправленных списков перед однонаправленными? URL: https://www.geeksforgeeks.org/advantages-of-doubly-linked-list-over-singly-linked-list/ (дата обращения: 01.11.2025).
31. Классификация структур данных. URL: https://otus.ru/media/articles/klassifikatsiya-struktur-dannykh/ (дата обращения: 01.11.2025).
32. Шаг 35. Двунаправленные списки. URL: https://www.citforum.ru/programming/pascal/step35.shtml (дата обращения: 01.11.2025).
33. Структуры данных: двусвязный (двунаправленный) список. URL: https://medium.com/nuances-of-programming/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B-%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85-%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9-%D0%B4%D0%B2%D1%83%D0%BD%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9-%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA-2ee7a5a87e07 (дата обращения: 01.11.2025).
34. Динамические структуры данных. Сравнения статических и динамических структур данных. Область применения динамических структур. URL: https://www.it-lectures.ru/lectures/programming/1154-dinamicheskie-struktury-dannykh.html (дата обращения: 01.11.2025).
35. Динамическое выделение и освобождение памяти в языке Си. URL: https://stepik.org/lesson/105436/step/2 (дата обращения: 01.11.2025).
36. Типы и структуры данных: какие бывают, примеры статических в программировании. URL: https://itproger.com/articles/tipy-i-struktury-dannyh-kakie-byvayut-primery-staticheskih-v-programmirovanii (дата обращения: 01.11.2025).
37. § 21. Структуры данных. URL: https://profi.msu.ru/lectures/informatics/structures.pdf (дата обращения: 01.11.2025).
38. Динамическое распределение памяти. URL: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8 (дата обращения: 01.11.2025).
39. Динамическая память и реализация динамического массива в C. URL: https://habr.com/ru/articles/763660/ (дата обращения: 01.11.2025).
40. Связные списки: однонаправленные, двунаправленные, кольцевые. Примеры реализации. URL: http://www.ict.edu.ru/ft/005698/626292.pdf (дата обращения: 01.11.2025).
41. Лекция №12. Динамические структуры данных. URL: http://www.pstu.ru/files/file/lectures/programming_languages/Lect_12.pdf (дата обращения: 01.11.2025).
42. Динамические структуры данных. Стек на языке Си. URL: https://linuxoid.ru/articles/dinamicheskie-struktury-dannyh-stek-na-yazyke-si (дата обращения: 01.11.2025).
43. Списки в C++. Односвязный список. URL: https://otus.ru/journal/spiski-v-c-odnosvyaznyj-spisok/ (дата обращения: 01.11.2025).
44. Циклический двунаправленный список. URL: https://etu.ru/assets/files/nauka/dissertacii/2014/korablyov-av/dissertaciya_korablyov.pdf (дата обращения: 01.11.2025).
45. Практическое применение связных списков в программировании. URL: https://abashin.ru/article/prakticheskoe-primenenie-svyaznykh-spiskov-v-programmirovanii (дата обращения: 01.11.2025).
46. Двусвязный список | Основы алгоритмов и структур данных. URL: https://ru.hexlet.io/courses/data-structures/lessons/doubly-linked-list/theory_unit (дата обращения: 01.11.2025).
47. Список. URL: https://pvs-studio.com/ru/docs/tutorials/list/ (дата обращения: 01.11.2025).
48. Курс Harvard CS50 - Лекция: Связный список и двусвязный список. URL: https://javarush.com/groups/posts/2627-svyaznoy-spisok-i-dvusvyaznoy-spisok (дата обращения: 01.11.2025).