Динамические типы данных. Списки

(узлов), которые состоят из данных и полей связи между узлами.
К спискам применимы ряд операций, например, включения, исключения, копирования, поиска, сортировки.

Списки – наиболее широко применяемая в программировании динамическая структура данных:
- при решении прикладных задач программирования:
при организации списков объектов (пользователей, задач, документов, рассылки, и т.п.);
- в системном императивном программировании:
при реализации ядра ОС;
при реализации СУБД;
при реализации пользовательского интерфейса;
при работе с файлами;
при построении других динамических структур данных: стеки, очереди, деревья, сети и графы, хеш-таблицы;
при построении трансляторов;
в функциональном программировании:
язык ЛИСП и его диалекты

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

Вложенные

памяти.
Используются указатели для реализации полей связи.

Достоинства:
лёгкость добавления и удаления элементов;
размер ограничен только объёмом памяти компьютера и разрядностью указателей;

Недостатки:
на поля связи (указатели на следующий и предыдущий элемент) расходуется дополнительная пам’ять;
работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы;
элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора;

из поля данных и указателя на следующий узел.
Начальный узел называется головой списка.
Значение указателя связи последнего узла равно NULL.
Полей данных может быть несколько.

Сравнение массивов и списков

списка;
поиск элемента в списке
удаление списка.

на след.узел
};

typedef Node *PNode; // тип данных: указатель на узел
PNode PHead; // указатель на голову списка
PHead = NULL; // список пуст

Создание списка

PNode createNode (int num)
{
PNode PNew = new Node; // указатель на новый узел
PNew->data = num; // поле данных – номер узла
PNew->next = NULL; // следующего узла нет
return PNew; // результат функции – адрес узла
}

Создание узла

addFirst (PNode &PHead, PNode PNew)
{
// установить next нового узла на голову списка
PNew->next = PHead;
//установить голову списка на новый узел
PHead = PNew;
}

в начало списка:

адрес головы списка передается по ссылке

1

2

next нового узла на узел, следующий за заданным PNew->next = p->next;// p – указатель на заданный узел
//установить next заданного узла на новый узел
p->next = PNew;
}

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

1

p

{ // если список пуст,
AddFirst(Head, NewNode); // вставляем первый элемент
return;
}
while (q->next) q = q->next; // ищем последний элемент
AddAfter(q, PNew);
}

Добавление узла в конец списка

== p) {
AddFirst(Head, NewNode); // вставка перед первым узлом
return;
}
while (q && q->next!=p) // ищем узел, за которым следует p
q = q->next;
if ( q ) // если нашли такой узел,
AddAfter(q, NewNode); // добавить новый после него
}

Добавление узла перед заданным

NULL) { printf("%d ", p->data); p = p->next; } printf("]\n"); }

PNode findNode (PNode PHead, int num)
{
PNode q = PHead;
// пока есть узел проверить нужное условие
while (q && ((q->data) != num))
q = q->next;
return q;
}

Поиск элемента в списке

(Head == DNode)
Head = DNode->next; // удаляем первый элемент
else {
while (q && q->next != DNode) // ищем элемент
q = q->next;
if ( q == NULL ) return; // если не нашли, выход
q->next = DNode->next;
}
delete DNode; // освобождаем память
}

q

DNode

PHead;
}
}

Удаление списка

Задание:

Удалить все элементы.
Найти средину списка.
Найти средину списка за один проход.