Применение связанных списков

Введение

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

История связных списков

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

Рисунок 1. Пример связного списка
Рисунок 1. Пример связного списка

У последней записи на рисунке отсутствует ссылка, но она есть и указывает на NULL. На основе списков можно реализовать структуры данных, такие как стеки, очереди и ассоциативные массивы.

Ранее уже упоминалось, что в массиве все элементы расположены в памяти по порядку, а в списке они в памяти никак не упорядочены. Более того, элемент может быть добавлен в любую позицию в списке. Однако сама операция по вставке элемента в список требует дополнительных ресурсов, так как нужно последовательно просканировать список для поиска нужной позиции.

В классическом языке Си есть только массив, но отсутствует встроенная реализация связного списка. Однако в других языках, например, в Lisp, существует встроенная реализация данной структуры. Официальная «дата рождения» связных списков - 1955 год, когда они появились на стыке логической теории машин и алгоритмов для решения шахматных задач. Тогда же связные списки начали использоваться для решения проблем трансляции натуральных языков в лингвистических задачах. В 1958 году появился язык Lisp, и связный список стал одной из базовых структур этого языка.

Связные списки стали применяться и при разработке операционных систем, например, для реализации файловых систем. Так, для операционной системы TSS/360 компания IBM разработала двойные связные списки и утилиту на их основе для исправления ошибок в файловой системе. Если при сканировании каталога обнаруживался поврежденный элемент, то происходил откат с заменой поврежденного элемента на его предыдущую версию.

В начало

Основные правила реализации связных списков

Список состоит из элементов, называемых узлами (node). Первый узел списка называется «головным» (head), а последний - «хвостовым» (tail). На рисунке 2 изображен двойной связный список.

Рисунок 2. Двойной связный список
Рисунок 2. Двойной связный список

Каждый элемент состоит из 3-х полей, два из которых являются указателями на предыдущий или следующий узел. Элемент может указывать и более чем на два узла, и в этом случае список называется многосвязным.

Помимо упоминавшихся ранее стандартных массивов существуют еще динамические массивы. Размер обычного массива является фиксированной величиной, а в динамический массив можно добавлять или удалять из него элементы. Если элемент добавляется в середину динамического массива, то происходит перераспределение элементов, находящихся справа от него, так как все элементы массива должны быть расположены в памяти строго по порядку. Поэтому вставка элемента в динамический массив требует дополнительных ресурсов, если элемент добавляется не в конец массива. Преимущество связного списка в том, что не требуется перестраивать последовательность узлов, независимо от того, в какую позицию списка вставляется новый элемент. Недостаток связных списков – это последовательный доступ (sequential access) к элементам, тогда как для массивов время доступа постоянно и не зависит от размера - random access. Если приложению требуется быстрый поиск элемента по индексу, то в данном случае списки не подходят, и лучше воспользоваться массивами.

Еще один негативный момент при использовании связных списков связан с нерациональным использованием памяти. Если в узле хранится небольшая порция данных, например, булевское значение, то список становится неэффективными из-за того, что объем памяти, выделяемой под хранение связей, превышает объем памяти, выделяемой под хранение «полезной нагрузки». Для решения этой проблемы существуют развернутые связные списки - unrolled linked list, каждый элемент которого включает целый массив данных. Пример такого списка приведен в листинге 1.

Листинг 1. Развернутый связный список
record node { node next; int numElements; array elements; }

Связный список - это рекурсивная структура, так как узел всегда содержит указатель на следующий узел. Это позволяет использовать простой рекурсивный алгоритм для таких операций, как объединение двух списков или изменение порядка элементов на обратный. У односвязных списков есть важное преимущество: если к вершине такого списка добавляется новый элемент, то старый список будет по прежнему доступен по ссылке на только что добавленный узел. Этот прием называется persistent data structure (постоянное хранение данных). У двусвязных списков есть свои преимущества, так как они позволяют выполнять итерацию в обоих направлениях, в отличие от односвязных списков.

Если последний элемент будет указывать на первый элемент списка, то такая структура называется циклическим замкнутым (или кольцевым (circular)) списком. Кольцевые списки можно использовать для списка процессов, в которых применяется «карусельный» (round-robin) алгоритм. Для такого списка достаточно иметь один указатель, который одновременно указывает и на конец, и на начало очереди. Кольцевой список можно разбить на два кольцевых списка или, наоборот, объединить.

Рисунок 3. Кольцевой связный список
Рисунок 3. Кольцевой связный список

В начало

Топологическая сортировка

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

Предполагается, что существует множество из 3-х элементов a, b и c, которое удовлетворяет трем правилам:

  • транзитивность: если a < b и b < c, то a < c;
  • асимметричность: если a < b, то не b < a;
  • антирефлексивность: невозможность a < a.

Цель топологической сортировки - преобразование частичного порядка в линейный. Графически процесс топологической сортировки показан на рисунках 4 и 5.

