Что такое интрузивный список и как он хранит данные?

В обычном List<Struct> данные находятся последовательно. В ячейках сохраняются значимые типы данных.

Если же это List<Class> то все сложнее но суть +- та же.

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

Интрузивный список — это такой список, в котором каждый элемент содержит ссылки на соседей. Другими словами, элементы в таком списке «имеют представление» о том, что находятся в списке и своем положении в нем, тогда как в обычном списке данные и информация о соседних элементах изолированы друг от друга.

Но есть и иной подход - он используется в LinkedList - это когда тип данных сохраняемый в листе помещается в обертку. Обертка в себе имеет сам обьект и две ссылки на соседние ячейки - предыдущую и последующую.

Это и есть пример Интрузивного списка.

Обращаться по индексу там невозможно.

Если ты стоишь перед диллемой: "стоит ли использовать LinkedList или нет?" - его НЕ СТОИТ ИСПОЛЬЗОВАТЬ.

LinkedList стоит использовать:

• Если нужно добавлять ячейки в начало/середину/конец листа в большом количестве
• Если нужен только последовательный доступ (не нужны индексы для random access)
• Хорошо подходит для хранения увесистых обьектов в относительно небольшом количестве т.к. под каждую ячейку так же нужно выделять память на 2 ссылки.

Смежная полезная информация по этой теме: C# List vs LinkedList vs Array

Интрузивный список - это список в котором элемент хранит свои полезные данные и связи с другими элементами вместе.

struct list_item {
      int a;
      int b;
      int c;
      list_item *next;
}

В неинтрузивном списке тип с полезными данными помещается внутрь типа элемента списка.

struct my_type {
      int a;
      int b;
      int c;
}
struct list_item {
      my_type *data;
      list_item *next;
}