Использование списка ссылок в системном программировании

Question

, несмотря на наличие стольких эффективных структур данных, почему используется только связанный список так сильно в системном программировании? Это потому, что это позволяет наименьшее использование кучи / меньше глючного кода?

С уважением, Pwn

Answer 1

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

Answer 2

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

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

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

Это потому, что он позволяет наименьшее использование кучи / меньше глючного кода?

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

Answer 3

Я предполагаю, потому что это очень просто реализовать и понять. И у него очень маленькие накладные расходы.

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

Так что это просто хороший матч. Нет необходимости (или редко) в необходимости усложнять ситуацию.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Есть много мест, где вам нужна именно такая структура.Есть и другие места, где вам это не нужно.

Answer 8

Обычно это потому, что вам нужен список вещей - то есть вам часто просто нужно что-то, что вы можете легко добавить / удалить с любого конца или удалить / вставить по указателю узла, который у вас уже есть, и выполнить итерацию.

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

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