русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Связанный список

Связанный список в программировании - одна из важнейших структур, данных, в которой элементы линейно упорядочены, но порядок определяется не номерами элементов, а указателями, входящих в состав элементов списка и указывают на следующий за данным элемент или на следующий и предыдущий элементы. Список имеет «голову» - первый элемент и «хвост» - последний элемент.

Связанные списки имеют серию преимуществ по сравнению с массивами. В частности, в них гораздо эффективнее (за время О (1), т.е. независимо от количества элементов) выполняются процедуры добавления и удаления элементов. Зато, массивы намного лучше в операциях, требующих непосредственного доступа к каждому элементу, что в случае со связанными списками невозможно и требует последовательного перебора всех элементов, предшествующих данному.

Разновидности связанных списков

Односторонне связанные списки

В одностороннем связанном списке, который является простейшим видом связанных списков, каждый элемент состоит из двух полей: data или данных, и указателя next на следующий элемент. Если указатель не указывает на другой элемент (иначе: next = NULL), то считается, что данный элемент - последний в списке.

Двусторонний связанный список

В Двустороннем связанном списке, элемент состоит из трех полей - указателя на предыдущий элемент prev, поля данных data и указателя next на следующий элемент. Если prev = NULL, то у элемента нет предшественника (т.е. он является «головой» списка), если next = NULL, то у него нет преемника («хвост» списка).

Кольцевой список

В кольцевом списке первый и последний элемент связаны. То есть, поле prev головы списка указывает на хвост списка, а поле next хвоста списка указывает на голову списка.

Применение списков

Списки интенсивно применяются в программировании как самостоятельные структуры. Также на их основе могут строиться более сложные структуры данных, такие как деревья. На базе списков также могут быть реализованы стеки и очереди.

Преимущества и недостатки

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

Связанные списки и массивы

Списки имеют некоторые преимущества над массивами. Они достаточно эффективны в отношении операций добавления или удаления элемента в произвольном месте списка, выполняя их за постоянное время, тогда как массивы для этого требуют времени O (n), то есть время возрастает с ростом количества элементов массива.

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

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

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

Двустороннее и одностороннее связывание

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

Просмотров: 6128

Оглавление: Компьютерная графика и информация в компьютерной сфере


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.