Różnica między tablicą a listą powiązaną

2019

Główna różnica między listą Array i Linked jest związana z ich strukturą. Tablice to struktura danych oparta na indeksach, w której każdy element jest powiązany z indeksem. Z drugiej strony lista powiązań opiera się na referencjach, w których każdy węzeł składa się z danych i odniesień do poprzedniego i następnego elementu.

Zasadniczo tablica to zestaw podobnych obiektów danych przechowywanych w lokalizacjach pamięci sekwencyjnej pod wspólnym nagłówkiem lub nazwą zmiennej.

Lista połączona to struktura danych, która zawiera sekwencję elementów, z których każdy element jest połączony z kolejnym elementem. W elemencie połączonej listy znajdują się dwa pola. Jednym z nich jest pole Data, a inne pole link, pole Data zawiera rzeczywistą wartość do zapisania i przetworzenia. Ponadto pole link zawiera adres następnego elementu danych na połączonej liście. Adres używany do uzyskania dostępu do określonego węzła jest znany jako wskaźnik.

Kolejną istotną różnicą między tablicą a listą połączoną jest to, że macierz ma ustalony rozmiar i musi być zadeklarowana wcześniej, ale lista powiązana nie jest ograniczona do rozmiaru i rozwijana i kontraktowana podczas wykonywania.

Wykres porównania

Podstawa do porównania	Szyk	Połączona lista
Podstawowy	Jest to spójny zestaw ustalonej liczby elementów danych.	Jest to uporządkowany zbiór zawierający zmienną liczbę elementów danych.
Rozmiar	Określone podczas deklaracji.	Nie trzeba określać; rośnie i kurczy się podczas wykonywania.
Przydział pamięci	Lokalizacja elementu jest przydzielana podczas kompilacji.	Położenie elementu jest przypisywane w czasie wykonywania.
Porządek elementów	Przechowywane kolejno	Zapisane losowo
Dostęp do elementu	Bezpośredni lub losowy dostęp, tj. Określ indeks tablicy lub indeks dolny.	Dostęp sekwencyjny, tzn. Przemieszczenie rozpoczynające się od pierwszego węzła na liście przez wskaźnik.
Wstawianie i usuwanie elementu	Powolny względnie przesunięcie jest wymagane.	Łatwiej, szybciej i wydajniej.
Badawczy	Wyszukiwanie binarne i wyszukiwanie liniowe	wyszukiwanie liniowe
Wymagana pamięć	mniej	Więcej
Wykorzystanie pamięci	Nieskuteczny	Wydajny

Definicja tablicy

Tablica jest zdefiniowana jako zbiór określonej liczby jednorodnych elementów lub elementów danych. Oznacza to, że tablica może zawierać tylko jeden typ danych, wszystkie liczby całkowite, wszystkie liczby zmiennoprzecinkowe lub wszystkie znaki. Deklaracja tablicy jest następująca:
int a [10];
Gdzie int określa typ danych lub elementy tablicy typów elementów. "A" to nazwa tablicy, a liczba określona w nawiasach kwadratowych to liczba elementów, które może przechowywać tablica, jest to również nazywane rozmiarem lub długością tablicy.

Przyjrzyjmy się niektórym koncepcjom, które należy zapamiętać na temat tablic:

