Разница между массивом и связанным списком

• 2019

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

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

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

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

Сравнительная таблица

Основа для сравнения	массив	Связанный список
основной	Это последовательный набор фиксированного количества элементов данных.	Это упорядоченный набор, содержащий переменное количество элементов данных.
Размер	Указано во время декларации.	Не нужно указывать; расти и сжиматься во время исполнения.
Распределение памяти	Расположение элемента выделяется во время компиляции.	Положение элемента назначается во время выполнения.
Порядок элементов	Хранится последовательно	Хранится в случайном порядке
Доступ к элементу	Прямой или случайный доступ, т. Е. Указание индекса массива или индекса.	Последовательный доступ, т. Е. Traverse, начиная с первого узла в списке по указателю.
Вставка и удаление элемента	Медленно, поскольку требуется смещение.	Легче, быстрее и эффективнее.
поиск	Бинарный поиск и линейный поиск	линейный поиск
Требуется память	Меньше	Больше
Использование памяти	неэффективный	эффективное

Определение массива

Массив определяется как набор определенного количества однородных элементов или элементов данных. Это означает, что массив может содержать только один тип данных: все целые числа, все числа с плавающей запятой или все символы. Объявление массива выглядит следующим образом:
int a [10];
Где int указывает тип данных или элементы массива элементов типа. «A» - это имя массива, а число, указанное в квадратных скобках, - это количество элементов, которое может хранить массив, это также называется размером или длиной массива.

Давайте посмотрим на некоторые концепции, которые нужно помнить о массивах:

• Доступ к отдельным элементам массива можно получить, описав имя массива, за которым следует индекс или индекс (определяющий расположение элемента в массиве) в квадратных скобках. Например, чтобы извлечь 5-й элемент массива, нам нужно написать оператор a [4].
• В любом случае элементы массива будут храниться в последовательной ячейке памяти.
• Самый первый элемент массива имеет индекс ноль [0]. Это означает, что первый и последний элемент будут определены как a [0] и a [9] соответственно.
• Количество элементов, которые могут быть сохранены в массиве, т. Е. Размер массива или его длина определяется следующим уравнением:
  (верхняя граница - нижняя граница) + 1
  Для приведенного выше массива это будет (9-0) + 1 = 10. Где 0 - нижняя граница массива, а 9 - верхняя граница массива.
• Массивы могут быть прочитаны или записаны через цикл. Если мы читаем одномерный массив, он требует один цикл для чтения и другой для записи (печати) массива, например:
  а. Для чтения массива
  для (i = 0; i <= 9; i ++)
  {scanf («% d», & a [i]); }
  б. Для написания массива
  для (i = 0; i <= 9; i ++)
  {printf («% d», a [i]); }
• В случае двумерного массива потребовалось бы два цикла, и аналогично n-мерному массиву потребовалось бы n циклов.

Операции над массивами:

1. Создание массива
2. Обход массива
3. Вставка новых элементов
4. Удаление обязательных элементов.
5. Модификация элемента.
6. Слияние массивов

пример

Следующая программа иллюстрирует чтение и запись массива.

#include
#include
void main ()
{
int a[10], i;
printf("Enter the array");
for ( i= 0; i <= 9; i++)
{
scanf ( "%d", &a[ i ] ) ;
}
printf( "Enter the array" );
for (i = 0 ; i <= 9 ; i++)
{
printf ( "%d\n", a[ i ] ) ;
}
getch ();
}

Определение связанного списка

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

Часть INFO, в которой хранится информация, и указатель, указывающий на следующий элемент. Как известно, для хранения адресов у нас есть уникальные структуры данных в Си, называемые указателями. Следовательно, второе поле списка должно быть указателем типа.

Типы связанных списков: Односвязный список, Двусвязный список, Круговой связанный список, Круговой двойной связанный список.

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

1. Создание
2. Пересекая
3. вставка
4. делеция
5. поиск
6. конкатенация
7. дисплей

пример

Следующий фрагмент иллюстрирует создание связанного списка:

struct node
{
int num;
stuct node *next;
}
start = NULL;
void create()
{
typedef struct node NODE;
NODE *p, *q;
char choice;
first = NULL;
do
{
p = (NODE *) malloc (sizeof (NODE));
printf ("Enter the data item\n");
scanf ("%d", & p -> num);
if (p == NULL)
{
q = start;
while (q -> next ! = NULL)
{ q = q -> next
}
p -> next = q -> next;
q -> = p;
}
else
{
p -> next = start;
start = p;
}
printf ("Do you want to continue (type y or n) ? \n");
scanf ("%c", &choice) ;
}
while ((choice == 'y') || (choice == 'Y'));
}

Ключевые различия между массивом и связанным списком

1. Массив - это структура данных, содержащая набор элементов данных аналогичного типа, тогда как Связанный список рассматривается как не примитивная структура данных, содержит набор неупорядоченных связанных элементов, известных как узлы.
2. В массиве элементы принадлежат индексам, т. Е. Если вы хотите попасть в четвертый элемент, вы должны написать имя переменной с указанием ее индекса или местоположения в квадратных скобках.
   В связанном списке, тем не менее, вы должны начать с головы и проходить до тех пор, пока не доберетесь до четвертого элемента.
3. В то время как доступ к массиву элементов быстрый, в то время как связанный список занимает линейное время, он немного медленнее.
4. Такие операции, как вставка и удаление в массивах, занимают много времени. С другой стороны, выполнение этих операций в связанных списках происходит быстро.
5. Массивы имеют фиксированный размер. В отличие от этого, связанные списки являются динамичными и гибкими и могут расширяться и сокращаться.
6. В массиве память выделяется во время компиляции, в то время как в связанном списке она выделяется во время выполнения или выполнения.
7. Элементы хранятся последовательно в массивах, в то время как они хранятся в случайном порядке в связанных списках.
8. Потребность в памяти меньше из-за фактических данных, хранящихся в индексе в массиве. В отличие от этого, требуется больше памяти в связанных списках из-за хранения дополнительных элементов следующего и предыдущего ссылок.
9. Кроме того, использование памяти в массиве неэффективно. И наоборот, использование памяти эффективно в массиве.

Заключение

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