Empfohlen, 2019

Tipp Der Redaktion

Unterschied zwischen Array und verknüpfter Liste

Der Hauptunterschied zwischen Array und verknüpfter Liste besteht in ihrer Struktur. Arrays sind eine auf Daten basierende Datenstruktur, bei der jedes Element einem Index zugeordnet ist. Auf der anderen Seite beruht die verknüpfte Liste auf Referenzen, bei denen jeder Knoten aus den Daten und den Referenzen zum vorherigen und zum nächsten Element besteht.

Grundsätzlich ist ein Array ein Satz ähnlicher Datenobjekte, die an aufeinanderfolgenden Speicherstellen unter einer gemeinsamen Überschrift oder einem Variablennamen gespeichert sind.

Eine verkettete Liste ist eine Datenstruktur, die eine Folge der Elemente enthält, bei denen jedes Element mit dem nächsten Element verknüpft ist. Ein Element einer verknüpften Liste enthält zwei Felder. Eines ist das Datenfeld und das andere ist das Linkfeld. Das Datenfeld enthält den tatsächlichen Wert, der gespeichert und verarbeitet werden soll. Außerdem enthält das Link-Feld die Adresse des nächsten Datenelements in der verknüpften Liste. Die Adresse, die für den Zugriff auf einen bestimmten Knoten verwendet wird, wird als Zeiger bezeichnet.

Ein weiterer wesentlicher Unterschied zwischen einem Array und einer verknüpften Liste besteht darin, dass Array eine feste Größe hat und vorher deklariert werden muss. Die verknüpfte Liste ist jedoch nicht auf die Größe und Erweiterung sowie die Kontraktion während der Ausführung beschränkt.

Vergleichstabelle

VergleichsgrundlageArrayVerknüpfte Liste
BasicEs ist eine konsistente Menge einer festen Anzahl von Datenelementen.Es ist ein geordneter Satz mit einer variablen Anzahl von Datenelementen.
GrößeWird bei der Deklaration angegeben.Keine Notwendigkeit zu spezifizieren; während der Ausführung wachsen und schrumpfen.
SpeicherzuordnungDie Position des Elements wird während der Kompilierzeit zugewiesen.Elementposition wird während der Laufzeit zugewiesen.
Reihenfolge der ElementeNacheinander gelagertZufällig gespeichert
Zugriff auf das ElementDirekt oder nach dem Zufallsprinzip, dh Geben Sie den Array-Index oder Index an.Sequentieller Zugriff, dh Traverse, beginnend mit dem ersten Knoten in der Liste durch den Zeiger.
Einfügen und Löschen eines ElementsLangsam relativ, da ein Schalten erforderlich ist.Einfacher, schneller und effizienter.
SuchenBinäre Suche und lineare Suchelineare Suche
Speicher benötigtWenigerMehr
SpeicherauslastungUnwirksamEffizient

Definition von Array

Ein Array ist definiert als eine Menge einer bestimmten Anzahl homogener Elemente oder Datenelemente. Dies bedeutet, dass ein Array nur einen Datentyp enthalten kann, entweder alle Ganzzahlen, alle Gleitkommazahlen oder alle Zeichen. Die Deklaration eines Arrays lautet wie folgt:
int a [10];
Dabei gibt int den Datentyp oder die Typelemente an, die Array speichert. "A" ist der Name eines Arrays und die in eckigen Klammern angegebene Anzahl ist die Anzahl der Elemente, die ein Array speichern kann. Dies wird auch als Größe oder Länge des Arrays bezeichnet.

Lassen Sie uns einige der Konzepte betrachten, die bei Arrays zu beachten sind:

  • Auf die einzelnen Elemente eines Arrays kann zugegriffen werden, indem der Name des Arrays beschrieben wird, gefolgt von Index oder Index (Bestimmen der Position des Elements im Array) in den eckigen Klammern. Um beispielsweise das fünfte Element des Arrays abzurufen, müssen Sie eine Anweisung a [4] schreiben.
  • In jedem Fall werden die Elemente eines Arrays an einem aufeinanderfolgenden Speicherplatz gespeichert.
  • Das allererste Element des Arrays hat den Index Null [0]. Es bedeutet, dass das erste und das letzte Element als [0] bzw. [9] angegeben werden.
  • Die Anzahl der Elemente, die in einem Array gespeichert werden können, dh die Größe eines Arrays oder seine Länge, ergibt sich aus der folgenden Gleichung:
    (obere Grenze-untere Grenze) + 1
    Für das obige Array wäre es (9-0) + 1 = 10. Dabei ist 0 die Untergrenze des Arrays und 9 die Obergrenze des Arrays.
  • Arrays können durch die Schleife gelesen oder geschrieben werden. Wenn wir das eindimensionale Array lesen, ist eine Schleife zum Lesen und eine andere zum Schreiben (Drucken) des Arrays erforderlich. Beispiel:
    ein. Zum Lesen eines Arrays
    für (i = 0; i <= 9; i ++)
    {scanf ("% d", & a [i]); }
    b. Zum Schreiben eines Arrays
    für (i = 0; i <= 9; i ++)
    {printf ("% d", a [i]); }
  • Im Falle eines 2D-Arrays würde es zwei Schleifen erfordern, und auf ähnliche Weise würde ein n-dimensionales Array n Schleifen benötigen.

