Рекомендуем, 2020

Выбор редакции

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

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

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

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

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

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

Основа для сравнениямассивСвязанный список
основнойЭто последовательный набор фиксированного количества элементов данных.Это упорядоченный набор, содержащий переменное количество элементов данных.
РазмерУказано во время декларации.Не нужно указывать; расти и сжиматься во время исполнения.
Распределение памятиРасположение элемента выделяется во время компиляции.Положение элемента назначается во время выполнения.
Порядок элементовХранится последовательноХранится в случайном порядке
Доступ к элементуПрямой или случайный доступ, т. Е. Указание индекса массива или индекса.Последовательный доступ, т. Е. 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. Кроме того, использование памяти в массиве неэффективно. И наоборот, использование памяти эффективно в массиве.

Заключение

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

Top