Связанный список может использоваться, когда вы хотите дешевую вставку и удаление элементов, и когда не имеет значения, что элементы не находятся рядом друг с другом в памяти.
Это очень абстрактно, и я хотел бы получить конкретное объяснение того, почему следует использовать связанный список, а не массив. Я не очень опытный в программировании, поэтому у меня нет большого (если вообще) реального опыта.
data-structures
linked-list
rightfold
источник
источник
Ответы:
Здесь есть нечто среднее между примером и аналогией. У вас есть кое-какие поручения, поэтому вы берете лист бумаги и пишете:
Тогда вы помните, что вам также необходимо купить марки. Из-за географии вашего города, вы должны сделать это после банка. Вы можете скопировать весь список на новый лист бумаги:
или вы могли бы набросать на тот, который у вас был:
Как вы уже подумали о других поручениях, вы можете написать их внизу списка, но со стрелками, напоминающими себе, в каком порядке их выполнять. Это связанный список. Это быстрее и проще, чем копировать весь список каждый раз, когда вы что-то добавляете.
Тогда ваш мобильный телефон звонит, пока вы в банке "Эй, у меня есть марки, больше не бери". Вы просто вычеркиваете STAMPS из списка, вы не переписываете новый без STAMPS.
Теперь вы можете реализовать список поручений в коде (может быть, приложение, которое упорядочивает ваши поручения в зависимости от вашей географии), и есть реальный шанс, что вы на самом деле будете использовать связанный список для этого в коде. Вы хотите добавить и удалить много элементов, порядок вещей, но вы не хотите переписывать весь список после каждой вставки или удаления.
источник
источник
«Стек вызовов» языка C реализован в виде связанного списка в двоичных API x86 (и большинстве других).
То есть, вызов процедуры на языке C следует дисциплине «первым пришел - последним вышел». Результат выполнения (возможно, рекурсивных) вызовов функций упоминается как «стек вызовов», а иногда даже просто «стек».
CALLИнструкция x86 заканчивается implmenting связанного списка , используя «стек вызовов».CALLИнструкция толкает содержимое регистра EIP%, адрес команды после вCALLна память стека. Пролог call-fuction помещает содержимое регистра% EBP, самого низкого адреса локальных переменных в вызывающей функции, в стековую память. Затем пролог вызываемой функции устанавливает% EBP в базу стека текущей функции.Это означает, что% EBP является указателем на область памяти, в которой хранится адрес значения% EBP вызывающей функции. Это не что иное, как связанный список, реализованный частично через аппаратное обеспечение
CALL.Насколько это хорошо, это то, как процессоры x86 реализуют вызовы функций, особенно вызовы функций, где функция имеет свою собственную копию аргументов и локальные для функции переменные. Каждый вызов функции помещает некоторую информацию в «стек вызовов», который позволяет процессору определить, где он остановился в вызывающей функции, без вмешательства вызываемой функции или вызывающей функции.
источник
Связанный список можно использовать для реализации очереди сообщений.
Очередь сообщений - это структура, в которой мы храним информацию о событиях для последующей обработки. Например, когда пользователь нажимает клавишу или перемещает мышь, это событие. Приложение может быть занято в момент возникновения события, поэтому нельзя ожидать, что оно обработает событие в тот момент, когда оно произойдет. Таким образом, событие помещается в очередь сообщений (информация о том, какая клавиша была нажата или где перемещена мышь), и, когда у приложения остается свободное время, оно проверяет свою очередь сообщений, выбирает события из нее и обрабатывает их. (Это происходит за миллисекунды, поэтому это не заметно).
Из сценария использования, который я только что описал, должно быть очевидно, что нам никогда не нужен произвольный доступ к событиям, хранящимся в очереди сообщений; мы заботимся только о том, чтобы иметь возможность хранить в нем сообщения и извлекать их. Таким образом, имеет смысл использовать связанный список, который обеспечивает оптимальное время вставки / удаления.
(Пожалуйста, не стоит указывать, что очередь сообщений, вероятно, или более вероятно, или почти так же вероятно, будет реализована с использованием кругового массива-списка; это техническая деталь, и она имеет ограничение: вы можете хранить только ограниченное количество сообщений в нем.)
источник