Различные типы связанных списков!

Question

Какие типы связанных списков обычно используются?

Я знаю и использовал следующее:

1. Одиночный связанный список
2. Двусвязный список
3. Циркулярный список

Какие еще списки были использованы вами или известны вам?

Answer 1

1. Развернутый связанный список

В компьютерном программировании развернутый связанный список - это разновидность связанного списка, в котором хранятсянесколько элементов в каждом узле.Это может значительно увеличить производительность кэша, уменьшая при этом нагрузку на память, связанную с хранением метаданных списка, таких как ссылки.Это связано с B-деревом.- Википедия

Связанный список XOR

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

Answer 2

Пропуск списков ! Не совсем тип связанного списка, но связанный и довольно аккуратный.

Хорошо, это либо тип связанного списка, либо группа связанных списков, в зависимости от того, как вы классифицируете вещи, но он имеет вставку / выбор O (log N), что довольно приятно для связанного списка.

Answer 3

Существует также многосвязный список .

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

Answer 4

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

Answer 5

Я мог бы придумать сценарии, в которых было бы полезно иметь возможность связать любой элемент в списке с первым и последним элементами. Если никто не исправит меня, я утверждаю, что это называется High-Performance-Mark-List .