Verschil Tussen Singly Linked List en Doubly Linked List

Anonim

Enkel gekoppelde lijst vs dubbele gekoppelde lijst

Gelinkte lijst is een lineaire datastructuur die gebruikt wordt om een ​​verzameling gegevens op te slaan. Een gekoppelde lijst wijst geheugen afzonderlijk in zijn eigen blok van geheugen en de algemene structuur wordt verkregen door deze elementen als koppelingen in een ketting te koppelen. Een alleen gekoppelde lijst bestaat uit een reeks knooppunten en elk knooppunt heeft een verwijzing naar het volgende knooppunt in de reeks. Een dubbel gekoppelde lijst bevat een reeks knooppunten waarin elk knooppunt een verwijzing naar het volgende knooppunt bevat, evenals het vorige knooppunt.

Enkel gekoppelde lijst

Elk element in een afzonderlijk gekoppelde lijst heeft twee velden zoals getoond in Figuur 1. Het gegevensveld bevat de actuele gegevens opgeslagen en het volgende veld bevat de verwijzing naar het volgende element in de ketting. Het eerste element van de gekoppelde lijst is opgeslagen als de kop van de gekoppelde lijst.

Figuur 2 geeft een afzonderlijk gekoppelde lijst weer met drie elementen. Elk element slaat zijn gegevens op en alle elementen behalve de laatste bevatten een verwijzing naar het volgende element. Laatste element heeft een nulwaarde in het volgende veld. Elk element in de lijst kan worden geopend door aan het hoofd te beginnen en de volgende aanwijzer te volgen totdat u het benodigde element voldoet.

Dubbele gekoppelde lijst

Elk element in een dubbel gekoppelde lijst heeft drie velden, zoals weergegeven in Figuur 3. Net als bij een gekoppelde lijst houdt het gegevensveld de actuele gegevens opgeslagen en wordt in het volgende veld de verwijzing naar het volgende element in de ketting. Daarnaast bevat het vorige veld de verwijzing naar het vorige element in de keten. Het eerste element van de gekoppelde lijst is opgeslagen als de kop van de gekoppelde lijst.

Figuur 4 toont een dubbel gekoppelde lijst met drie elementen. Alle tussenliggende elementen bewaren verwijzingen naar de eerste en vorige elementen. Het laatste element in de lijst heeft een nulwaarde in het volgende veld en het eerste element in de lijst heeft een nulwaarde in het vorige veld. Dubbele gekoppelde lijst kan doorgevoerd worden door de volgende referenties in elk element te volgen en kan ook achteruit worden doorgevoerd met behulp van de vorige referenties in elk element.

Wat is het verschil tussen Singly Linked List en Doubly Linked List?

Elk element in de afzonderlijk gekoppelde lijst bevat een verwijzing naar het volgende element in de lijst, terwijl elk element in de dubbel gekoppelde lijst verwijzingen bevat naar het volgende element, evenals het vorige element in de lijst. Dubbel gekoppelde lijsten vereisen meer ruimte voor elk element in de lijst en elementaire bewerkingen, zoals invoeging en verwijdering, zijn complexer omdat ze twee referenties hebben. Maar dubbele linklijsten maken het gemakkelijker om te manipuleren, aangezien het de lijst in de voorwaartse en achterwaartse richting mogelijk maakt.