Poszczególne elementy tablicy można uzyskać, opisując nazwę tablicy, a następnie indeks lub indeks dolny (określający położenie elementu w tablicy) wewnątrz nawiasów kwadratowych. Na przykład, aby pobrać 5 element tablicy, musimy napisać instrukcję a [4].
W każdym przypadku elementy tablicy będą przechowywane w kolejnej lokalizacji pamięci.
Pierwszy element tablicy ma indeks zero [0]. Oznacza to, że pierwszy i ostatni element zostaną określone odpowiednio jako [0] i [9].
Liczba elementów, które mogą być przechowywane w tablicy, tj. Rozmiar tablicy lub jej długość, wynika z następującego równania:
(górna granica - dolna granica) + 1
Dla powyższej tablicy będzie to (9-0) + 1 = 10. Gdzie 0 jest dolną granicą tablicy, a 9 jest górną granicą tablicy.
Tablice można odczytywać lub zapisywać w pętli. Jeśli odczytujemy tablicę jednowymiarową, wymaga ona jednej pętli do odczytu i innej do zapisu (drukowania) tablicy, na przykład:
za. Do odczytywania tablicy
dla (i = 0; i <= 9; i ++)
{scanf ("% d", & a [i]); }
b. Do pisania tablicy
dla (i = 0; i <= 9; i ++)
{printf ("% d", a [i]); }
W przypadku macierzy 2-D wymagałoby to dwóch pętli i podobnie n-wymiarowej tablicy potrzebowałoby pętli n.

Operacje wykonywane na tablicach to:

Przykład

Poniższy program ilustruje odczytywanie i zapisywanie tablicy.

#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 ();
}

Definicja listy połączonej

Lista połączona to szczególna lista niektórych elementów danych połączonych ze sobą. W tym każdy element wskazuje na następny element, który reprezentuje porządek logiczny. Każdy element nazywany jest węzłem, który składa się z dwóch części.

Część INFO, która przechowuje informacje i POINTER, które wskazuje na następny element. Jak wiadomo do przechowywania adresu, mamy unikalne struktury danych w C zwane wskaźnikami. Dlatego drugie pole listy musi być typem wskaźnika.

Rodzaje połączonych list to lista pojedynczo połączona, lista połączona podwójnie, lista połączona okrągłymi, lista podwójnych połączeń podwójnych.

Operacje wykonywane na liście powiązanej to:

Przykład

Poniższy fragment ilustruje utworzenie połączonej listy:

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'));
}

Kluczowe różnice między tablicą a listą połączoną

Tablica jest strukturą danych zawierającą zbiór podobnych elementów danych, podczas gdy lista Łączona jest traktowana jako nieprosta struktura danych zawiera zbiór nieuporządkowanych połączonych elementów zwanych węzłami.
W tablicy elementy należą do indeksów, tzn. Jeśli chcesz dostać się do czwartego elementu, musisz wpisać nazwę zmiennej z jej indeksem lub lokalizacją w nawiasie kwadratowym.
Na liście połączonej musisz jednak zacząć od głowy i przepracować, aż dotrzesz do czwartego elementu.
Dostęp do tablicy elementów jest szybki, natomiast lista łączy zajmuje liniowy czas, więc jest nieco wolniejsza.
Operacje takie jak wstawianie i usuwanie w tablicach zajmują dużo czasu. Z drugiej strony wydajność tych operacji na listach powiązanych jest szybka.
Tablice mają stały rozmiar. Natomiast listy połączone są dynamiczne i elastyczne, mogą rozszerzać i zmniejszać swój rozmiar.
W tablicy pamięć jest przypisywana podczas kompilacji, podczas gdy na liście połączonej jest przydzielana podczas wykonywania lub w czasie wykonywania.
Elementy są przechowywane kolejno w tablicach, podczas gdy są przechowywane losowo na listach połączonych.
Wymóg pamięci jest mniejszy ze względu na faktyczne dane przechowywane w indeksie w tablicy. W związku z tym istnieje zapotrzebowanie na więcej pamięci w listach połączonych z powodu przechowywania dodatkowych, następnych i poprzednich elementów odwołujących się.
Ponadto wykorzystanie pamięci jest nieefektywne w macierzy. Odwrotnie, wykorzystanie pamięci jest wydajne w macierzy.

Wniosek

Array i Linked list to typy struktur danych różniących się między sobą strukturą, metodami dostępu i manipulacji, wymaganiami pamięci i wykorzystaniem. I mają szczególną przewagę i wady w stosunku do jego realizacji. W związku z tym każdy z nich może być użyty zgodnie z potrzebami.