Загрузка...
 
Печать

Связные списки (Linked lists)


Image
Рис.1 Разница между однонаправленным (односвязным) и двунаправленным (двухсвязным) связными списками


  • Являются одними из простейших видов динамических данных.
  • Являются фундаментальным понятием в игрокодинге.
  • Лежат в основе создания главного игрового цикла.

Существует множество различных способов хранения данных в приложении. Ты можешь сохранять данные как отдельные переменные, но со временем ими становится всё сложнее управлять. Другой вариант - сохранять все данные в массивах, которые по сути являются списками фиксированной длины с предопределённым типом данных. Этот способ позволяет намного успешнее управлять данными, но сильно проигрывает в возможностях расширения. Если ты сначала создал массив с 5 элементами, а затем решил, что тебе нужно хранить 8 элементов, тебе необходимо изменить размер массива и перекомпилировать исходный код (если только ты не используешь специальный класс для работы с массивами, поддерживающий изменение размеров).
Один из лучших способов хранить данные приложения - это разместить их в специальном контейнере, соответствующем типу данных, называемом связный список(external link) (Linked list). Связный список во многом схож с обычным массивом, за исключением того что он может намного быстрее и эффективнее изменять свой размер прямо во время выполнения. Связный список можно сравнить с поездом, к которому прицеплены несколько вагонов. Каждый вагон прицеплен к другому с двух сторон (за исключением последнего). Несколько вагонов, сцепленных друг с другом, образуют продолжающуюся цепь. В ней есть голова (локомотив) и есть хвост (последний вагон). Вагоны могут цепляться в разном порядке, новые могут быть добавлены, а старые - отцеплены (удалены). Всё это время поезд представляет собой, продолжающуюся от головы до хвоста, цепь. С точки зрения компьютерного программирования, существуют 2 основных типа связных списков:
Однонаправленный (односвязный) Содержит элементы, которые устанавливают связь только с впереди идущим элементом. Использует меньше памяти, т.к. каждый элемент хранит в себе только 1 указатель на впереди идущий элемент списка. (См. Рис.1) В то же время, в него труднее добавлять (вставлять) новые элементы, т.к. сперва необходимо траверсировать ("отмотать") список для определения предыдущего элемента и установления связей (укзателей).
Двунаправленный (двусвязный) Содержит элементы, которые устанавливают связь как с впереди идущим, так и с предыдущим элементом. Применяется намного чаще, чем односвязный список. Каждый элемент устанавливает связь с предыдущим и впереди идущим элементами. Это позволяет намного проще вставлять новые элементы в любой из участков списка. Вдобавок, сортировка таких списков происходит намного быстрее.

Закрыть
noteПримечание

У связных списков есть один недостаток, по сравнению с другими хранилищами данных (например массивами). В связных списках гораздо сложнее определить отдельные элементы, т.к. для этого необходимо оттрассировать весь список и проверить каждый элемент. Это не проблема для списков небольшого размера. Но если ты работаешь со связным списком, который содержит тысячи элементов, и тебе нужно отыскать один из них, поиск может занять какое-то время, особенно если разыскиваемый элемент расположен в конце списка. Эффект задержки в расчёте может нарастать очень быстро, если ты ищешь элементы в большом связном списке несколько раз за кадр.
Если ты работаешь со списками фиксированного размера или заранее знаешь максимальное число элементов, тогда гораздо рациональнее использовать массивы, которые дадут возможность быстро найти необходимые элементы, опираясь на их индексы в массиве.


Последние изменения страницы Четверг 23 / Июнь, 2022 11:41:32 MSK

Последние комментарии wiki

No records to display

Search Wiki Page

Точное совпадение

Категории

|--> C#
|--> C++