Развернутый связанный список
- Развернутый связанный список
-
Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).
Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при очень малом размере логических элементов и большом их количестве — так, односвязный список из 10000 четырёхбайтовых целых чисел при четырёхбайтовой же адресации памяти занимает 40000 дополнительных байт под адреса, если же объединить числа в массивы по 100, расход памяти упадёт до 400 байт.
Прирост производительности достигается за счёт того, что большая часть операций проводится над относительно небольшими массивами данных, которые обычно целиком помещаются в кэш-памяти. Благодаря этому быстродействие программы может быть даже выше, чем при работе с обычными массивами. В развёрнутый список легко можно добавлять новые элементы, без необходимости переписывать весь массив, что является большой проблемой при работе с обычными массивами.
При реализации необходимо тщательно выбирать размер "блока" (количество логических элементов в физическом). При слишком большом размере блока список начинает страдать от тех же проблем, что и обыкновенный массив: долгая вставка элементов в начало или середину, долгое удаление элементов оттуда же, и т.п.
Ссылки
Wikimedia Foundation.
2010.
Смотреть что такое "Развернутый связанный список" в других словарях:
Нейпоген — Действующее вещество ›› Филграстим* (Filgrastim*) Латинское название Neupogen АТХ: ›› L03AA02 Филграстим Фармакологическая группа: Стимуляторы гемопоэза Нозологическая классификация (МКБ 10) ›› D70 Агранулоцитоз ›› D71 Функциональные нарушения… … Словарь медицинских препаратов
КАЗАНСКАЯ ИКОНА БОЖИЕЙ МАТЕРИ — (празд. 8 июля, 22 окт.), одна из главных русских святынь, связанная с важнейшими событиями истории Российского гос ва и РПЦ XVI нач. XXI в. Явилась в Казани 8 июля 1579 г., в царствование Иоанна IV Васильевича Грозного. Списки иконы получили… … Православная энциклопедия
ИУСТИН ФИЛОСОФ — [греч. ᾿Ιουστῖνος Θιλόσοφος] (кон. I нач. II в., г. Флавия Неаполь 165, Рим), мч. (пам. 1 июня), апологет, отец Церкви. Жизнь Мч. Иустин Философ. Роспись ц. свт. Николая мон ря Ставроникита, Афон. Мастера Феофан Критский и Симеон. 1546 г. Мч.… … Православная энциклопедия
Барак Обама — (Barack Obama) Барак Обама это 44 й президент Соединенных Штатов Америки, первый темнокожий президент на этом посту Биография президента США Барака Обамы, в том числе его политическая карьера, деятельность в сенате штата Иллинойс и затем в Сенате … Энциклопедия инвестора
ИУДА — [греч. ᾿Ιούδας] (I в.), брат Господень (пам. 19 июня; пам. зап. 28 окт.), отождествляется в правосл. традиции с апостолами от 12 Иудой Иаковлевым и Фаддеем Леввеем и с автором Иуды послания. В НЗ существует 4 варианта списков 12 апостолов (Мф 10 … Православная энциклопедия
СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК — (СССР, Союз ССР, Советский Союз) первое в истории социалистич. гос во. Занимает почти шестую часть обитаемой суши земного шара 22 млн. 402,2 тыс. км2. По численности населения 243,9 млн. чел. (на 1 янв. 1971) Сов. Союзу принадлежит 3 е место в… … Советская историческая энциклопедия
Купренил — Действующее вещество ›› Пеницилламин* (Penicillamine*) Латинское название Cuprenyl АТХ: ›› M01CC01 Пеницилламин Фармакологические группы: Иммунодепрессанты ›› Детоксицирующие средства, включая антидоты Нозологическая классификация (МКБ 10) ›› E83 … Словарь медицинских препаратов
Польский поход РККА — Не следует путать с Советско польской войной. Польский поход РККА (1939) Вторая мировая война Дата 17 29 сентября 1939 Место … Википедия
«ЕДИНОРОДНЫЙ СЫНЕ» — [греч. ῾Ο μονοϒενὴς Υἱός̇; слав. ], тропарь, выражающий учение Церкви о домостроительстве спасения; в совр. правосл. богослужении поется во время полной евхаристической литургии в конце 2 го антифона, а также входит в состав чина изобразительных … Православная энциклопедия
