Share
De eerste gegevensstructuur waar we naar zullen kijken, is de gelinkte lijst, en terecht. Naast een bijna alomtegenwoordige structuur die wordt gebruikt in alles, van besturingssystemen tot videogames, is het ook een bouwsteen waarmee vele andere datastructuren kunnen worden gemaakt.
In een zeer algemene zin is het doel van een gelinkte lijst om een consistent mechanisme te verschaffen om een willekeurige hoeveelheid gegevens op te slaan en te benaderen. Zoals de naam al aangeeft, doet het dit door de gegevens aan elkaar te koppelen in een lijst.
Voordat we ingaan op wat dit betekent, laten we beginnen met het bekijken hoe gegevens in een array worden opgeslagen.
Geheel getalgegevens die zijn opgeslagen in een array Zoals de afbeelding laat zien, worden matrixgegevens opgeslagen als een enkel aaneengesloten toegewezen geheugengeheugen dat logisch is gesegmenteerd. De gegevens die in de array zijn opgeslagen, worden in een van deze segmenten geplaatst en via de locatie of index in de array gerefereerd.
Dit is een goede manier om gegevens op te slaan. De meeste programmeertalen maken het zeer eenvoudig om arrays toe te wijzen en op hun inhoud te werken. Aaneengesloten gegevensopslag biedt prestatievoordelen (namelijk datarocaliteit), iteratie over de gegevens is eenvoudig en de gegevens kunnen direct worden benaderd door index (willekeurige toegang) in constante tijd.
Er zijn echter tijden wanneer een array niet de ideale oplossing is.
Overweeg een programma met de volgende vereisten:
Accentsconagua
nextValue methode) totdat het cijfer 0xFFFF wordt aangetroffen.ProcessItems methode.Aangezien de vereisten aangeven dat meerdere waarden moeten worden doorgegeven aan de ProcessItems methode in een enkele aanroep, zou een voor de hand liggende oplossing het gebruik van een array van gehele getallen impliceren. Bijvoorbeeld:
void LoadData () // Stel dat 20 voldoende is om de waarden vast te houden. int [] waarden = nieuwe int [20]; voor (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Deze oplossing heeft verschillende problemen, maar de meest in het oog springende wordt gezien wanneer meer dan 20 waarden worden gelezen. Zoals het programma nu is, worden de waarden van 21 tot n eenvoudigweg genegeerd. Dit kan worden gemitigeerd door meer dan 20 waarden toe te wijzen, bijvoorbeeld 200 of 2000. Misschien kan de grootte door de gebruiker worden geconfigureerd, of misschien kan de array vol raken als er een grotere array kan worden toegewezen en alle bestaande gegevens erin worden gekopieerd. Uiteindelijk creëren deze oplossingen complexiteit en verspilling van geheugen.
Wat we nodig hebben, is een verzameling waarmee we een willekeurig aantal gehele getallen kunnen toevoegen en vervolgens die gehele getallen kunnen nummeren in de volgorde waarin ze zijn toegevoegd. De verzameling mag geen vaste maximale grootte hebben en indexering van willekeurige toegang is niet nodig. Wat we nodig hebben is een gelinkte lijst.
Voordat we verder gaan en leren hoe de gelinkte lijstgegevensstructuur is ontworpen en geïmplementeerd, laten we eens kijken hoe onze uiteindelijke oplossing eruit zou kunnen zien.
static void LoadItems () LinkedList-lijst = nieuwe LinkedList (); while (true) int value = NextValue (); if (value! = 0xFFFF) list.Add (value); else break; ProcessItems (lijst); static void ProcessItems (lijst LinkedList) // ... Gegevens verwerken.
Merk op dat alle problemen met de array-oplossing niet langer bestaan. Er zijn geen problemen meer met de array die niet groot genoeg is of het toewijzen van meer dan nodig is.
U moet ook opmerken dat deze oplossing enkele van de ontwerpbeslissingen die we later zullen maken, deelt, namelijk dat het LinkedList class accepteert een generiek typeargument en implementeert het IEnumerable interface.
De knooppuntklasse is de kern van de gekoppelde gegevenslijststructuur. Een knooppunt is een container die de mogelijkheid biedt om zowel gegevens op te slaan als verbinding te maken met andere knooppunten.
Een knooppunt met een gekoppelde lijst bevat gegevens en een eigenschap die naar het volgende knooppunt verwijst In de eenvoudigste vorm kan een klasse Node die gehele getallen bevat er als volgt uitzien:
public class Node public int Value get; vast te stellen; public Node Next get; vast te stellen;
Hiermee kunnen we nu een zeer primitieve gekoppelde lijst maken. In het volgende voorbeeld zullen we drie knooppunten (eerste, middelste en laatste) toewijzen en ze vervolgens aan elkaar koppelen in een lijst.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Node first = new Node Value = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Node middle = nieuwe Node Waarde = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Node last = nieuw Node Waarde = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = laatste;
We hebben nu een gelinkte lijst die begint met het knooppunt eerste en eindigt met het knooppunt laatste. De volgende eigenschap voor de laatste knooppuntpunten tot nul, wat de indicator voor het einde van de lijst is. Met deze lijst kunnen we enkele basishandelingen uitvoeren. Bijvoorbeeld de waarde van elk knooppunt Gegevens eigendom:
private static void PrintList (Node node) while (node! = null) Console.WriteLine (node.Value); node = node.Next;
De PrintList methode werkt door te itereren over elk knooppunt in de lijst, de waarde van het huidige knooppunt af te drukken en vervolgens verder te gaan naar het knooppunt waarop de volgende eigendom.
Nu we begrijpen hoe een gelinkte lijstknooppunt eruit kan zien, laten we eens naar de werkelijke kijken LinkedListNode klasse.
public class LinkedListNode /// /// Construeert een nieuw knooppunt met de opgegeven waarde. /// public LinkedListNode (T-waarde) Waarde = waarde; /// /// De waarde van het knooppunt. /// openbare T-waarde krijg; interne set; /// /// Het volgende knooppunt in de gekoppelde lijst (null if last node). /// public LinkedListNode Volgende krijg; interne set;
Voordat we onze LinkedList klas, moeten we nadenken over wat we graag zouden willen doen met de lijst.
Eerder zagen we dat de verzameling sterk getypeerde gegevens moet ondersteunen, zodat we weten dat we een generieke interface willen maken.
Aangezien we het .NET-framework gebruiken om de lijst te implementeren, is het logisch dat we willen dat deze klasse zich kan gedragen als de andere ingebouwde collectietypen. De eenvoudigste manier om dit te doen is om het ICollection interface. Merk op dat ik kies ICollection en niet IList. Dit komt omdat het IList interface voegt de mogelijkheid toe om waarden per index te benaderen. Hoewel directe indexering over het algemeen nuttig is, kan deze niet efficiënt worden geïmplementeerd in een gekoppelde lijst.
Met deze vereisten in gedachten kunnen we een standaard klassenstomp maken en dan kunnen we door de rest van de sectie deze methoden invullen.
public class LinkedList: System.Collections.Generic.ICollection public void Add (T item) throw new System.NotImplementedException (); public void Clear () throw new System.NotImplementedException (); public bool Bevat (T item) gooi nieuw System.NotImplementedException (); openbare void CopyTo (T [] array, int arrayIndex) throw new System.NotImplementedException (); openbare int Graaf krijgen; privé set; public bool IsReadOnly krijg throw new System.NotImplementedException (); public bool Verwijderen (T item) throw new System.NotImplementedException (); public System.Collections.Generic.IEnumerator GetEnumerator () throw new System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () throw new System.NotImplementedException ();
| Gedrag | Voegt de opgegeven waarde toe aan het einde van de gekoppelde lijst. |
| Prestatie | O (1) |
Het toevoegen van een item aan een gekoppelde lijst omvat drie stappen:
LinkedListNode aanleg.volgende eigenschap van het laatste knooppunt naar het nieuwe knooppunt.De sleutel is om te weten welk knooppunt het laatste knooppunt in de lijst is. Er zijn twee manieren om dit te weten. De eerste manier is om het eerste knooppunt (het "hoofdknooppunt") bij te houden en door de lijst te lopen totdat we het laatste knooppunt hebben gevonden. Deze aanpak vereist niet dat we het laatste knooppunt bij houden, wat een referentiewaarde van het geheugen bespaart (ongeacht de grootte van uw platformaanwijzer), maar vereist wel dat we de lijst doorlopen telkens wanneer een knooppunt wordt toegevoegd. Dit zou maken Toevoegen een O (n) -bewerking.
De tweede benadering vereist dat we het laatste knooppunt (het "staartknooppunt") in de lijst bijhouden en wanneer we het nieuwe knooppunt toevoegen, hebben we eenvoudig toegang tot onze opgeslagen referentie. Dit is een O (1) -algoritme en daarom de voorkeursbenadering.
Het eerste dat we moeten doen is twee privévelden toevoegen aan de LinkedList klasse: verwijzingen naar de eerste (kop) en laatste (staart) knooppunten.
private LinkedListNode _head; private LinkedListNode _tail;
Vervolgens moeten we de methode toevoegen die de drie stappen uitvoert.
public void Toevoegen (T-waarde) LinkedListNode node = nieuwe LinkedListNode (waarde); if (_head == null) _head = node; _tail = knooppunt; else _tail.Next = node; _tail = knooppunt; Tel ++;
Ten eerste wijst het de nieuwe toe LinkedListNode aanleg. Vervolgens wordt gecontroleerd of de lijst leeg is. Als de lijst leeg is, wordt het nieuwe knooppunt eenvoudigweg toegevoegd door de _hoofd en _staart verwijzingen naar het nieuwe knooppunt. Het nieuwe knooppunt is nu zowel het eerste als het laatste knooppunt in de lijst. Als de lijst niet leeg is, wordt het knooppunt aan het einde van de lijst toegevoegd en de _staart referentie wordt bijgewerkt om naar het nieuwe einde van de lijst te wijzen.
De tellen eigenschap wordt opgehoogd wanneer een knooppunt wordt toegevoegd om de ICollection. tellen eigenschap retourneert de juiste waarde.
| Gedrag | Verwijdert het eerste knooppunt in de lijst waarvan de waarde gelijk is aan de opgegeven waarde. De methode geeft true als een waarde is verwijderd. Anders wordt false geretourneerd. |
| Prestatie | Op) |
Voordat we het hebben over de Verwijderen algoritme, laten we eens kijken naar wat het probeert te bereiken. In de volgende afbeelding zijn er vier knooppunten in een lijst. We willen het knooppunt verwijderen met de waarde drie.
Een gelinkte lijst met vier waarden Wanneer de verwijdering is voltooid, wordt de lijst zodanig gewijzigd dat de volgende eigenschap op het knooppunt met de waarde twee punten voor het knooppunt met de waarde vier.
De gekoppelde lijst met het 3-knooppunt verwijderd Het basisalgoritme voor knooppuntverwijdering is:
Zoals altijd zit de duivel in de details. Er zijn een paar gevallen waar we aan moeten denken bij het verwijderen van een knooppunt:
_hoofd en _staart velden naar nul._hoofd veld om naar het nieuwe hoofdknooppunt te wijzen._staart veld om te verwijzen naar het voorlaatste knooppunt in de lijst en stel het in volgende eigendom aan nul.public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: lege lijst: niets doen. // 2: Single node: Previous is null. // 3: Veel knooppunten: // a: knoop die moet worden verwijderd, is het eerste knooppunt. // b: Knooppunt dat verwijderd moet worden, is het midden of het laatst. while (current! = null) if (current.Value.Equals (item)) // Het is een knoop in het midden of einde. if (previous! = null) // Case 3b. // Before: Head -> 3 -> 5 -> null // After: Head -> 3 ------> null vorige.Next = current.Next; // Het was het einde, dus update _tail. if (current.Next == null) _tail = vorige; else // Case 2 of 3a. // Before: Head -> 3 -> 5 // After: Head ------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; // Is de lijst nu leeg? if (_head == null) _tail = null; Count--; geef waar terug; vorige = huidige; current = current.Next; return false;
De tellen eigenschap wordt verlaagd wanneer een knoop wordt verwijderd om de ICollection. tellen eigenschap retourneert de juiste waarde.
| Gedrag | Retourneert een Booleaanse waarde die aangeeft of de opgegeven waarde bestaat binnen de gekoppelde lijst. |
| Prestatie | Op) |
De bevat methode is vrij eenvoudig. Het kijkt naar elk knooppunt in de lijst, van de eerste naar de laatste, en retourneert de waarde true zodra een knoop die overeenkomt met de parameter wordt gevonden. Als het einde van de lijst wordt bereikt en het knooppunt niet wordt gevonden, keert de methode terug vals.
public bool Bevat (T item) LinkedListNode current = _head; while (current! = null) if (current.Value.Equals (item)) return true; current = current.Next; return false;
| Gedrag | Retourneert een IEnumerator-instantie waarmee de gelinkte lijstwaarden van voor tot achter opgesomd kunnen worden. |
| Prestatie | Het retourneren van de enumerator-instantie is een O (1) -bewerking. Het opsommen van elk item is een O (n) -bewerking. |
GetEnumerator wordt geïmplementeerd door de lijst op te sommen van het eerste naar het laatste knooppunt en gebruikt de C # opbrengst sleutelwoord om de waarde van het huidige knooppunt terug te geven aan de beller.
Merk op dat de LinkedList het iteratiegedrag implementeert in de IEnumerable versie van de GetEnumerator-methode en verwijst naar dit gedrag in de IEnumerable versie.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; while (current! = null) yield return current.Value; current = current.Next; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Gedrag | Verwijdert alle items uit de lijst. |
| Prestatie | O (1) |
De Duidelijk methode stelt eenvoudig de _hoofd en _staart velden naar nul om de lijst te wissen. Omdat .NET een taal is die door de vuilnisbak wordt verzameld, hoeven de knooppunten niet expliciet te worden verwijderd. Het is de verantwoordelijkheid van de beller en niet van de gekoppelde lijst om ervoor te zorgen dat de knooppunten bevatten IDisposable referenties worden ze op de juiste manier verwijderd.
public void Wissen () _head = null; _tail = null; Aantal = 0;
| Gedrag | Kopieert de inhoud van de gekoppelde lijst van begin tot eind in de opgegeven array, beginnend bij de opgegeven array-index. |
| Prestatie | Op) |
De Kopiëren naar methode herhaalt eenvoudigweg de lijstitems en gebruikt een eenvoudige toewijzing om de items naar de array te kopiëren. Het is de verantwoordelijkheid van de beller ervoor te zorgen dat de doelarray de juiste vrije ruimte bevat voor alle items in de lijst.
openbare void CopyTo (T [] array, int arrayIndex) LinkedListNode current = _head; while (current! = null) array [arrayIndex ++] = current.Value; current = current.Next;
| Gedrag | Retourneert een geheel getal dat het aantal items aangeeft dat momenteel in de lijst staat. Als de lijst leeg is, is de teruggegeven waarde 0. |
| Prestatie | O (1) |
tellen is gewoon een automatisch geïmplementeerd eigendom met een openbare vangstof en een privézetter. Het echte gedrag gebeurt in de Toevoegen, Verwijderen, en Duidelijk methoden.
openbare int graaf krijg; privé set;
| Gedrag | Retourneert false als de lijst niet alleen-lezen is. |
| Prestatie | O (1) |
public bool IsReadOnly krijg return false;
De klasse LinkedList die we zojuist hebben gemaakt, staat bekend als een afzonderlijke, gekoppelde lijst. Dit betekent dat er slechts één enkele unidirectionele koppeling bestaat tussen een knooppunt en het volgende knooppunt in de lijst. Er is een gemeenschappelijke variant van de gekoppelde lijst die de beller in staat stelt om vanaf beide kanten toegang te krijgen tot de lijst. Deze variant staat bekend als een dubbel gekoppelde lijst.
Als u een dubbel gelinkte lijst wilt maken, moeten we eerst onze klasse LinkedListNode wijzigen om een nieuwe eigenschap met de naam Vorige te krijgen. Vorige zal handelen als Volgende, alleen zal het verwijzen naar het vorige knooppunt in de lijst.
Een dubbel gekoppelde lijst met een eigenschap Previous node De volgende secties beschrijven alleen de wijzigingen tussen de enkelvoudig gekoppelde lijst en de nieuwe dubbel gelinkte lijst.
De enige verandering die zal worden aangebracht in de LinkedListNode klasse is de toevoeging van een nieuwe eigenschap met de naam voorgaand die naar het vorige wijst LinkedListNode in de gekoppelde lijst, of retourneert nul als dit het eerste knooppunt in de lijst is.
public class LinkedListNode /// /// Construeert een nieuw knooppunt met de opgegeven waarde. /// /// public LinkedListNode (T-waarde) Waarde = waarde; /// /// De waarde van het knooppunt. /// openbare T-waarde krijg; interne set; /// /// Het volgende knooppunt in de gekoppelde lijst (null if last node). /// public LinkedListNode Volgende krijg; interne set; /// /// Het vorige knooppunt in de gekoppelde lijst (nul als eerste knoop). /// public LinkedListNode Vorige get; interne set;
Terwijl de enkelvoudig gekoppelde lijst alleen knooppunten aan het einde van de lijst heeft toegevoegd, staat de dubbel gelinkte lijst toe dat knooppunten aan het begin en einde van de lijst worden toegevoegd met behulp van AddFirst en AddLast, respectievelijk. De ICollection. Toevoegen methode zal uitstellen naar de AddLast methode om de compatibiliteit met de enkelvoudig verbonden te behouden Lijst klasse.
| Gedrag | Voegt de opgegeven waarde toe aan de voorzijde van de lijst. |
| Prestatie | O (1) |
Wanneer u een knooppunt aan de voorzijde van de lijst toevoegt, lijken de acties sterk op toevoegen aan een enkelvoudige gekoppelde lijst.
volgende eigenschap van het nieuwe knooppunt van het oude hoofdknooppunt.voorgaand eigenschap van het oude hoofdknooppunt naar het nieuwe knooppunt._staart veld (indien nodig) en verhogen tellen.public void AddFirst (T-waarde) LinkedListNode node = nieuwe LinkedListNode (waarde); // Bewaar het hoofdknooppunt zodat we het niet verliezen. LinkedListNode temp = _head; // Wijs naar het nieuwe knooppunt. _head = knooppunt; // Plaats de rest van de lijst achter het hoofd. _head.Next = temp; if (Count == 0) // Als de lijst leeg was, moeten head en tail // beide verwijzen naar het nieuwe knooppunt. _tail = _head; else // Before: head -------> 5 <-> 7 -> null // After: head -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Tel ++;
| Gedrag | Voegt de opgegeven waarde toe aan het einde van de lijst. |
| Prestatie | O (1) |
Het toevoegen van een knooppunt aan het einde van de lijst is nog eenvoudiger dan het toevoegen van een knoop aan het begin.
Het nieuwe knooppunt wordt eenvoudigweg aan het einde van de lijst toegevoegd, waarbij de status wordt bijgewerkt _staart en _hoofd waar nodig, en tellen is verhoogd.
public void AddLast (T-waarde) LinkedListNode node = nieuwe LinkedListNode (waarde); if (Count == 0) _head = node; else _tail.Next = node; // Before: Head -> 3 <-> 5 -> null // After: Head -> 3 <-> 5 <-> 7 -> null // 7.Vorige = 5 node.Previous = _tail; _tail = knooppunt; Count ++;
En zoals eerder vermeld, ICollection.Toevoegen zal nu gewoon bellen AddLast.
public void Toevoegen (T-waarde) AddLast (waarde);
Net zoals Toevoegen, de Verwijderen methode zal worden uitgebreid ter ondersteuning van het verwijderen van knooppunten aan het begin of einde van de lijst. De ICollection.Verwijder methode blijft items verwijderen vanaf het begin met als enige wijziging het bijwerken van de juiste voorgaand eigendom.
| Gedrag | Verwijdert de eerste waarde uit de lijst. Als de lijst leeg is, wordt geen actie ondernomen. Retourneert true als een waarde is verwijderd. Anders wordt false geretourneerd. |
| Prestatie | O (1) |
RemoveFirst werkt de lijst bij door de gekoppelde lijst in te stellen hoofd eigenschap naar het tweede knooppunt in de lijst en de bijbehorende bijwerken voorgaand eigendom aan nul. Hiermee worden alle verwijzingen naar het vorige hoofdknooppunt verwijderd en uit de lijst verwijderd. Als de lijst slechts één singleton bevat, of leeg was, is de lijst leeg (de hoofd en staart eigenschappen zullen zijn nul).
public void RemoveFirst () if (Count! = 0) // Before: Head -> 3 <-> 5 // After: Head -------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; Count--; if (Count == 0) _tail = null; else // 5. Vroeger was 3; nu is het nul. _head.Previous = null;
| Gedrag | Verwijdert het laatste knooppunt uit de lijst. Als de lijst leeg is, wordt er geen actie uitgevoerd. Retourneert true als een waarde is verwijderd. Anders wordt false geretourneerd. |
| Prestatie | O (1) |
RemoveLast werkt door het instellen van de lijst's staart eigenschap om het knooppunt te zijn dat voorafgaat aan het huidige staartknooppunt. Hiermee verwijdert u het laatste knooppunt uit de lijst. Als de lijst leeg was of slechts één knooppunt had, wanneer de methode de hoofd en staart eigenschappen, ze zullen beide zijn nul.
public void RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = null; else // Before: Head -> 3 -> 5 -> 7 // Tail = 7 // After: Head -> 3 -> 5 -> null // Tail = 5 // Null uit 5's volgende eigendom. _tail.Previous.Next = null; _tail = _tail.Previous; Count--;
| Gedrag | Verwijdert het eerste knooppunt in de lijst waarvan de waarde gelijk is aan de opgegeven waarde. De methode geeft true als een waarde is verwijderd. Anders wordt false geretourneerd. |
| Prestatie | Op) |
De ICollection. Verwijderen methode is bijna identiek aan de enkelvoudig gekoppelde versie, behalve dat de voorgaand eigenschap is nu bijgewerkt tijdens de verwijderingsbewerking. Om herhaalde code te voorkomen, roept de methode aan RemoveFirst wanneer wordt vastgesteld dat het knooppunt dat wordt verwijderd, het eerste knooppunt in de lijst is.
public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: lege lijst: niets doen. // 2: Single node: Previous is null. // 3: Veel knooppunten: // a: knoop die moet worden verwijderd, is het eerste knooppunt. // b: Knooppunt dat verwijderd moet worden, is het midden of het laatst. while (current! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals (item) ) // Het is een knoop in het midden of einde. if (previous! = null) // Case 3b. previous.Next = current.Next; // Het was het einde, dus update _tail. if (current.Next == null) _tail = vorige; else // Before: Head -> 3 <-> 5 <-> 7 -> null // After: Head -> 3 <-------> 7 -> null // vorige = 3 // huidige = 5 // current.Next = 7 // So ... 7.Vorige = 3 current.Next.Previous = vorige; Count--; else // Case 2 of 3a. RemoveFirst (); return true; vorige = huidige; current = current.Next; return false;
We kunnen knooppunten toevoegen aan de voorkant en het einde van de lijst, dus wat? Waarom geven we erom? Zoals het er nu uitziet, het dubbel verbonden Lijst klas is niet krachtiger dan de enkelvoudig gekoppelde lijst. Maar met slechts een kleine wijziging kunnen we allerlei mogelijke gedragingen openen. Door de hoofd en staart eigenschappen als alleen-lezen openbare eigenschappen, de gelinkte lijst die de consument in staat zal zijn om allerlei soorten nieuw gedrag te implementeren.
public LinkedListNode Head krijg return _head; public LinkedListNode Tail krijg return _tail;
Met deze eenvoudige wijziging kunnen we de lijst handmatig opsommen, waardoor we reverse (tail-to-head) opsomming en zoeken kunnen uitvoeren.
In het volgende codevoorbeeld ziet u bijvoorbeeld hoe u de lijst gebruikt Staart en voorgaand eigenschappen om de lijst in omgekeerde volgorde op te sommen en enige verwerking op elk knooppunt uit te voeren.
public void ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (lijst); LinkedListNode current = list.Tail; while (current! = null) ProcessNode (current); current = current.Previous;
Bovendien is de dubbel verbonden Lijst klasse stelt ons in staat om eenvoudig het Deque klasse, die zelf een bouwsteen is voor andere klassen. We zullen deze klasse later in een andere sectie bespreken.