Operationen, die an Arrays durchgeführt werden, sind:

  1. Erstellung eines Arrays
  2. Ein Array durchlaufen
  3. Einfügen neuer Elemente
  4. Löschen von erforderlichen Elementen.
  5. Änderung eines Elements
  6. Zusammenführen von Arrays

Beispiel

Das folgende Programm veranschaulicht das Lesen und Schreiben des Arrays.

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

Definition der verknüpften Liste

Verknüpfte Liste ist eine bestimmte Liste einiger Datenelemente, die miteinander verknüpft sind. In diesem Punkt zeigt jedes Element auf das nächste Element, das die logische Reihenfolge darstellt. Jedes Element wird als Knoten bezeichnet, der aus zwei Teilen besteht.

INFO-Teil, der die Informationen speichert, und POINTER, der auf das nächste Element zeigt. Wie Sie wissen, haben wir eine eindeutige Datenstruktur in C, die als Zeiger bezeichnet wird. Daher muss das zweite Feld der Liste ein Zeigertyp sein.

Typen von verknüpften Listen sind einfach verknüpfte Liste, doppelt verknüpfte Liste, zirkuläre verknüpfte Liste, zirkulare verknüpfte Liste.

In der verknüpften Liste ausgeführte Vorgänge sind:

  1. Schaffung
  2. Überqueren
  3. Einfügung
  4. Streichung
  5. Suchen
  6. Verkettung
  7. Anzeige

Beispiel

Der folgende Ausschnitt veranschaulicht die Erstellung einer verknüpften Liste:

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

Hauptunterschiede zwischen Array und verknüpfter Liste

  1. Ein Array ist die Datenstruktur, die eine Sammlung ähnlicher Datenelemente enthält, während die verknüpfte Liste als nicht primitive Datenstruktur betrachtet wird. Sie enthält eine Sammlung ungeordneter verknüpfter Elemente, die als Knoten bezeichnet werden.
  2. Im Array gehören die Elemente zu Indizes, dh wenn Sie in das vierte Element einsteigen möchten, müssen Sie den Variablennamen mit seinem Index oder seiner Position in die eckige Klammer schreiben.
    In einer verknüpften Liste müssen Sie jedoch vom Kopf aus beginnen und sich durcharbeiten, bis Sie zum vierten Element gelangen.
  3. Der Zugriff auf ein Elementarray ist zwar schnell, während die verknüpfte Liste eine lineare Zeit benötigt, sie ist jedoch etwas langsamer.
  4. Operationen wie das Einfügen und Löschen in Arrays benötigen viel Zeit. Auf der anderen Seite ist die Leistung dieser Vorgänge in verknüpften Listen schnell.
  5. Arrays haben eine feste Größe. Im Gegensatz dazu sind verknüpfte Listen dynamisch und flexibel und können ihre Größe vergrößern und verkleinern.
  6. In einem Array wird Speicher während der Kompilierungszeit zugewiesen, während er in einer verknüpften Liste während der Ausführung oder Laufzeit zugewiesen wird.
  7. Elemente werden fortlaufend in Arrays gespeichert, während sie in verknüpften Listen zufällig gespeichert werden.
  8. Der Speicherbedarf ist geringer, da die tatsächlichen Daten im Index des Arrays gespeichert sind. Im Gegensatz dazu besteht aufgrund der Speicherung zusätzlicher, nächster und früherer Referenzierungselemente mehr Speicherplatz in verknüpften Listen.
  9. Außerdem ist die Speicherauslastung in dem Array ineffizient. Umgekehrt ist die Speicherauslastung im Array effizient.

Fazit

Array- und Linked-Listen sind die Arten von Datenstrukturen, die sich in ihrer Struktur, den Zugriffs- und Manipulationsmethoden, dem Speicherbedarf und der Nutzung unterscheiden. Und haben besondere Vorteile und Nachteile gegenüber der Implementierung. Folglich kann einer von beiden nach Bedarf verwendet werden.

Top