Microsoft se întreabă: listă unică sau dublă? Care sunt avantajele și dezavantajele utilizării fiecăreia dintre ele? (Programare, .Net, Listă Legată)

Tarik a intrebat.
a intrebat.

Mi se pune o astfel de întrebare și eu am propriile mele ziceri, dar nu sunt foarte sigur ce să spun despre contra și pro? Microsoft a adresat această întrebare unuia dintre candidații săi.

Lista legată singular vă permite să mergeți într-o singură direcție. În timp ce lista dublu legată are două direcții, următoarea și precedenta.

Iată o imagine bună care prezintă listele legate simplu și dublu.

Cu toate acestea, cum puteți explica avantajele și dezavantajele acestor elemente într-un mod mai ordonat?

Comentarii

  • Una este mai flexibilă, iar cealaltă necesită mai mult efort. De asemenea, listele dvs. legate sunt de fapt liste legate circular. –  > Por robert.
  • Am folosit aceste imagini pentru a da un avertisment, de fapt. –  > Por Tarik.
  • S-ar putea să vrei să vezi listele cu legături simple și duble când și de ce –  > Por nawfal.
6 răspunsuri
Reed Copsey

Mi se pune o astfel de întrebare și am propriile mele ziceri, dar nu sunt foarte sigur ce să spun despre contra și pro?

Totul se reduce la utilizare. Există un compromis aici.

Lista legată singular este mai simplă din punct de vedere al implementării și, de obicei, are o cerință de memorie mai mică, deoarece trebuie să păstreze doar referința la membru înainte în loc.

Lista dublu legată are o iterație mai eficientă, în special dacă este nevoie să iterați vreodată în sens invers (ceea ce este extrem de ineficient cu o listă legată simplu) și o ștergere mai eficientă a nodurilor specifice.

Acestea fiind spuse – din moment ce aveți acest lucru etichetat .NET, listele dublu legate au, de asemenea, avantajul de a fi direct în cadrul sub forma LinkedList<T> clasă. Acest lucru oferă un avantaj uriaș prin faptul că nu trebuie să implementați, să testați și să mențineți propria clasă de colecție.

coder0h1t

Deși această întrebare a primit deja un răspuns, nu sunt cumva mulțumit de răspuns (fără supărare), așa că iată cum aș răspunde eu la ea:

Ce să folosiți – listă legată simplu sau dublu depinde de ceea ce intenționați să realizați și de limitările sistemului, dacă există.

Listă cu o singură legătură:

Avantaje: Simplu în implementare, necesită o memorie relativ mai mică pentru stocare, presupunând că trebuie să ștergeți/inserați (la) următorul nod – ștergerea/inserția este mai rapidă.

Dezavantaje: nu poate fi iterată în sens invers, trebuie să se mențină un mâner la nodul de cap al listei, altfel lista se va pierde în memorie. Dacă ștergeți nodul anterior sau inserați la nodul anterior, va trebui să parcurgeți lista de la capul listei până la nodul anterior pentru a putea efectua aceste operațiuni – timp O(N).

–Prin urmare, acest lucru ar trebui să fie utilizat atunci când aveți o memorie mai mică și obiectivul dvs. principal este inserarea/ștergerea și nu căutarea elementelor.

Listă cu legături duble:

Avantaje: Poate fi iterată atât în sens înainte, cât și în sens invers. În cazul în care este necesar să se șteargă nodul anterior, nu este necesar să se parcurgă de la nodul principal, deoarece nodul care trebuie șters poate fi găsit din indicatorul ‘.previous’.

Dezavantaje: relativ complexă de implementat, necesită mai multă memorie pentru stocare (1 pointer ‘.previous’ pentru fiecare nod). Inserțiile și ștergerile necesită mai mult timp (atribuirea/reatribuirea pointerului ‘.previous’ pentru nodurile vecine).

–Ar trebui să se utilizeze atunci când nu aveți limitări minime sau deloc în ceea ce privește memoria, iar obiectivul principal este căutarea de elemente.

Dacă mai există și alte argumente pro și contra, nu ezitați să le adăugați, răspundeți în comentarii. Vă mulțumim!

Serghei Kalinichenko

În timp ce lista legată simplu utilizează mai puțină memorie per nod (un pointer față de doi pointeri), operațiunea de ștergere a acesteia este O(N) dacă tot ceea ce aveți este un pointer la nodul pe care doriți să îl ștergeți, în timp ce ștergerea unei liste dublu legate este O(1). Există un truc puțin cunoscut care vă permite să ștergeți dintr-o listă cu o singură legătură în O(1), , dar lista trebuie să fie circulară pentru ca acest lucru să funcționeze (mutați conținutul lui next în cea curentă și ștergeți next).

Listele cu două legături pot fi utilizate în locuri în care listele cu o singură legătură nu ar funcționa (o coadă cu două capete), dar acestea necesită ceva mai multă „curățenie” și sunt puțin mai puțin eficiente în ceea ce privește inserțiile ca rezultat.

Comentarii

  • Frumos truc! Nu știam că…  > Por Martín Schere.
Porco

Avantajul listei dublu legate: Se poate parcurge în ambele direcții

Avantajul unei liste legate simple: Mai puțină muncă de casă la actualizare/inserție/ștergere, mai puțină utilizare a memoriei.

Peladao

Ei bine, depinde de situație. Dacă trebuie să puteți obține rapid atât elementul anterior, cât și următorul element dintr-un anumit element, atunci o listă dublu legată este cea mai bună.

Dacă trebuie să obțineți doar următorul element dintr-un anumit element, atunci o listă cu o singură legătură este suficient de bună.

thealchemist

O listă cu o singură legătură este mai bună decât o listă cu două legături:

Avantaje:1. Necesită mai puțină memorie.

  1. Trebuie doar să mențină pe loc pointerul/referențierea înainte.
  2. 2. Listele cu o singură legătură sunt structuri de date persistente. http://en.wikipedia.org/wiki/Persistent_data_structure#Linked_lists

Dezavantaje:1. În general, pentru a elimina un nod din listă, trebuie să modificați următorul pointer al nodului care apare înainte de nodul de eliminat, astfel încât să nu mai arate spre nodul de eliminat. În cazul în care aveți un pointer către nodul care urmează să fie șters. Trebuie să începeți de la începutul listei și să o parcurgeți până când găsiți nodul care apare chiar înaintea nodului care trebuie șters. Acest lucru necesită timp O(n), astfel încât timpul de execuție pentru etapa de eliminare este O(n) în cel mai rău caz.

  1. Oferă acces secvențial într-o singură direcție. Ce se întâmplă dacă doriți să accesați în ambele direcții, ceea ce face din el un DLL.

Listă dublu legată peste lista simplu legată:

Avantaje: 1. Pentru a elimina un nod atunci când se dă un pointer la acel nod, lista dublu legată necesită O(1) în cel mai rău caz.

  1. Oferă acces secvențial în ambele direcții.

Dezavantaje:1. Necesită mai multă memorie (dacă nu este o listă cu legături XOR). Necesită doi pointeri previous și next, deoarece este o listă cu două direcții.

  1. Trebuie să mențină la locul lor atât indicatorii înainte cât și înapoi.

  2. Lista dublu legată nu se adaptează bine la o setare persistentă.