Share
Prima structură a datelor pe care o vom analiza este lista legată și cu un motiv bun. Pe lângă faptul că este o structură aproape omniprezentă utilizată în orice, de la sistemele de operare la jocurile video, este, de asemenea, un element de construcție cu care pot fi create multe alte structuri de date.
Într-un sens foarte general, scopul unei liste legate este de a oferi un mecanism coerent de stocare și accesare a unei cantități arbitrare de date. După cum sugerează și numele, aceasta se face prin legarea datelor într-o listă.
Înainte de a ne arunca cu capul în ceea ce înseamnă acest lucru, să începem prin examinarea modului în care datele sunt stocate într-un matrice.
Datele întregi stocate într-o matrice După cum arată figura, datele din matrice sunt stocate ca o singură bucată de memorie alocată contiguu, care este segmentată logic. Datele stocate în matrice sunt plasate într-unul din aceste segmente și se referă prin locația sau indexul în matrice.
Aceasta este o modalitate bună de a stoca date. Majoritatea limbajelor de programare facilitează alocarea rețelelor și funcționarea conținutului lor. Stocarea contextuală a datelor oferă beneficii de performanță (și anume localitatea datelor), iterarea datelor este simplă și datele pot fi accesate direct prin index (acces aleator) în timp constant.
Există totuși momente când o matrice nu este soluția ideală.
Luați în considerare un program cu următoarele cerințe:
Accentsconagua
NextValue ) până când se întâlnește numărul 0xFFFF.ProcessItems metodă.Întrucât cerințele indică faptul că trebuie transmise mai multe valori la ProcessItems într-un singur apel, o soluție evidentă ar implica utilizarea unei serii de numere întregi. De exemplu:
void LoadData () // Să presupunem că 20 este suficient pentru a menține valorile. int [] valori = int int [20]; pentru (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Această soluție are mai multe probleme, dar cel mai evident este văzut când se citesc mai mult de 20 de valori. Deoarece programul este acum, valorile de la 21 la n sunt pur și simplu ignorate. Acest lucru ar putea fi atenuat prin alocarea a mai mult de 20 de valori - poate 200 sau 2000. Poate că dimensiunea ar putea fi configurată de către utilizator sau, probabil, dacă matricea ar deveni plină ar putea fi alocată o matrice mai mare și toate datele existente copiate în ea. În cele din urmă, aceste soluții creează complexitate și deșeuri de memorie.
Este nevoie de o colecție care să ne permită să adăugăm un număr arbitrar de valori întregi și apoi să enumerăm acele numere întregi în ordinea în care au fost adăugate. Colecția nu ar trebui să aibă o dimensiune maximă fixă și indexarea accesului aleatoriu nu este necesară. Avem nevoie de o listă legată.
Înainte de a continua și de a afla cum este proiectată și implementată structura de date a listei legate, să examinăm cum poate arăta soluția noastră finală.
static void LoadItems () LinkedList list = nou LinkedList (); în timp ce (true) value int = NextValue (); dacă (valoare! = 0xFFFF) list.Add (valoare); altceva break; ProcessItems (listă); static void ProcessItems (lista LinkedList) // ... Date de proces.
Observați că toate problemele cu soluția de matrice nu mai există. Nu mai există probleme în care matricea nu este suficient de mare sau nu alocă mai mult decât este necesar.
De asemenea, trebuie să observați că această soluție informează unele dintre deciziile de proiectare pe care le vom face mai târziu, și anume că LinkedList clasa acceptă un argument generic și implementează IEnumerable interfață.
În centrul structurii de date asociate este clasa de noduri. Un nod este un container care oferă posibilitatea stocării datelor și conectării la alte noduri.
Un nod al listei conține date și o proprietate care indică următorul nod În forma sa cea mai simplă, o clasă Nod care conține numere întregi ar putea arăta astfel:
clasa publică Node public int Value get; a stabilit; Nod public Următor get; a stabilit;
Cu aceasta putem crea o listă foarte apropiată. În următorul exemplu vom aloca trei noduri (primul, mijlocul și ultimul) și apoi le vom uni într-o listă.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Nod primul = nou Nod Valoare = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Nodul mediu = Nod nou Value = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = mediu; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Nodul ultimul = nou Nod Valoare = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = ultimul;
Acum avem o listă legată care începe cu nodul primul și se termină cu nodul ultimul. Următor → proprietatea pentru ultimul nod indică nul, care este indicatorul final al listei. Având în vedere această listă, putem efectua câteva operații de bază. De exemplu, valoarea fiecărui nod Date proprietate:
privat static void PrintList (Nod nod) în timp ce (node! = null) Console.WriteLine (node.Value); node = node.Next;
PrintList metoda funcționează prin iterarea peste fiecare nod din listă, printarea valorii nodului curent și apoi deplasarea către nodul indicat de către Următor → proprietate.
Acum, că avem o înțelegere a ceea ce ar putea arăta un nod al listei legate, să analizăm realitatea LinkedListNode clasă.
public class LinkedListNode /// /// Construiește un nou nod cu valoarea specificată. /// LinkedListNode public (valoarea T) Value = value; /// /// Valoarea nodului. /// valoarea publică T get; setul intern; /// /// Următorul nod din lista legată (nul ultim nod). /// public LinkedListNode Înainte get; setul intern;
Înainte de a ne implementa LinkedList clasa, trebuie să ne gândim la ce am dori să facem cu lista.
Anterior am văzut că colecția trebuie să susțină datele puternic tipizate, astfel încât știm că vrem să creăm o interfață generică.
Deoarece utilizăm cadrul .NET pentru implementarea listei, este logic să ne dorim ca această clasă să poată acționa ca și celelalte tipuri de colecții încorporate. Cea mai ușoară modalitate de a face acest lucru este implementarea ICollection interfață. Observați că aleg ICollection si nu IList. Acest lucru se datorează faptului că IList interfata adauga abilitatea de a accesa valorile dupa index. În timp ce indexarea directă este în general utilă, ea nu poate fi implementată eficient într-o listă legată.
Având în vedere aceste cerințe, putem crea un element de clasă de bază, iar apoi, prin restul secțiunii, putem completa aceste metode.
public class LinkedList: System.Collections.Generic.ICollection public void Adăugați (element T) aruncați noua System.NotImplementedException (); void public Clear () arunca noua System.NotImplementedException (); bool public Contine (element T) arunca noua System.NotImplementedException (); public void CopyTo (T [] array, int arrayIndex) arunca noua System.NotImplementedException (); public int Count get; set privat; boot public IsReadOnly get arunca noua System.NotImplementedException (); bool public Eliminare (element T) arunca noua System.NotImplementedException (); public System.Collections.Generic.IEnumerator GetEnumerator () arunca noua System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () arunca noua System.NotImplementedException ();
| Comportament | Se adaugă valoarea furnizată la sfârșitul listei legate. |
| Performanţă | O (1) |
Adăugarea unui element la o listă legată implică trei pași:
LinkedListNode instanță.Următor → proprietatea ultimului nod la noul nod.Cheia este să știm nodul care este ultimul nod din listă. Există două modalități prin care putem ști asta. Prima modalitate este de a urmări primul nod (nodul "cap") și de a merge pe listă până când găsim ultimul nod. Această abordare nu presupune urmărirea ultimului nod, care salvează o valoare de memorie de referință (oricare ar fi dimensiunea indicelui platformei dvs.), dar necesită efectuarea traversării listei de fiecare dată când un nod este adăugat. Asta ar face Adăuga o operație O (n).
A doua abordare presupune ca noi să ținem evidența ultimului nod (nodul "coada") din listă și când adăugăm nodul nou, accesăm direct referința noastră stocată direct. Acesta este un algoritm O (1) și, prin urmare, abordarea preferată.
Primul lucru pe care trebuie să-l facem este să adăugăm două câmpuri private la LinkedList clasă: referințele la primul (capul) și ultimul (coada) noduri.
privat LinkedListNode _head; privat LinkedListNode _tail;
Apoi trebuie să adăugăm metoda care efectuează cei trei pași.
public void Adăugați (valoarea T) LinkedListNode node = new LinkedListNode (valoare); dacă (_head == null) _head = nod; _tail = nod; altceva _tail.Next = nod; _tail = nod; Count ++;
Mai întâi, alocă noul LinkedListNode instanță. Apoi, verifică dacă lista este goală. Dacă lista este goală, noul nod este adăugat pur și simplu prin alocarea _cap și _coadă referințele la noul nod. Noul nod este acum primul și ultimul nod din listă. Dacă lista nu este goală, nodul este adăugat la sfârșitul listei și _coadă referința este actualizată pentru a indica noul sfârșit al listei.
Numara proprietatea este incrementată atunci când un nod este adăugat pentru a asigura ICollection. Numara proprietatea returnează valoarea exactă.
| Comportament | Îndepărtează primul nod din listă a cărei valoare este egală cu valoarea furnizată. Metoda returnează valoarea adevărată dacă o valoare a fost eliminată. În caz contrar, se întoarce false. |
| Performanţă | Pe) |
Înainte de a vorbi despre Elimina algoritmul, să aruncăm o privire la ceea ce încearcă să realizeze. În figura următoare, există patru noduri dintr-o listă. Vrem să eliminăm nodul cu valoarea trei.
O listă legată cu patru valori După terminarea eliminării, lista va fi modificată astfel încât Următor → proprietate pe nod cu valoarea două puncte la nodul cu valoarea patru.
Lista conectată cu cel de-al 3-lea eliminat Algoritmul de bază pentru eliminarea nodurilor este:
Ca întotdeauna, diavolul este în detalii. Există câteva cazuri în care trebuie să ne gândim când eliminăm un nod:
_cap și _coadă câmpuri la nul._cap câmp pentru a indica noul nod cap._coadă câmpul de referință pentru penultimul nod din listă și setați-l Următor → proprietate la nul.public bool Ștergeți (element T) LinkedListNode precedent = null; LinkedListNode curent = _head; // 1: Lista goală: Nu faceți nimic. // 2: Nod singular: Anteriorul este nul. // 3: Multe noduri: // a: Nodul de eliminat este primul nod. // b: Nodul de eliminat este mijlocul sau ultimul. în timp ce (curent! = null) if (actual.Value.Equals (item)) // Este un nod în mijloc sau în final. dacă (anterior! = null) // Cazul 3b. // Înainte: Cap -> 3 -> 5 -> null // După: Cap -> 3 ------> null previous.Next = current.Next; // A fost sfârșitul, deci actualizare _tail. dacă (curent.Next == null) _tail = anterior; altfel // Cazul 2 sau 3a. // Înainte: Cap -> 3 -> 5 // După: Cap ------> 5 // Cap -> 3 -> null // Cap ------> null _head = _head.Next; // Lista este acum goală? dacă (_head == null) _tail = null; Numara--; return true; anterior = actual; curent = curent.Următor; return false;
Numara proprietatea este decrementată atunci când un nod este îndepărtat pentru a asigura ICollection. Numara proprietatea returnează valoarea exactă.
| Comportament | Returnează un Boolean care indică dacă valoarea furnizată există în lista asociată. |
| Performanţă | Pe) |
Conține metoda este destul de simplă. Se uită la fiecare nod din listă, de la primul la ultimul, și returnează adevărat imediat ce se găsește un nod care corespunde parametrului. Dacă se ajunge la sfârșitul listei și nodul nu este găsit, metoda revine fals.
bool public Contains (element T) LinkedListNode current = _head; în timp ce (curent! = null) if (actual.Value.Equals (item)) return true; current = current.Next; return false;
| Comportament | Returnează o instanță IEnumerator care permite enumerarea valorilor listei legate de la prima la ultima. |
| Performanţă | Returnează instanța enumerator este o operație O (1). Enumerarea fiecărui element este o operație O (n). |
GetEnumerator este implementată prin enumerarea listei de la primul nod la ultimul și utilizează C # Randament cuvânt cheie pentru a returna valoarea apelului nodului curent.
Observați că LinkedList implementează comportamentul de iterație în IEnumerable versiunea a metodei GetEnumerator și se îndepărtează de acest comportament în versiunea IEnumerable.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode curent = _head; în timp ce (curent! = null) randamentul randament curent.Value; curent = curent.Următor; IEnumerator IEnumerable.GetEnumerator () retur ((IEnumerable) acest) .GetEnumerator ();
| Comportament | Elimină toate elementele din listă. |
| Performanţă | O (1) |
clar metoda doar stabilește _cap și _coadă câmpuri pentru a șterge lista. Deoarece .NET este un limbaj colectat de gunoi, nodurile nu trebuie să fie eliminate în mod explicit. Este responsabilitatea apelantului, nu a listei conectate, să se asigure că dacă nodurile conțin IDisposable trimiteri sunt eliminate în mod corespunzător.
public void Clear () _head = null; _tail = null; Conținut = 0;
| Comportament | Copiază conținutul listei legate de la început până la sfârșit în matricea furnizată, pornind de la indexul de matrice specificat. |
| Performanţă | Pe) |
Copiaza in metoda pur și simplu iterează asupra elementelor din listă și utilizează atribuirea simplă pentru a copia elementele în matrice. Este responsabilitatea apelantului să se asigure că matricea țintă conține spațiul liber adecvat pentru a găzdui toate elementele din listă.
public void CopyTo (T [] array, int arrayIndex) LinkedListNode curent = _head; în timp ce (curent! = null) array [arrayIndex ++] = actual.Value; curent = curent.Următor;
| Comportament | Returnează un număr întreg indicând numărul de elemente care se află în prezent în listă. Când lista este goală, valoarea returnată este 0. |
| Performanţă | O (1) |
Numara este pur și simplu o proprietate implementată automat cu un getter public și setter privat. Comportamentul real se întâmplă în Adăuga, Elimina, și clar metode.
public int Count get; set privat;
| Comportament | Returnează false dacă lista nu este numai pentru citire. |
| Performanţă | O (1) |
boolean public IsReadOnly get return false;
Clasa LinkedList pe care tocmai am creat-o este cunoscută ca o listă unică, asociată. Aceasta înseamnă că există o singură legătură unidirecțională între un nod și nodul următor din listă. Există o variație obișnuită a listei legate, care permite apelantului să acceseze lista din ambele capete. Această variantă este cunoscută ca o listă dublată.
Pentru a crea o listă dublu legată, va trebui să modificăm mai întâi clasa noastră LinkedListNode pentru a avea o nouă proprietate numită Anterior. Anterior se va acționa ca în continuare, doar va indica punctul nodul anterior din listă.
O listă dublu legată utilizând o proprietate Nod precedent Următoarele secțiuni vor descrie doar modificările dintre lista singură legată și noua listă dublată.
Singura schimbare care va fi făcută în LinkedListNode clasa este adăugarea unei noi proprietăți numite Anterior ceea ce arată spre precedentul LinkedListNode în lista legată sau se întoarce nul dacă este primul nod din listă.
public class LinkedListNode /// /// Construiește un nou nod cu valoarea specificată. /// /// public LinkedListNode (valoare T) Value = value; /// /// Valoarea nodului. /// valoarea publică T get; setul intern; /// /// Următorul nod din lista legată (nul ultim nod). /// public LinkedListNode Înainte get; setul intern; /// /// Nodul anterior din lista legată (nul în cazul primului nod). /// public LinkedListNode Înapoi get; setul intern;
În timp ce singura listă de legături adaugă numai noduri la sfârșitul listei, lista dublată va permite adăugarea nodurilor la începutul și la sfârșitul listei utilizând AddFirst și AddLast, respectiv. ICollection. Adăuga metoda se va amâna la AddLast metodă pentru a păstra compatibilitatea cu singure legate Listă clasă.
| Comportament | Adaugă valoarea introdusă în partea din față a listei. |
| Performanţă | O (1) |
Atunci când adăugați un nod în partea din față a listei, acțiunile sunt foarte asemănătoare cu adăugarea la o singură listă legată.
Următor → proprietatea noului nod la nodul vechi al capului.Anterior proprietatea nodului vechi al capului la noul nod._coadă câmp (dacă este necesar) și incrementare Numara.public void AddFirst (valoarea T) LinkedListNode node = new LinkedListNode (valoare); // Salvați nodul capului astfel încât să nu-l pierdem. LinkedListNode temp = _head; // Capul punctului la noul nod. _head = nod; // Introduceți restul listei în spatele capului. _head.Next = temp; dacă (Count == 0) // Dacă lista a fost goală, atunci capul și coada trebuie să / / ambele să indice noul nod. _tail = _head; altceva // Înainte: cap -------> 5 <-> 7 -> null // După: cap -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Count ++;
| Comportament | Adaugă valoarea introdusă la sfârșitul listei. |
| Performanţă | O (1) |
Adăugarea unui nod la sfârșitul listei este chiar mai ușoară decât adăugarea unui nod la început.
Noul nod este pur și simplu atașat la sfârșitul listei, actualizând starea _coadă și _cap după caz, și Numara este incrementat.
public void AddLast (valoarea T) nod = LinkedListNode nou = LinkedListNode (valoare); dacă (Count == 0) _head = nod; altceva _tail.Next = nod; // Înainte: Cap -> 3 <-> 5 -> null // După: Cap -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = nod; Count ++;
Și așa cum am menționat mai devreme, ICollection.Adăugați va apela pur și simplu AddLast.
public void Adăugați (valoare T) AddLast (valoare);
Ca Adăuga, Elimina metoda va fi extinsă pentru a sprijini eliminarea nodurilor de la începutul sau sfârșitul listei. ICollection.Modul de eliminare va continua să elimine elemente de la început, singura modificare fiind actualizarea corespunzătoare Anterior proprietate.
| Comportament | Îndepărtează prima valoare din listă. Dacă lista este goală, nu se ia nicio acțiune. Returnează true dacă o valoare a fost eliminată. În caz contrar, se întoarce false. |
| Performanţă | O (1) |
RemoveFirst actualizează lista prin setarea listei legate cap proprietatea la al doilea nod din listă și actualizarea acestuia Anterior proprietate la nul. Aceasta elimină toate referințele la nodul anterior anterior, eliminându-l din listă. Dacă lista conținea doar un singur ton sau era goală, lista va fi goală ( cap și coadă proprietățile vor fi nul).
public void RemoveFirst () if (Count! = 0) // Înainte: Head -> 3 <-> 5 // După: Cap -------> 5 // Cap -> 3 -> null // Cap ------> null _head = _head.Next; Numara--; dacă (Count == 0) _tail = null; altfel // 5.Previous a fost 3; acum este nul. _head.Previous = null;
| Comportament | Îndepărtează ultimul nod din listă. Dacă lista este goală, nu se efectuează nicio acțiune. Returnează true dacă o valoare a fost eliminată. În caz contrar, se întoarce fals. |
| Performanţă | O (1) |
RemoveLast funcționează prin setarea listei coadă proprietatea a fi nodul care precedă nodul cozii curente. Aceasta elimină ultimul nod din listă. Dacă lista era goală sau avea doar un nod, atunci când metoda returnează cap și coadă proprietăți, ambele vor fi nul.
public void RemoveLast () if (Număr! = 0) if (Count == 1) _head = null; _tail = null; altceva // Înainte: Cap -> 3 -> 5 -> 7 // Tail = 7 // După: Cap -> 3 -> 5 -> null // Tail = 5 out din proprietatea 5 următoare. _tail.Previous.Next = null; _tail = _tail.Previous; Numara--;
| Comportament | Îndepărtează primul nod din listă a cărei valoare este egală cu valoarea furnizată. Metoda returnează valoarea adevărată dacă o valoare a fost eliminată. În caz contrar, se întoarce false. |
| Performanţă | Pe) |
ICollection. Elimina metoda este aproape identică cu versiunea singulară, cu excepția faptului că Anterior proprietatea este actualizată în timpul operației de eliminare. Pentru a evita codul repetat, metoda solicită RemoveFirst când se constată că nodul care este eliminat este primul nod din listă.
public bool Ștergeți (element T) LinkedListNode precedent = null; LinkedListNode curent = _head; // 1: Lista goală: Nu faceți nimic. // 2: Nod singular: Anteriorul este nul. // 3: Multe noduri: // a: Nodul de eliminat este primul nod. // b: Nodul de eliminat este mijlocul sau ultimul. în timp ce (actual! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals ) // Este un nod la mijloc sau la capăt. dacă (anterior! = null) // Cazul 3b. previous.Next = current.Next; // A fost sfârșitul, deci actualizare _tail. dacă (curent.Next == null) _tail = anterior; altceva // Înainte: Cap -> 3 <-> 5 <-> 7 -> null // După: Cap -> 3 <-------> 7 -> null // anterior = 3 // curent = 5 // curent.Next = 7 // Deci ... 7. Precedent = 3 curent.Următor precedent = precedent; Numara--; altfel // Cazul 2 sau 3a. RemoveFirst (); return true; anterior = actual; curent = curent.Următor; return false;
Putem adăuga noduri la fața și la sfârșitul listei - deci ce? De ce ne pasă? În starea actuală, dublu legate Listă clasa nu este mai puternică decât singura listă legată. Dar, cu o singură modificare minoră, putem deschide tot felul de comportamente posibile. Prin expunerea cap și coadă proprietăți ca proprietăți publice numai pentru citire, consumatorul listei asociate va putea implementa tot felul de noi comportamente.
public LinkedListNode Cap get return _head; public LinkedListNode Tail get return _tail;
Cu această schimbare simplă putem enumera lista manual, ceea ce ne permite să efectuăm enumerarea inversă (tail-to-head) și căutarea.
De exemplu, următoarea eșantion de cod arată cum se utilizează lista Coadă și Anterior proprietăți pentru a enumera lista în sens invers și a efectua o prelucrare pe fiecare nod.
public void ProcessListBackwards () LinkedList list = nou LinkedList (); PopulateList (lista); LinkedListNode curent = list.Tail; în timp ce (curent! = null) ProcessNode (curent); curent = curent.
În plus, dublu legate Listă clasa ne permite să creați cu ușurință Deque clasa, care este ea însăși un element de construcție pentru alte clase. Vom discuta această clasă mai târziu într-o altă secțiune.
