Списки в C++

Массив — не единственный тип, способный играть роль контейнера для данных. Другим таким типом является связанный список. В отличие от массива, он реализуется не языком, а программистом.

Пример. Определить связанный список и операции над ним.

// Структура - элемент списка
struct Item {
int info;
Item* next;
};

void main ( )
{
Item *first = 0; //Указатель на начало списка
Item *p;
int i;
// Создать список
for (;;) {
// Вводить числа, пока не введем 0
сin » i;
if (!i) break;

// Создать новый элемент списка
р = new Item;
p->info = i;

// Присоединить новый элемент к началу списка
p->next = first ;
first = р;
}

// Пройти список и вывести элементы
р = first;
while (p) {
cout « p->info « " " ;
р = p->next;
}

// Пройти список и удалить элементы
while (first) {
р = first;
first = first->next ;
delete p;
}
}

Другие виды списков:
• список с указателями на первый и последний элементы — позволяет добавлять и удалять элементы с обеих сторон списка;
• двунаправленный список — позволяет перемещаться по списку в обоих направлениях;
• кольцевой список — позволяет достичь любой элемент списка,
начав движение с любого места в списке.

Источник: http://www.cplus-plus.ru