Rose debug info
---------------

Структуры данных: связанные списки

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

Наиболее используемые типы списков:

  1. Односвязный список
+-------+------+    +-------+-------+ 
| Hello |  *---+--->| world | null  +
+-------+------+    +-------+-------+
  1. Двусвязный список
+----------+---------+       +----------+----------+ 
|          |     *---|------>|          |          |
|  Hello   |         |       |          |  world   |
|          |         |<------|---*      |          |
+----------+---------+       +----------+----------+
  1. Кольцевой список
.        +-------<----------<--------------<--------+
         |                                          |
+-----+--+---+    +-----+------+    +-----+-----+   |
| 12  |  *---+--->| 15  |   *--+--->| 25  |  *--+---+
+-----+------+    +-----+------+    +-----+-----+



Быстродействие

  • Добавляет элемент в конец/начало списка — O(1)
  • Удаляет первый элемент списка со значением, равным переданному — O(n)
  • Поиск элемента — O(n)
  • Копирование а массив — O(n)
  • Получить количество — O(1)

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

  1. Элементы могут быть удалены или добавлены из середины списка
  2. Нет необходимости объявлять разvер списка при инициализации
  3. Эффективное удаление и добавление элементов

Недостатки

  1. Связанные списки не имеют возможности произвольного доступа к элементам — т. е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него.
  2. Для работы списков требуется динамическое выделение памяти, что может привести к утечкам памяти.

Ссылки

  1. https://metanit.com/sharp/algoritm/2.1.php
  2. https://rtfm.co.ua/c-svyazannye-spiski/
  3. https://ru.wikipedia.org/wiki/Связный_список
  4. https://tproger.ru/translations/linked-list-for-beginners/
  5. https://medium.com/outco/reversing-a-linked-list-easy-as-1-2-3-560fbffe2088
Поделиться
Отправить