Списки
Простейший и самый быстрый способ собрать список – это добавлять новые элементы в его начало:
При изменении списка у него может измениться первый элемент, что и происходит при вызове addfront. Функции, изменяющие список, должны возвращать указатель на новый первый элемент, который хранится в переменной, указывающей на список. Функция addfront и другие функции этой группы передают указатель на первый элемент в качестве возвращаемого значения; вот типичное использование таких функций:
nvlist = addf ront(nvlist, newitem("smiley", Ox263A));
Такая конструкция работает, даже если существующий список пуст (NULL), она хороша и тем, что позволяет легко объединять вызовы функций в выражениях. Это более естественно, чем альтернативный вариант – передавать указатель на указатель на голову списка.
Добавление элемента в конец списка – процедура порядка O(n), поскольку нам нужно пройтись по всему списку до конца:
Чтобы сделать addend операцией порядка O(1), мы могли бы завести отдельный указатель на конец списка. Недостаток этого подхода, кроме того, что нам нужно заботиться о корректности этого указателя, состоит в том, что список теперь уже представлен не одной переменной, а двумя. Мы будем придерживаться более простого стиля.
Для поиска элемента с заданным именем нужно пройтись по указателям next:
Поиск занимает время порядка O(n), и, в принципе, эту оценку не улучшить. Даже если список отсортирован, нам все равно нужно пройтись по нему, чтобы добраться до нужного элемента. Двоичный поиск к спискам неприменим.