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

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

Ref: - http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

Ответ 10

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