Какое использование для связанных списков?

Question

Имеют ли связанные списки какое-либо практическое применение вообще. Многие книги по информатике сравнивают их с массивами и говорят, что главное преимущество в том, что они изменчивы. Однако большинство языков предоставляют изменяемые версии массивов. Так есть ли у связанных списков какие-либо реальные применения в реальном мире, или они просто являются частью теории информатики?

Answer 1

Они абсолютно ценны (как в популярной версии с двойной связью , так и , менее популярной, но более простой и быстрой, когда это применимо !, версия с одной ссылкой). Например, вставка (или удаление) нового элемента в указанное «случайное» место в «изменяемой версии массива» (например, std::vector в C ++) - это O(N), где N - это количество элементов в массив, потому что все последующие (в среднем половина) должны быть сдвинуты, и это операция O(N); в списке это O(1), то есть постоянное время, если у вас уже есть, например, указатель на «предыдущий» элемент. Различия Big-O, подобные этой, абсолютно огромны - разница между реально используемой и масштабируемой программой и игрушкой "домашнее задание" уровня! -)

Answer 2

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

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

Answer 3

Основные применения связанных списков:

• Для представления полиномов. Это означает сложение / вычитание / умножение двух полиномов.Например: p1 = 2x ^ 2 + 3x + 7 и p2 = 3x ^ 3 + 5x + 2 p1 + p2 = 3x ^ 3 + 2x ^ 2 + 8x + 9
• В динамическом управлении памятью При выделении и освобождениипамять во время выполнения.* В таблицах символов в балансирующем паратезе
• Представляет разреженную матрицу

Ссылка: - http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf

Answer 4

Да, конечно, это полезно по многим причинам.

В любое время, например, если вы хотите эффективную вставку и удаление из списка.Чтобы найти место вставки, у вас есть поиск O (N), но для выполнения вставки, если у вас уже есть правильная позиция, это O (1).

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

Answer 5

Так что связанные списки имеют какое-либо реальное применение в реальном мире,

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

Answer 6

Неизменяемый связанный список является наиболее тривиальным примером постоянной структуры данных, поэтому он является стандартной (а иногда даже только ) структурой данных во многих функциональных языках. Lisp, Scheme, ML, Haskell, Scala, вы называете это.

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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