infa_1 / 4.Связные списки

4. Связные списки

Список – упорядоченное множество, состоящее из переменного числа элементов, к которым применяются операции включения и исключения.

Связный список – структура данных, элементами которой являются записи, связанные друг с другом при помощи указателей, хранящихся в самих элементах записей.

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

• линейный: односвязный (циклич./нециклич.), двухсвязный (циклич./нециклич.)

• нелинейный: двухсвязный, многосвязный.

В зависимости от характера взаимного расположения элемента в памяти структуры данных можно разделить на:

• структуры с последовательным распределением элементов памяти (векторы, строки, массивы)

• структуры с произвольным распределением элементов памяти (односвязные и двусвязные списки)

Над всеми структурами данных могут выполняться 4 операции:

1) создание (заключение в отделении памяти для структуры данных)

2) уничтожение

3) выбор (доступ)

4) обновление

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