Share
Den första datastrukturen vi ska titta på är den länkade listan, och med god anledning. Förutom att vara en nästan allestädes närvarande struktur som används i allt från operativsystem till videospel, är det också ett byggstenar med vilket många andra datastrukturer kan skapas.
I en mycket allmän bemärkelse är syftet med en länkad lista att tillhandahålla en konsekvent mekanism för att lagra och få tillgång till en godtycklig mängd data. Som namnet antyder gör det det genom att länka data tillsammans till en lista.
Innan vi dyker in i vad det betyder, låt oss börja med att granska hur data lagras i en array.
Heltalsdata lagrad i en array Som bilden visar lagras matrisdata som en enda tillhörande tilldelad bit av minne som logiskt segmenteras. Data som lagras i matrisen placeras i ett av dessa segment och refereras via dess plats eller index i matrisen.
Detta är ett bra sätt att lagra data. De flesta programmeringsspråk gör det väldigt enkelt att fördela arrayer och driva på innehållet. Kontinuerlig datalagring ger prestandafördelar (nämligen dataläge), iterering över data är enkel, och data kan nås direkt av index (random access) i konstant tid.
Det finns dock tider när en array inte är den perfekta lösningen.
Tänk på ett program med följande krav:
Accentsconagua
nextvalue metod) tills numret 0xFFFF stöter på.ProcessItems metod.Eftersom kraven visar att flera värden måste överföras till ProcessItems metod i ett samtal, en uppenbar lösning skulle innebära att man använder en rad heltal. Till exempel:
void LoadData () // Antag att 20 är tillräckligt för att hålla värdena. int [] värden = nytt int [20]; för (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Denna lösning har flera problem, men den mest skarpa ses när mer än 20 värden läses. Som programmet är nu ignoreras värdena från 21 till n. Detta kan mildras genom att tilldela mer än 20 värden, kanske 200 eller 2000. Kanske kan storleken konfigureras av användaren, eller om arrayen blev full kan en större grupp tilldelas och alla befintliga data kopieras in i den. I slutändan skapar dessa lösningar komplexitet och slöseri.
Vad vi behöver är en samling som tillåter oss att lägga till ett godtyckligt antal heltalvärden och sedan räkna över de heltal i den ordning som de lagts till. Samlingen ska inte ha en bestämd maximal storlek och det är inte nödvändigt med indexering av slumpmässig åtkomst. Vad vi behöver är en länkad lista.
Innan vi fortsätter och lär oss hur den länkade listdatastrukturen är utformad och implementerad, låt oss förhandsgranska vad vår ultimata lösning kan se ut.
static void LoadItems () LinkedList list = new LinkedList (); medan (sant) int värde = NextValue (); om (värde! = 0xFFFF) list.Add (value); annars break; ProcessItems (lista); statisk tomgång ProcessItems (LinkedList list) // ... Processdata.
Observera att alla problem med matrislösningen inte längre finns. Det finns inte längre några problem med att arrayen inte är stor nog eller fördelar mer än nödvändigt.
Du bör också märka att denna lösning informerar några av de designbeslut vi ska göra senare, nämligen att Länkad lista klassen accepterar ett generiskt typ argument och implementerar IEnumerable gränssnitt.
Kärnan i den länkade listan är datastrukturen i Node-klassen. En nod är en behållare som ger möjlighet att både lagra data och ansluta till andra noder.
En länkad listnod innehåller data och en egenskap som pekar på nästa nod I sin enklaste form kan en Node-klass som innehåller heltal se ut så här:
allmänklass Node public int Value get; uppsättning; Public Node Next get; uppsättning;
Med detta kan vi nu skapa en mycket primitiv länkad lista. I det följande exemplet fördelar vi tre noder (första, mitten och sista) och länkar dem sedan till en lista.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + nod första = ny nod värde = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Node middle = ny Node Value = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Node sist = nytt Node Value = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = sista;
Vi har nu en länkad lista som börjar med noden först och slutar med noden sista. De Nästa Egenskapen för den sista noden pekar till null vilket är slutförteckningsindikatorn. Med tanke på denna lista kan vi utföra några grundläggande operationer. Till exempel är värdet på varje nod Data fast egendom:
privat statisk tomt PrintList (Node node) while (node! = null) Console.WriteLine (node.Value); node = node.Next;
De PrintList Metoden fungerar genom att iterera över varje nod i listan, skriva ut värdet av nuvarande nod och sedan flytta vidare till noden påpekad av Nästa fast egendom.
Nu när vi har en förståelse för vad en länkad listnod kan se ut, låt oss titta på det faktiska LinkedListNode klass.
public class LinkedListNode /// /// Konstruerar en ny nod med det angivna värdet. /// public LinkedListNode (T-värde) Value = value; /// /// Nodvärdet. /// public T Value get; intern set; /// /// Nästa nod i länklistan (null om sista noden). /// public LinkedListNode Nästa get; intern set;
Innan vi genomför vår Länkad lista klass måste vi tänka på vad vi skulle vilja kunna göra med listan.
Tidigare såg vi att samlingen måste stödja starkt skrivad data, så vi vet att vi vill skapa ett generiskt gränssnitt.
Eftersom vi använder .NET-ramverket för att implementera listan är det meningsfullt att vi vill att den här klassen ska kunna fungera som de andra inbyggda samlingstyperna. Det enklaste sättet att göra detta är att genomföra iCollection gränssnitt. Lägg märke till att jag väljer iCollection och inte IList. Detta beror på att IList gränssnittet lägger till möjligheten att få tillgång till värden enligt index. Även om direkt indexering är vanligtvis användbar, kan den inte effektivt genomföras i en länkad lista.
Med dessa krav i åtanke kan vi skapa en grundläggande klassstub, och sedan genom resten av avsnittet kan vi fylla i dessa metoder.
public class LinkedList: System.Collections.Generic.ICollection public void Lägg till (T item) kasta nytt system.NotImplementedException (); public void Clear () kasta nytt system.NotImplementedException (); public bool Innehåller (T item) kasta nytt System.NotImplementedException (); public void CopyTo (T [] array, int arrayIndex) kasta nytt System.NotImplementedException (); public int count get; privat uppsättning public bool IsReadOnly get kasta nytt system.NotImplementedException (); public bool Ta bort (T item) kasta nytt system.NotImplementedException (); offentligt System.Collections.Generic.IEnumerator GetEnumerator () kasta nytt system.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () kasta nytt System.NotImplementedException ();
| Beteende | Lägger till det angivna värdet till slutet av den länkade listan. |
| Prestanda | O (1) |
Lägga till en vara i en länkad lista omfattar tre steg:
LinkedListNode exempel.Nästa egenskapen för den sista noden till den nya noden.Nyckeln är att veta vilken nod som är den sista noden i listan. Det finns två sätt att vi kan veta detta. Det första sättet är att hålla reda på den första noden ("huvud" noden) och gå till listan tills vi har hittat den sista noden. Detta tillvägagångssätt kräver inte att vi håller reda på den sista noden, vilket sparar en referensvärde av minne (oavsett vilken plattformspekare storlek är), men kräver att vi utför en passage över listan varje gång en nod läggs till. Detta skulle göra Lägg till en O (n) operation.
Det andra tillvägagångssättet kräver att vi håller reda på den sista noden ("svansnoden") i listan och när vi lägger till den nya noden öppnar vi bara vår lagrade referens direkt. Detta är en O (1) -algoritm och därmed det föredragna tillvägagångssättet.
Det första vi behöver göra är att lägga till två privata fält till Länkad lista klass: referenser till de första (huvud) och sista (svans) noderna.
privat LinkedListNode _head; privat LinkedListNode _tail;
Nästa måste vi lägga till metoden som utför de tre stegen.
public void Lägg till (T-värde) LinkedListNode node = new LinkedListNode (value); om (_head == null) _head = nod; _tail = nod; annars _tail.Next = nod; _tail = nod; Räkna ++;
För det första fördelar den den nya LinkedListNode exempel. Därefter kontrolleras det om listan är tom. Om listan är tom läggs den nya noden helt enkelt genom att tilldela _huvud och _svans referenser till den nya noden. Den nya noden är nu både den första och sista noden i listan. Om listan inte är tom läggs noden till slutet av listan och _svans referens uppdateras för att peka på den nya änden av listan.
De Räkna egenskapen ökas när en nod läggs till för att säkerställa iCollection. Räkna egenskapen returnerar det korrekta värdet.
| Beteende | Ta bort den första noden i listan vars värde är lika med det angivna värdet. Metoden returnerar sant om ett värde har tagits bort. Annars returneras det falskt. |
| Prestanda | På) |
Innan vi pratar om Ta bort algoritmen, låt oss ta en titt på vad den försöker åstadkomma. I följande figur finns det fyra noder i en lista. Vi vill ta bort noden med värdet tre.
En länkad lista med fyra värden När borttagningen är klar ändras listan så att Nästa egenskap på noden med värdet två pekar på noden med värdet fyra.
Den länkade listan med 3 noden borttagen Grundalgoritmen för borttagning av nod är:
Som alltid är djävulen i detaljerna. Det finns några fall vi måste tänka på när vi tar bort en nod:
_huvud och _svans fält till null._huvud fält för att peka på den nya huvudnoden._svans fält för att referera till näst sista nivån i listan och ställa in dess Nästa egendom till null.public bool Ta bort (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Tom lista: Gör ingenting. // 2: Enkelt nod: Föregående är null. // 3: Många noder: // a: Node att ta bort är den första noden. // b: Noden att ta bort är mitten eller senast. medan (nuvarande! = null) if (current.Value.Equals (item)) // Det är en nod i mitten eller slutet. om (tidigare! = null) // fall 3b. // Före: Huvud -> 3 -> 5 -> null // Efter: Huvud -> 3 ------> null previous.Next = current.Next; // Det var slutet, så uppdatera _tail. om (current.Next == null) _tail = previous; annat // fall 2 eller 3a. // Före: Huvud -> 3 -> 5 // Efter: Huvud ------> 5 // Huvud -> 3 -> null // Huvud ------> null _head = _head.Next; // Är listan nu tom? om (_head == null) _tail = null; Count--; återvänd sant; föregående = nuvarande; nuvarande = nuvarande.Nästa; returnera false;
De Räkna egenskapen minskas när en nod tas bort för att säkerställa iCollection. Räkna egenskapen returnerar det korrekta värdet.
| Beteende | Returnerar en booleska som anger om det angivna värdet finns inom den länkade listan. |
| Prestanda | På) |
De innehåller Metoden är ganska enkel. Det ser på varje nod i listan, från första till sista, och returneras sant så snart en nod som matchar parametern hittas. Om slutet av listan uppnås och noden inte hittas returnerar metoden falsk.
public bool Innehåller (T item) LinkedListNode current = _head; medan (nuvarande! = null) if (current.Value.Equals (item)) return true; nuvarande = nuvarande.Nästa; returnera false;
| Beteende | Returnerar en IEnumerator-instans som tillåter uppräkning av de länkade listvärdena från första till sista. |
| Prestanda | Att återkomma uppräkningsinstansen är en O (1) operation. Att räkna upp varje objekt är en O (n) operation. |
GetEnumerator implementeras genom att lista listan från första till sista nod och använder C # avkastning sökord för att returnera det aktuella nodens värde till den som ringer.
Observera att LinkedList implementerar iterationsbeteendet i IEnumerable versionen av GetEnumerator-metoden och försvarar detta beteende i den IEnumerable versionen.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; medan (nuvarande! = null) return return current.Value; nuvarande = nuvarande.Nästa; IEnumerator IEnumerable.GetEnumerator () returnera ((IEnumerable) this) .GetEnumerator ();
| Beteende | Tar bort alla objekt från listan. |
| Prestanda | O (1) |
De Klar Metoden ställer bara in _huvud och _svans Fält till null för att rensa listan. Eftersom .NET är ett skräpuppsamlat språk behöver noderna inte explicit tas bort. Det är ansvaret för den som ringer, inte den länkade listan, för att säkerställa att om noderna innehåller IDisposable referenser de är bortskaffade på rätt sätt.
public void Clear () _head = null; _tail = null; Räkna = 0;
| Beteende | Kopierar innehållet i den länkade listan från början till slut i den angivna matrisen, börjar med det angivna matrisindexet. |
| Prestanda | På) |
De Kopia till Metoden klarar helt enkelt över listobjekten och använder enkel uppgift för att kopiera objekten till matrisen. Det är uppringarens ansvar att se till att målmatrisen innehåller rätt ledigt utrymme för att rymma alla objekt i listan.
public void CopyTo (T [] array, int arrayIndex) LinkedListNode current = _head; medan (nuvarande! = null) array [arrayIndex ++] = current.Value; nuvarande = nuvarande.Nästa;
| Beteende | Returnerar ett heltal som anger antalet objekt som för närvarande finns i listan. När listan är tom är det returnerade värdet 0. |
| Prestanda | O (1) |
Räkna är helt enkelt en automatiskt genomförd egendom med en offentlig getter och privat setter. Det verkliga beteendet händer i Lägg till, Ta bort, och Klar metoder.
offentlig inträkning get; privat uppsättning
| Beteende | Returnerar fel om listan inte är skrivskyddad. |
| Prestanda | O (1) |
offentlig bool IsReadOnly get return false;
Den LinkedList-klass vi just skapat är känd som en ensam länkad lista. Det betyder att det bara finns en enda, enriktad länk mellan en nod och nästa nod i listan. Det finns en gemensam variant av den länkade listan som låter uppringaren komma åt listan från båda ändarna. Denna variant är känd som en dubbelkopplad lista.
För att skapa en dubbel länkad lista måste vi först ändra vår LinkedListNode-klass för att få en ny egenskap med namnet Föregående. Föregående kommer att fungera som Nästa, bara det kommer att peka på föregående nod i listan.
En dubbelt länkad lista med egenskapen Föregående nod Följande avsnitt beskriver bara ändringarna mellan den ensamlänkade listan och den nya dubbelförbundna listan.
Den enda förändringen som kommer att göras i LinkedListNode klassen är tillägget av en ny egendom som heter Tidigare vilket pekar på det föregående LinkedListNode i den länkade listan, eller returnerar null om det är den första noden i listan.
public class LinkedListNode /// /// Konstruerar en ny nod med det angivna värdet. /// /// public LinkedListNode (T-värde) Value = value; /// /// Nodvärdet. /// public T Value get; intern set; /// /// Nästa nod i länklistan (null om sista noden). /// public LinkedListNode Nästa get; intern set; /// /// Den föregående noden i den länkade listan (null om första noden). /// public LinkedListNode Föregående get; intern set;
Medan den enbart länkade listan bara lade till noder till slutet av listan, tillåter den dubbelkopplade listan att lägga till noder till början och slutet av listan med hjälp av AddFirst och AddLast, respektive. De iCollection. Lägg till Metoden kommer att skjuta upp till AddLast metod för att behålla kompatibiliteten med den ensam länkade Lista klass.
| Beteende | Lägger till det angivna värdet längst upp i listan. |
| Prestanda | O (1) |
När du lägger till en nod på framsidan av listan är åtgärderna väldigt lika med att du lägger till en enbart länkad lista.
Nästa egenskapen hos den nya noden till den gamla huvudnoden.Tidigare egenskapen hos den gamla huvudnoden till den nya noden._svans fält (om nödvändigt) och inkrement Räkna.public void AddFirst (T-värde) LinkedListNode node = nytt LinkedListNode (värde); // Spara huvudnoden så att vi inte förlorar det. LinkedListNode temp = _head; // Peka huvudet till den nya noden. _head = nod // Sätt in resten av listan bakom huvudet. _head.Next = temp; om (Räkna == 0) // Om listan var tom ska huvud och svans // vinkla till den nya noden. _tail = _head; annat // Före: huvud -------> 5 <-> 7 -> null // Efter: huvud -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Räkna ++;
| Beteende | Lägger till det angivna värdet till slutet av listan. |
| Prestanda | O (1) |
Att lägga till en nod till slutet av listan är ännu enklare än att lägga till en till början.
Den nya noden läggs enkelt till i slutet av listan, uppdaterar tillståndet för _svans och _huvud i förekommande fall, och Räkna ökas.
public void AddLast (T-värde) LinkedListNode node = nytt LinkedListNode (värde); om (räkna == 0) _head = nod; annars _tail.Next = nod; // Före: Huvud -> 3 <-> 5 -> null // Efter: Huvud -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = nod; Räkna ++;
Och som tidigare nämnts, iCollection.Lägg till kommer nu bara ringa AddLast.
public void Lägg till (T-värde) AddLast (värde);
Tycka om Lägg till, de Ta bort Metoden kommer att utökas för att stödja borttagna noder från början eller slutet av listan. De iCollection.Ta bort metod fortsätter att ta bort objekt från början med den enda ändringen att uppdatera lämpliga Tidigare fast egendom.
| Beteende | Tar bort det första värdet från listan. Om listan är tom, tas ingen åtgärd. Returnerar sant om ett värde har tagits bort. Annars returneras det falskt. |
| Prestanda | O (1) |
RemoveFirst uppdaterar listan genom att ange länklistan huvud egenskap till den andra noden i listan och uppdatera dess Tidigare egendom till null. Detta tar bort alla referenser till föregående huvudkod, tar bort den från listan. Om listan endast innehöll en singleton, eller var tom, kommer listan vara tom ( huvud och svans egenskaper kommer att vara null).
public void RemoveFirst () if (Count! = 0) // Före: Head -> 3 <-> 5 // Efter: Huvud -------> 5 // Huvud -> 3 -> null // Huvud ------> null _head = _head.Next; Räkna--; om (räkna == 0) _tail = null; annat // 5. Tidigare var 3; nu är det noll. _head.Previous = null;
| Beteende | Tar bort den sista noden från listan. Om listan är tom görs ingen åtgärd. Returnerar sant om ett värde har tagits bort. Annars returneras det falskt. |
| Prestanda | O (1) |
RemoveLast fungerar genom att ställa in listan svans egenskapen att vara noden som föregår den aktuella svansnoden. Detta tar bort den sista noden från listan. Om listan var tom eller bara hade en nod, när metoden returnerar huvud och svans egenskaper, de kommer båda vara null.
offentligt tomrum RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = null; annat // Före: Huvud -> 3 -> 5 -> 7 // Svans = 7 // Efter: Huvud -> 3 -> 5 -> null // Svans = 5 // Null ut 5: e nästa fastighet. _tail.Previous.Next = null; _tail = _tail.Previous; Räkna--;
| Beteende | Ta bort den första noden i listan vars värde är lika med det angivna värdet. Metoden returnerar sant om ett värde har tagits bort. Annars returneras det falskt. |
| Prestanda | På) |
De iCollection. Ta bort Metoden är nästan identisk med den ensam länkade versionen förutom att Tidigare egendom uppdateras nu under borttagningsoperationen. För att undvika upprepad kod, ringer metoden RemoveFirst när det är bestämt att noden som tas bort är den första noden i listan.
public bool Ta bort (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Tom lista: Gör ingenting. // 2: Enkelt nod: Föregående är null. // 3: Många noder: // a: Node att ta bort är den första noden. // b: Noden att ta bort är mitten eller senast. medan (nuvarande! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null om (current.Value.Equals ) // Det är en nod i mitten eller slutet. om (tidigare! = null) // fall 3b. föregående.Nästa = nuvarande.Nästa; // Det var slutet, så uppdatera _tail. om (current.Next == null) _tail = previous; annat // Före: Huvud -> 3 <-> 5 <-> 7 -> null // Efter: Huvud -> 3 <-------> 7 -> null // tidigare = 3 // nuvarande = 5 // current.Next = 7 // Så ... 7.Föreläsning = 3 current.Next.Forrige = föregående; Räkna--; annat // fall 2 eller 3a. RemoveFirst (); returnera sant; föregående = nuvarande; nuvarande = nuvarande.Nästa; returnera false;
Vi kan lägga till noder på framsidan och slutet av listan - så vad? Varför bryr vi oss? Som det står just nu är det dubbelt kopplat Lista klassen är inte mer kraftfull än den ensam länkade listan. Men med bara en mindre ändring kan vi öppna upp alla möjliga beteenden. Genom att exponera huvud och svans egenskaper som skrivskyddade offentliga egenskaper, kommer den länkade listan konsumenten att kunna genomföra alla typer av nya beteenden.
Public LinkedListNode Head get return _head; Public LinkedListNode Tail get return _tail;
Med denna enkla förändring kan vi räkna upp listan manuellt, vilket gör att vi kan göra omvänd (sväng-till-huvud) uppräkning och sökning.
Exempelvis visar följande kodprov hur du använder listan Svans och Tidigare egenskaper för att räkna upp listan i omvänd och utföra viss bearbetning på varje nod.
public void ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (lista); LinkedListNode current = list.Tail; medan (nuvarande! = null) ProcessNode (nuvarande); nuvarande = nuvarande
Dessutom är den dubbelt länkade Lista klassen tillåter oss att enkelt skapa Deque klass, som själv är ett byggstenar för andra klasser. Vi kommer att diskutera denna klass senare i en annan sektion.
