Array och Länkad lista är de två sätten att organisera data i minnet. Innan du förstår skillnaderna mellan Array och den Länkad lista , vi tittar först vid en array och en länkad lista .
vad gör ravel i python
Vad är en array?
En datastruktur som innehåller element av samma typ. En datastruktur är ett sätt att organisera data; en array är en datastruktur eftersom den organiserar data sekventiellt. En array är en stor minnesbit där minnet är uppdelat i små-små block, och varje block kan lagra något värde.
Anta att vi har skapat en array som består av 10 värden, då kommer varje block att lagra värdet av en heltalstyp. Om vi försöker lagra värdet i en array av olika typer, så är det inte en korrekt array och kommer att ge ett kompileringsfel.
Deklaration av array
En matris kan deklareras som:
data_type name of the array[no of elements]
För att deklarera en array måste vi först ange typen av array och sedan arrayens namn. Inom hakparenteserna måste vi ange antalet element som vår array ska innehålla.
Låt oss förstå genom ett exempel.
int a[5];
I ovanstående fall har vi deklarerat en array med 5 element med ' a ' namn på en heltal data typ.
Vad är länkad lista?
En länkad lista är samlingen av noder som är slumpmässigt lagrade. Varje nod består av två fält, dvs. data och länk . Här är data värdet som lagras vid den specifika noden, och länken är pekaren som håller adressen till nästa nod.
Skillnader mellan Array och Linked list
Vi kan inte säga vilken datastruktur som är bättre, dvs array eller länkad lista . Det kan finnas en möjlighet att en datastruktur är bättre för en typ av krav, medan den andra datastrukturen är bättre för en annan typ av krav. Det finns olika faktorer som vad är de frekventa operationerna som utförs på datastrukturen eller storleken på data, och andra faktorer som också ligger till grund för valet av datastrukturen. Nu kommer vi att se några skillnader mellan arrayen och den länkade listan baserat på några parametrar.
amplitudmodulering
1. Kostnad för att komma åt ett element
I fallet med en array, oavsett storleken på en array, tar en array en konstant tid för att komma åt ett element. I en array lagras elementen på ett sammanhängande sätt, så om vi känner till elementets basadress kan vi enkelt få adressen till vilket element som helst i en array. Vi måste utföra en enkel beräkning för att få adressen till ett element i en array. Så att komma åt elementet i en array är O(1) när det gäller tidskomplexitet.
I den länkade listan lagras inte elementen på ett sammanhängande sätt. Den består av flera block, och varje block representeras som en nod. Varje nod har två fält, dvs ett är för datafältet, och ett annat lagrar adressen till nästa nod. För att hitta någon nod i den länkade listan måste vi först bestämma den första noden som kallas huvudnoden. Om vi måste hitta den andra noden i listan måste vi gå från den första noden, och i värsta fall, för att hitta den sista noden, kommer vi att korsa alla noder. Det genomsnittliga fallet för att komma åt elementet är O(n).
Vi drar slutsatsen att kostnaden för att komma åt ett element i array är mindre än den länkade listan. Därför, om vi har något krav för att komma åt elementen, är array ett bättre val.
2. Kostnad för att infoga ett element
Det kan finnas tre scenarier i infogningen:
I fallet med en länkad lista, för att infoga ett element i början av den länkade listan, kommer vi att skapa en ny nod, och adressen till den första noden läggs till i den nya noden. På så sätt blir den nya noden den första noden. Så tidskomplexiteten är inte proportionell mot storleken på listan. Tidskomplexiteten skulle vara konstant, dvs O(1).
Om arrayen inte är full kan vi direkt lägga till det nya elementet genom indexet. I detta fall skulle tidskomplexiteten vara konstant, dvs O(1). Om arrayen är full måste vi först kopiera arrayen till en annan array och lägga till ett nytt element. I detta fall skulle tidskomplexiteten vara O(n).
För att infoga ett element i slutet av den länkade listan måste vi gå igenom hela listan. Om den länkade listan består av n element, skulle tidskomplexiteten vara O(n).
Anta att vi vill infoga elementet vid i:etthpositionen för arrayen; vi måste flytta n/2-elementen åt höger. Därför är tidskomplexiteten proportionell mot antalet element. Tidskomplexiteten skulle vara O(n) för genomsnittsfallet.
j-knappen
I fallet med länkad lista måste vi gå till den positionen där vi måste infoga det nya elementet. Även om vi inte behöver utföra någon form av växling, utan vi måste gå till n/2 position. Tidsåtgången är proportionell mot antalet n element, och tidskomplexiteten för det genomsnittliga fallet skulle vara O(n).
Den resulterande länkade listan är:
Implementeringen av en array är enkel jämfört med den länkade listan. När du skapar ett program med hjälp av en länkad lista är programmet mer benäget att få fel som segmenteringsfel eller minnesläcka. Så mycket försiktighet måste tas när du skapar ett program i den länkade listan.
Den länkade listan är dynamisk i storlek medan arrayen är statisk. Här betyder statisk inte att vi inte kan bestämma storleken under körningstiden, men vi kan inte ändra den när storleken väl har bestämts.
3. Minneskrav
Eftersom elementen i en array lagras i ett sammanhängande minnesblock har arrayen fast storlek. Anta att vi har en array av storlek 7, och arrayen består av 4 element, då är resten av utrymmet oanvänt. Minnet som upptas av de 7 elementen:
Minnesutrymme = 7*4 = 28 byte
Där 7 är antalet element i en array och 4 är antalet byte av en heltalstyp.
I händelse av länkad lista finns det inget oanvänt minne utan det extra minnet upptas av pekarvariablerna. Om data är av heltalstyp, är det totala minnet som upptas av en nod 8 byte, dvs 4 byte för data och 4 byte för pekarvariabel. Om den länkade listan består av 4 element, skulle minnesutrymmet som upptas av den länkade listan vara:
webbdrivrutin
Minnesutrymme = 8*4 = 32 byte
Den länkade listan skulle vara ett bättre val om datadelen är större i storlek. Anta att datan är på 16 byte. Minnesutrymmet som tas upp av arrayen skulle vara 16*7=112 byte medan den länkade listan upptar 20*4=80, här har vi specificerat 20 byte som 16 byte för storleken på data plus 4 byte för pekarvariabeln. Om vi väljer den större datastorleken, skulle den länkade listan förbruka mindre minne; annars beror det på de faktorer som vi använder för att bestämma storleken.
Låt oss titta på skillnaderna mellan arrayen och den länkade listan i tabellform.
| Array | Länkad lista |
|---|---|
| En array är en samling element av liknande datatyp. | En länkad lista är en samling objekt som kallas en nod där noden består av två delar, dvs data och adress. |
| Arrayelement lagras på en sammanhängande minnesplats. | Länkade listelement kan lagras var som helst i minnet eller slumpmässigt. |
| Array fungerar med ett statiskt minne. Här betyder statiskt minne att minnesstorleken är fast och inte kan ändras under körtiden. | Den länkade listan fungerar med dynamiskt minne. Här innebär dynamiskt minne att minnesstorleken kan ändras vid körning enligt våra krav. |
| Matriselement är oberoende av varandra. | Länkade listelement är beroende av varandra. Eftersom varje nod innehåller adressen till nästa nod för att komma åt nästa nod, måste vi komma åt dess föregående nod. |
| Array tar längre tid när du utför någon operation som infogning, radering, etc. | Länkad lista tar mindre tid när du utför någon operation som infogning, radering, etc. |
| Det går snabbare att komma åt vilket element som helst i en array eftersom elementet i en array kan nås direkt via indexet. | Att komma åt ett element i en länkad lista är långsammare eftersom det börjar gå från det första elementet i den länkade listan. |
| I fallet med en array tilldelas minne vid kompilering. | I fallet med en länkad lista tilldelas minne vid körning. |
| Minnesanvändningen är ineffektiv i arrayen. Till exempel, om storleken på arrayen är 6 och arrayen endast består av 3 element kommer resten av utrymmet att vara oanvänt. | Minnesanvändning är effektiv i fallet med en länkad lista eftersom minnet kan allokeras eller avallokeras vid körning enligt våra krav. |