Различные типы связанных списков!
Каковы различные типы Связанных списков, которые являются наиболее часто используемыми?
Я знаю и использовал следующее:
- Отдельно связанный список
- Двунаправленный связанный список
- Циклический список
Каковы другие виды списков, которые использовались Вами или известны Вам?
5 ответов
В компьютерном программировании развернутый связный список - это разновидность связного списка, в котором в каждом узле хранится несколько элементов. Он может значительно увеличить производительность кэша, одновременно снижая затраты памяти, связанные с хранением метаданных списка, таких как ссылки. Он связан с B-деревом. - Википедия
XOR-связанные списки - это структура данных. используемая в компьютерном программировании. Они используют преимущество побитового исключающей дизъюнкции (XOR) операция, обозначаемая здесь ⊕, чтобы уменьшить требования к хранению двусвязных списков. - Wikipedia
Я, вероятно, мог бы придумать сценарии, в которых было бы полезно иметь возможность связывать любой элемент в списке с первым и последним элементами. Если меня никто не поправит, я утверждаю, что это называется High-Performance-Mark-List .
Пропустить списки ! На самом деле это не тип связанного списка, но связанный и довольно аккуратный.
Хорошо, это либо тип связанного списка, либо группа связанных списков, в зависимости от того, как вы классифицируете вещи, но в нем есть вставка / выбор O (log N), что довольно приятно для связного списка.
Существует также многосвязный список.
В многосвязном списке каждый узел содержит два или более полей связей, каждое из которых используется для соединения одного и того же набора записей данных в различном порядке (например, по имени, по отделу, по дате рождения и т.д.). (Хотя двусвязные списки можно рассматривать как частные случаи многосвязных списков, тот факт, что два порядка противоположны друг другу, приводит к более простым и эффективным алгоритмам, поэтому их обычно рассматривают как отдельный случай.)
И стеки и очереди часто реализуются с помощью связных списков, и просто ограничивают тип операций, которые поддерживаются. развернутый связный список - это связный список, в котором каждый узел содержит массив значений данных. Это приводит к улучшению производительности кэша, так как большее количество элементов списка смежны в памяти, и уменьшению накладных расходов памяти, так как меньше метаданных нужно хранить для каждого элемента списка.