Рисунок 4. Исходное множество
Рисунок 4. Исходное множество
Рисунок 5. Результат топологической сортировки
Рисунок 5. Результат топологической сортировки

Топологическая сортировка начинается с того, что во множестве выбирается элемент, которому не предшествует никакой другой. Этот элемент помещается в начало списка и исключается из множества. В оставшемся множестве опять выбирается такой же по свойству элемент, и все повторяется до тех пор, пока множество не станет пустым. Для подобного алгоритма потребуются две структуры, первая будет называться лидером (leader), а вторая - ведомой (trailer).

Листинг 2. Структуры для топологической сортировки
struct trailer { struct leader id; struct trailer next; }; struct leader { int key; int count; struct leader next; struct trailer trail; };

Элемент исходного множества, содержащийся в нем только один раз, является лидером, а остальные — ведомыми. Первоначально исходное множество задается в виде списка пар, как показано в листинге 3.

Листинг 3. Исходное множество
1 < 2 2 < 4 4 < 6 1 < 3 3 < 5...

На первом шаге эти пары читаются и создается список лидеров. Затем для каждого лидера формируется свой список ведомых. На платформе Unix есть специальная консольная утилита tsort, которая получает на вход список пар и выдает конечный линейный список.

Листинг 4. Использование утилиты tsort
$ tsort <<EOF > 3 8 > 3 10 > 5 11 > 7 8 > 7 11 > 8 9 > 11 2 > 11 9 > 11 10 > EOF 3 5 7 11 8 10 2 9

В начало

Задача Иосифа Флавия

Иосиф Флавий - это исторический деятель, живший в первом веке нашей эры, с которым была связана одна драматическая история. Об этой истории можно прочесть по >>следующей ссылке<< [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%98%D0%BE%D1%81%D0%B8%D1%84%D0%B0_%D0%A4%D0%BB%D0%B0%D0%B2%D0%B8%D1%8F], но в рамках статьи больший интерес представляет математическая задача, связанная с этой историей. В этой задаче предлагается вычислить, какой элемент останется последним в списке, если из списка последовательно будет удаляться каждый третий элемент, как показано на рисунке 6.

Рисунок 6. Задача Иосифа Флавия
Рисунок 6. Задача Иосифа Флавия

На рисунке 6, если начать отсчет с нулевого индекса, продвигаться по часовой стрелке и уничтожать каждый третий элемент, то останутся только элементы с индексами 1 и 7. Для моделирования этой ситуации можно взять кольцевой связный список или обычный массив. В связном списке удалить элемент гораздо проще, чем найти последний узел, который останется после удаления всех узлов, не удаляя физически элементов из списка.

В представленном алгоритме для решения задачи Иосифа Флавия для поиска последнего «оставшегося в живых» элемента используется двусвязный круговой список. В процессе поиска происходит динамическое удаление элементов из списка и перестройка связей для поддержки целостности списка. Оба варианта решения задачи на языках Си и Python находятся в файлах last_man_standing_task.c и last_man_standing_task.py, упакованных в архив sources.zip, прикрепленный к статье. Реализация алгоритма на языке Python получилась в два раза компактнее, чем на языке Си.

В начало

Использование связных списков в ядре Linux

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

Листинг 5. Элемент связного списка, используемого в ядре Linux
struct mystruct { int data ; struct list_head mylist ; } ;

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

Листинг 6. Два способа инициализации
struct mystruct first = {.data = 10,.mylist = LIST_HEAD_INIT(first.mylist) } ; struct mystruct second ; second.data = 20 ; INIT_LIST_HEAD( & second.mylist ) ;

Метод LIST_HEAD_INIT, используемый в первом варианте, - это следующий макрос:

#define LIST_HEAD_INIT(name) { &(name), &(name) }

В ядре Linux макросы используются вместо обычных функций, так как макросы позволяют сгенерировать более эффективный код, что положительно сказывается на производительности. Во втором варианте используется inline-функция, приведенная в листинге 7.

Листинг 7. Функция для инициализации списка
static inline void INIT_LIST_HEAD(struct list_head list) { list->next = list; list->prev = list; }

Как видно из определения, создаваемый список является двусвязным, так как в нем содержатся указатели на следующий и предыдущий элементы. Использование inline-функции вместо обычной также окажет положительное влияние на производительность. Когда компилятор будет генерировать исполняемый код этой функции, то он поместит его в объектном файле непосредственно в то место, где была вызвана эта функция. Благодаря этому не потребуется тратить ресурсы на вызов функции.

Для создания самого списка, также будет использоваться макрос - LIST_HEAD:

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

А для добавления элементов будет использоваться inline-функция list_add, которая служит «оболочкой» для вызова еще одной функции __list_add.

Листинг 8. Функции для добавления элементов в список
static inline void list_add(struct list_head new, struct list_head head) { __list_add(new, head, head->next); } static inline void __list_add(struct list_head new, struct list_head prev, struct list_head next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; }

Теперь можно добавить элементы в только что созданный список:

list_add ( &first.mylist, &mylinkedlist ) ; list_add ( &second.mylist, &mylinkedlist ) ;

