Разница между массивом и связанным списком
Содержание
- Сравнительная таблица
- Определение массива
- Давайте посмотрим на некоторые концепции, которые нужно помнить о массивах:
- Операции над массивами:
- пример
- Определение связанного списка
- Операции, выполняемые в связанном списке:
- пример
- Вывод
Основное различие между массив а также Связанный список С уважением к их структуре. Массивы на основе индекса структура данных, где каждый элемент связан с индексом. С другой стороны, связанный список опирается на Ссылки где каждый узел состоит из данных и ссылок на предыдущий и следующий элемент.
По сути, массив - это набор похожих объектов данных, хранящихся в последовательных ячейках памяти под общим заголовком или именем переменной.
В то время как связанный список представляет собой структуру данных, которая содержит последовательность элементов, где каждый элемент связан со своим следующим элементом. В элементе связанного списка есть два поля. Одним из них является поле данных, а другим - поле ссылки, поле данных содержит фактическое значение, которое будет сохранено и обработано. Кроме того, поле ссылки содержит адрес следующего элемента данных в связанном списке. Адрес, используемый для доступа к конкретному узлу, называется указателем.
Другое существенное различие между массивом и связанным списком состоит в том, что массив имеет фиксированный размер и должен быть объявлен ранее, но связанный список не ограничен размером, расширением и сокращением во время выполнения.
- Сравнительная таблица
- Определение
- Ключевые отличия
- Вывод
Сравнительная таблица
Основа для сравнения | массив | Связанный список |
---|---|---|
основной | Это последовательный набор фиксированного количества элементов данных. | Это упорядоченный набор, содержащий переменное количество элементов данных. |
Размер | Указано во время декларации. | Не нужно указывать; расти и сжиматься во время исполнения. |
Распределение памяти | Расположение элемента выделяется во время компиляции. | Положение элемента назначается во время выполнения. |
Порядок элементов | Хранится последовательно | Хранится в случайном порядке |
Доступ к элементу | Прямой или произвольный доступ, т. Е. Указание индекса массива или индекса. | Последовательный доступ, т. Е. Перемещение по указателю с первого узла в списке. |
Вставка и удаление элемента | Медленно, поскольку требуется смещение. | Легче, быстрее и эффективнее. |
Поиск | Бинарный поиск и линейный поиск | линейный поиск |
Требуется память | Меньше | Больше |
Использование памяти | неэффективный | эффективное |
Определение массива
Массив определяется как набор определенного количества однородных элементов или элементов данных. Это означает, что массив может содержать только один тип данных: все целые числа, все числа с плавающей запятой или все символы. Объявление массива выглядит следующим образом:
int a;
Где int указывает тип данных или элементы массива элементов типа. «A» - это имя массива, а число, указанное в квадратных скобках, - это количество элементов, которое может хранить массив, это также называется размером или длиной массива.
Давайте посмотрим на некоторые концепции, которые нужно помнить о массивах:
- Доступ к отдельным элементам массива можно получить, описав имя массива, за которым следует индекс или индекс (определяющий расположение элемента в массиве) в квадратных скобках. Например, чтобы извлечь 5-й элемент массива, нам нужно написать оператор a.
- В любом случае элементы массива будут храниться в последовательной ячейке памяти.
- Самый первый элемент массива имеет нулевой индекс. Это означает, что первый и последний элемент будут указаны как a и a соответственно.
- Количество элементов, которые могут быть сохранены в массиве, то есть размер массива или его длина определяется следующим уравнением:
(верхняя граница - нижняя граница) + 1
Для приведенного выше массива это будет (9-0) + 1 = 10. Где 0 - нижняя граница массива, а 9 - верхняя граница массива. - Массивы могут быть прочитаны или записаны через цикл. Если мы читаем одномерный массив, он требует один цикл для чтения и другой для записи (извлечения) массива, например:
а. Для чтения массива
для (i = 0; i <= 9; i ++)
{scanf («% d», & a); }
б. Для написания массива
для (i = 0; i <= 9; i ++)
{f («% d», а); } - В случае двумерного массива потребовалось бы два цикла, и аналогично n-мерному массиву потребовалось бы n циклов.
Операции над массивами:
- Создание массива
- Обход массива
- Вставка новых элементов
- Удаление обязательных элементов.
- Модификация элемента.
- Слияние массивов
пример
Следующая программа иллюстрирует чтение и запись массива.
#включают
#включают
пустая функция ()
{
int a, i;
f («Ввести массив»);
для (i = 0; i <= 9; i ++)
{
scanf ("% d", & a);
}
f («Ввести массив»);
для (i = 0; i <= 9; i ++)
{
f ("% d n", а);
}
getch ();
}
Определение связанного списка
Связанный список - это определенный список некоторых элементов данных, связанных друг с другом. В этом каждый элемент указывает на следующий элемент, который представляет логический порядок. Каждый элемент называется узлом, который состоит из двух частей.
Часть INFO, в которой хранится информация, и указатель, указывающий на следующий элемент. Как известно, для хранения адресов у нас есть уникальные структуры данных в Си, называемые указателями. Следовательно, второе поле списка должно быть указателем типа.
Типы связанных списков: Односвязный список, Двусвязный список, Круговой связанный список, Круговой двойной связанный список.
Операции, выполняемые в связанном списке:
- Создание
- Обход
- вставка
- делеция
- Поиск
- конкатенация
- дисплей
пример
Следующий фрагмент иллюстрирует создание связанного списка:
структура узла
{
int num;
узел Stuct * следующий;
}
начало = NULL;
void create ()
{
typedef struct node NODE;
УЗЕЛ * p, * q;
выбор символа;
first = NULL;
делать
{
p = (NODE *) malloc (sizeof (NODE));
f («Введите элемент данных n»);
scanf ("% d", & p -> num);
если (p == NULL)
{
q = начало;
while (q -> next! = NULL)
{q = q -> далее
}
p -> следующий = q -> следующий;
q -> = p;
}
еще
{
р -> следующий = начало;
начало = р;
}
f («Хотите продолжить (введите y или n)? n»);
scanf ("% c", & choice);
}
while ((выбор == у) || (выбор == у));
}
- Массив - это структура данных, содержащая набор элементов данных аналогичного типа, тогда как Связанный список рассматривается как не примитивная структура данных, содержит набор неупорядоченных связанных элементов, известных как узлы.
- В массиве элементы принадлежат индексам, т. Е. Если вы хотите попасть в четвертый элемент, вы должны написать имя переменной с ее индексом или местоположением в квадратных скобках.
В связанном списке, тем не менее, вы должны начать с головы и проходить до тех пор, пока не доберетесь до четвертого элемента. - В то время как доступ к массиву элементов быстрый, в то время как связанный список занимает линейное время, он немного медленнее.
- Такие операции, как вставка и удаление в массивах, занимают много времени. С другой стороны, выполнение этих операций в связанных списках происходит быстро.
- Массивы имеют фиксированный размер. В отличие от этого, связанные списки являются динамичными и гибкими и могут расширяться и сокращаться.
- В массиве память выделяется во время компиляции, в то время как в связанном списке она выделяется во время выполнения или выполнения.
- Элементы хранятся последовательно в массивах, в то время как они хранятся в случайном порядке в связанных списках.
- Потребность в памяти меньше из-за фактических данных, хранящихся в индексе в массиве. В отличие от этого, требуется больше памяти в связанных списках из-за хранения дополнительных элементов следующего и предыдущего ссылок.
- Кроме того, использование памяти в массиве неэффективно. И наоборот, использование памяти эффективно в массиве.
Вывод
Массив и связанные списки - это типы структур данных, различающиеся по своей структуре, методам доступа и манипулирования, требованиям к памяти и использованию. И имеют определенные преимущества и недостатки по сравнению с его реализацией. Следовательно, любой из них может быть использован по необходимости.