Enkel gelinkte lijst versus dubbel gelinkte lijst
Gelinkte lijst is een lineaire gegevensstructuur die wordt gebruikt om een verzameling gegevens op te slaan. Een gekoppelde lijst wijst geheugen toe aan zijn elementen afzonderlijk in zijn eigen geheugenblok en de algehele structuur wordt verkregen door deze elementen als schakels in een ketting te koppelen. Een enkelvoudig gekoppelde lijst bestaat uit een reeks knooppunten en elk knooppunt heeft een verwijzing naar het volgende knooppunt in de reeks. Een dubbel gelinkte lijst bevat een reeks knooppunten waarin elk knooppunt zowel een verwijzing naar het volgende knooppunt als naar het vorige knooppunt bevat.
Afzonderlijk gelinkte lijst
Elk element in een enkelvoudig gelinkte lijst heeft twee velden zoals getoond in figuur 1. Het dataveld bevat de daadwerkelijke opgeslagen gegevens en het volgende veld bevat de verwijzing naar het volgende element in de keten. Het eerste element van de gekoppelde lijst wordt opgeslagen als de kop van de gekoppelde lijst.
Figuur 2 toont een enkelvoudig gekoppelde lijst met drie elementen. Elk element slaat zijn gegevens op en alle elementen behalve de laatste slaan een verwijzing op naar het volgende element. Het laatste element bevat een null-waarde in het volgende veld. Elk element in de lijst is toegankelijk door bij de kop te beginnen en de volgende aanwijzer te volgen totdat u aan het vereiste element voldoet.
Dubbel gelinkte lijst
Elk element in een dubbel gelinkte lijst heeft drie velden zoals weergegeven in figuur 3. Net als bij een enkelvoudig gekoppelde lijst, bevat het gegevensveld de daadwerkelijke opgeslagen gegevens en bevat het volgende veld de verwijzing naar het volgende element in de keten. Bovendien bevat het vorige veld de verwijzing naar het vorige element in de keten. Het eerste element van de gekoppelde lijst wordt opgeslagen als de kop van de gekoppelde lijst.
Figuur 4 toont een dubbel gelinkte lijst met drie elementen. Alle tussenliggende elementen slaan verwijzingen op naar de eerste en vorige elementen. Het laatste element in de lijst heeft een null-waarde in het volgende veld en het eerste element in de lijst bevat een null-waarde in het vorige veld. Dubbel gelinkte lijst kan vooruit worden doorlopen door de volgende verwijzingen in elk element te volgen en kan op dezelfde manier achteruit worden doorlopen met behulp van de vorige verwijzingen in elk element.
Wat is het verschil tussen enkelvoudig gelinkte lijst en dubbel gelinkte lijst?
Elk element in de enkelvoudig gekoppelde lijst bevat een verwijzing naar het volgende element in de lijst, terwijl elk element in de dubbel gekoppelde lijst verwijzingen bevat naar zowel het volgende element als het vorige element in de lijst. Dubbel gekoppelde lijsten vereisen meer ruimte voor elk element in de lijst en elementaire bewerkingen zoals invoegen en verwijderen zijn complexer omdat ze te maken hebben met twee verwijzingen. Maar lijsten met dubbele links zorgen voor eenvoudigere manipulatie, omdat het de lijst in voorwaartse en achterwaartse richtingen doorkruist.