В результате получится связный список, состоящий из 2-х элементов, и указатель на первый элемент в переменной mylinkedlist. Для просмотра содержимого списка или выполнения итерации также используются макросы с целью получения быстрого и эффективного исполняемого кода.

Листинг 9. Макрос для просмотра содержимого списка
#define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos!= (head); \ pos = pos->next)
Листинг 10. Использование макроса для итерации по списку
struct list_head position ; list_for_each ( position, & mylinkedlist ) { printk ("surfing the linked list next = %p and prev = %p\n", position->next, position->prev ); }

Исходный код в листинге 11 суммирует всю информацию, представленную в этой статье. В нем демонстрируется реализация связного списка с помощью макроса define_list, принимающего на вход два параметра - имя списка и тип элемента. Также в листинге 11 объявлены уже знакомые и новые inline-функции, обеспечивающие функциональность связного списка. В методе main объявленные методы и структуры используются для создания связного списка из пяти элементов и последующей итерации по нему.

Листинг 11. Пример объявления и использования связного списка
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> / объявление списка / struct list_head { struct list_head next, prev; }; / статический inline-метод для инициализации списка / static inline void INIT_LIST_HEAD(struct list_head list) { list->next = list; list->prev = list; } / статический inline-метод для вставки элемента в список / static inline void __list_add(struct list_head new, struct list_head prev, struct list_head next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } / статический inline-метод для добавления элементов в конец списка / static inline void list_add_tail(struct list_head new, struct list_head head) { __list_add(new, head->prev, head); } #undef offsetof #ifdef __compiler_offsetof #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) #else #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE )0)->MEMBER) #endif #define container_of(ptr, type, member) ({ \ const typeof( ((type )0)->member ) __mptr = (ptr); \ (type )( (char )__mptr – offsetof(type,member) );}) #define list_entry(ptr, type, member) \ container_of(ptr, type, member) / реализация связного списка с необходимой функциональностью / #define define_list(name, type) \ struct name##_head { \ struct list_head _private; \ }; \ \ static inline type name##_head_first(struct name##_head head) { \ return list_entry(head->_private.next, type, name); \ } \ \ static inline type name##_next(const type node) { \ return list_entry(node->name.next, type, name); \ } \ \ static inline bool name##_is_last(struct name##_head head, const type node) { \ return &head->_private == &node->name; \ } \ \ static inline void name##_init(struct name##_head head) { \ INIT_LIST_HEAD(&head->_private); \ } \ \ static inline void name##_add_tail(struct name##_head head, type new) { \ list_add_tail(&new->name, &head->_private); \ } / объявление элемента списка / struct node { struct list_head node_list; char string; }; / объявление связного списка с заданным именем и нужным типом элементов / define_list(node_list, struct node); struct node new_node(const char string) { struct node ret = malloc(sizeof struct node); ret->string = string; return ret; } / метод main / int main(int argc, char argv[]) { / создание и инициализация списка / struct node_list_head head; node_list_init(&head); / добавление элементов в конец списка / node_list_add_tail(&head, new_node("1")); node_list_add_tail(&head, new_node("2")); node_list_add_tail(&head, new_node("3")); node_list_add_tail(&head, new_node("4")); node_list_add_tail(&head, new_node("5")); / итерация по списку, начиная с первого элемента / for (struct node i = node_list_head_first(&head);!node_list_is_last(&head, i); i = node_list_next(i)) { printf("node: %s\n", i->string); } return 0; }

В начало

Заключение

В данной статье рассматривались связные списки, которые относятся к наиболее важным структурам данных, использующихся в современном программировании. В статье рассматривались как теоретические аспекты со связными списками (задача Иосифа Флавия), так и практическая реализация связных списков в ядре ОС Linux. Для теоретической задачи была разработана реализация на двух различных языках программирования: Си и Python. Однако практическая задача была решена с помощью языка Си, так как в нем имеются такие возможности, как inline-функции и макросы, благодаря использованию которых можно значительно увеличить скорость работы приложения.

В начало

Загрузка



Закрыть ... [X]

Применение связанных списков Работа со структурами данных в языках Си и Python: Часть 3. - IBM
Применение связанных списков Динамический список, его реализация и применение C - CodeNet
Применение связанных списков Создание приложений баз данных в среде Microsoft Visual Basic.Net и
Применение связанных списков Структуры данных в картинках. LinkedList / Хабрахабр
Применение связанных списков Освой самостоятельно C за 24 часа, 4-е издание
Применение связанных списков Применение связанных списков
Применение связанных списков Связный список Википедия
Связанный список Life-Prog Выкройка и пошив юбки по косой Как сшить юбку-солнце и Вышивка лентами. Мастер класс для начинающих пошагово Единая коллекция Цифровых Образовательных Ресурсов Как нарисовать гимнастку поэтапно Какие вязаные шапки в моде? Вяжем с Лана Ви Конкурс для педагогов на «Лучший мастер-класс»