Интрузивный список

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

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

Пример

Пример интрузивного списка пар целых чисел:

struct list_link 
{
    list_link *prev, *next;
};
 
struct element
{
    int x, y;
    list_link link;
};

Для сравнения, пример обычного списка пар целых чисел:

struct list
{
    list *next, *prev;
    element* data;
};
 
struct element // структура не меняется
{
    int x, y;
};

См. также

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

Ссылки

• Обсуждение на RSDN: интрузивные/неинтрузивные контейнеры.

Литература

• Б. Страуструп. Язык программирования C++ = The C++ Programming Language / Пер. с англ. — 3-е изд. — СПб.; М.: Невский диалект — Бином, 1999. — 991 с. — 3000 экз. — ISBN 5-7940-0031-7 (Невский диалект), ISBN 5-7989-0127-0 (Бином), ISBN 0-201-88954-4 (англ.)

Связать^?

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