Kada trebam koristiti popis u odnosu na LinkedList

Kada je najbolje koristiti List(Of T) vs LinkedList(Of T) ?

320
04 окт. 04. listopada Jonathana Allena 2008-10-04 11:23 '08 u 11:23 2008-10-04 11:23
@ 13 odgovora

ispraviti

Pročitajte komentare na ovaj odgovor. Ljudi tvrde da nisam obavio odgovarajuće testove. Slažem se da to ne bi trebao biti prihvatljiv odgovor. Kao što sam bio, provela sam nekoliko testova i osjetila kako ih odvojiti.

Izvorni odgovor ...

Našao sam zanimljive rezultate:

 // Temporary class to show the example class Temp { public decimal A, B, C, D; public Temp(decimal a, decimal b, decimal c, decimal d) { A = a; B = b; C = c; D = d; } } 

Povezani popis (3,9 sekundi)

  LinkedList<Temp> list = new LinkedList<Temp>(); for (var i = 0; i < 12345678; i++) { var a = new Temp(i, i, i, i); list.AddLast(a); } decimal sum = 0; foreach (var item in list) sum += item.A; 

Popis (2,4 sekunde)

  List<Temp> list = new List<Temp>(); // 2.4 seconds for (var i = 0; i < 12345678; i++) { var a = new Temp(i, i, i, i); list.Add(a); } decimal sum = 0; foreach (var item in list) sum += item.A; 

Čak i ako pristupate samo podacima, to je mnogo sporije! Kažem da nikad ne koristim povezani popis.



border=0
border=0

Ovdje je još jedna usporedba koja izvodi više umetaka (planiramo umetnuti element u sredinu popisa)

Povezani popis (51 sekunda)

  LinkedList<Temp> list = new LinkedList<Temp>(); for (var i = 0; i < 123456; i++) { var a = new Temp(i, i, i, i); list.AddLast(a); var curNode = list.First; for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it curNode = curNode.Next; list.AddAfter(curNode, a); // Insert it after } decimal sum = 0; foreach (var item in list) sum += item.A; 

Popis (7,26 sekundi)

  List<Temp> list = new List<Temp>(); for (var i = 0; i < 123456; i++) { var a = new Temp(i, i, i, i); list.Insert(i / 2, a); } decimal sum = 0; foreach (var item in list) sum += item.A; 

Povezani popis s vezom do mjesta gdje želite umetnuti (0,04 sekunde)

  list.AddLast(new Temp(1,1,1,1)); var referenceNode = list.First; for (var i = 0; i < 123456; i++) { var a = new Temp(i, i, i, i); list.AddLast(a); list.AddBefore(referenceNode, a); } decimal sum = 0; foreach (var item in list) sum += item.A; 

Dakle, samo ako namjeravate umetnuti nekoliko elemenata, a također , negdje postoji veza gdje namjeravate umetnuti element, a zatim upotrijebiti povezani popis. Samo zato što trebate umetnuti mnogo elemenata, to ne ubrzava posao, jer pronalaženje mjesta na koje želite umetnuti treba vremena.

97
17 сент. Odgovor je dan Tono Nam 17 sep . 2012-09-17 23:47 '12 u 23:47 2012-09-17 23:47

U većini slučajeva, List<T> korisniji. LinkedList<T> imat će niže troškove prilikom dodavanja / brisanja stavki na sredini popisa, dok List<T> može biti jeftin samo za dodavanje / uklanjanje na kraju popisa.

LinkedList<T> radi samo ako pristupate serijskim podacima (naprijed ili natrag) - slučajni pristup je relativno skup, jer svaki put mora hodati duž lanca (dakle nema indeksera). Međutim, budući da je List<T> u osnovi samo niz (omotan), slučajan pristup je u redu.

border=0

List<T> također nudi različite metode podrške - Find , ToArray , itd.; međutim, oni su također dostupni za LinkedList<T> s .NET 3.5 / C # 3.0 metodama proširenja - tako da je to manje važno.

221
04 окт. odgovor dao Marc Gravell 04. listopada. 2008-10-04 11:28 '08 u 11:28 2008-10-04 11:28

Razmišljanje o povezanom popisu kao popisu može biti malo pogrešno. Ovo je više kao lanac. Zapravo, u .NET-u, LinkedList<T> ne primjenjuje čak ni IList<T> . U povezanom popisu nema stvarnog koncepta indeksa, iako se može činiti da postoji. Naravno, nijedna od metoda navedenih u razredu ne prihvaća indekse.

Povezane popise možete povezati pojedinačno ili dvostruko. To se odnosi na to da li svaki element u lancu ima vezu samo na sljedeći (jedan spojen) ili na oba prethodna / sljedeća elementa (dvaput spojen). LinkedList<T> ima dvostruku vezu.

Unutarnji niz List<T> podržava niz. Pruža vrlo kompaktan prikaz memorije. Obrnuto, LinkedList<T> uključuje dodatnu memoriju za pohranu dvosmjernih veza između uzastopnih elemenata. Prema tome, veličina memorije LinkedList<T> obično će biti veća nego za List<T> (uz uvjet da List<T> može imati neiskorištene interne elemente niza za poboljšanje performansi tijekom operacija dodavanja).

Oni također imaju različite karakteristike:

dodati

  • LinkedList<T>.AddLast(item) konstantno vrijeme
  • List<T>.Add(item) amortizirano konstantno vrijeme, linearno najgori slučaj

Dodavanje na početak

  • LinkedList<T>.AddFirst(item) stalno vrijeme
  • List<T>.Insert(0, item) linearno vrijeme

umetnuti

  • LinkedList<T>.AddBefore(node, item)
  • LinkedList<T>.AddAfter(node, item) konstantno vrijeme
  • List<T>.Insert(index, item) linearno vrijeme

uklanjanje

  • LinkedList<T>.Remove(item) linearno vrijeme
  • LinkedList<T>.Remove(node) konstantno vrijeme
  • List<T>.Remove(item) linearno vrijeme
  • List<T>.RemoveAt(index) linearno vrijeme

računati

  • LinkedList<T>.Count stalno vrijeme
  • List<T>.Count stalno vrijeme

sadrži

  • LinkedList<T>.Contains(item) linearno vrijeme
  • List<T>.Contains(item) linearno vrijeme List<T>.Contains(item)

čist

  • LinkedList<T>.Clear() linearno vrijeme
  • List<T>.Clear() linearno vrijeme

Kao što možete vidjeti, oni su u osnovi jednaki. U praksi, LinkedList<T> API je teže koristiti, a detalji njegovih internih potreba ulaze u vaš kod.

Međutim, ako trebate napraviti mnogo privitaka / apstrakcija s popisa, on nudi stalno vrijeme. List<T> nudi linearno vrijeme budući da se dodatne stavke na popisu moraju miješati nakon umetanja / brisanja.

174
15 окт. Odgovor dao Drew Noakes 15. listopada 2011-10-15 14:58 '11 u 14:58 2011-10-15 14:58

Povezani popisi omogućuju vrlo brzo umetanje ili brisanje člana popisa. Svaki član u povezanom popisu sadrži pokazivač na sljedećeg člana na popisu za umetanje elementa na poziciju i:

  • ažurirajte pokazivač u i-1 da biste pokazali na novu stavku
  • postavite pokazivač u novom članu da označi člana i

Nedostatak povezanog popisa je da nasumični pristup nije moguć. Pristup članu zahtijeva prosljeđivanje popisa sve dok se ne pronađe željena stavka.

111
Odgovor je b3. 04. listopada 2008-10-04 11:34 '08 u 11:34 2008-10-04 11:34

Razlika između popisa i LinkedLista leži u njihovoj glavnoj implementaciji. Popis je niz baziran na nizu (ArrayList). LinkedList je zbirka koja se temelji na čvoru (LinkedListNode). Kada se koristi API razina, obje su gotovo iste, budući da obje implementiraju isti skup sučelja, kao što su ICollection, IEnumerable, itd.

Ključna razlika nastaje kada je izvedba važna. Na primjer, ako implementirate popis s teškom INSERT operacijom, LinkedList je superiorniji od popisa. Budući da LinkedList može učiniti ova vremena O (1), popis će možda trebati proširiti veličinu osnovnog niza. Za više informacija ili pojedinosti, možda ćete se morati upoznati s algoritamskom razlikom između strukture podataka LinkedList i niza podataka. http://en.wikipedia.org/wiki/Linked_list i polje

Nadam se ovoj pomoći

16
04 окт. odgovor od korisnika23117 04. 2008-10-04 11:35 '08 u 11:35 2008-10-04 11:35

Glavna prednost povezanih popisa pomoću nizova je ta da nam veze omogućuju da učinkovito obnovimo elemente. Sedgewick, str. 91

9
odgovor daje Dr. 25 нояб. Alrawi 25. stu 2012-11-25 11:52 '12 u 11:52 2012-11-25 11:52

Moj prethodni odgovor nije bio dovoljno točan. Kako je bilo strašno: D Ali sada mogu postaviti mnogo više korisnog i točnog odgovora.


Napravio sam neke dodatne testove. Njezin izvor možete pronaći na sljedećem linku i ponovo ga sami instalirati u svom okruženju: https://github.com/ukushu/DataStructuresTestsAndOther.git

Kratki rezultati:

  • Niz bi trebao koristiti:

    • Što je češće moguće. Brz je i zauzima najmanje količine RAM-a za informacije o istom iznosu.
    • Ako znate točan broj potrebnih stanica
    • Ako su podaci pohranjeni u nizu <85000 b
    • Ako je potreban slučajan pristup velikom brzinom
  • Popis treba koristiti:

    • Ako želite dodati ćelije na kraj popisa (često)
    • Ako trebate dodati ćelije na početak / sredinu popisa (NOT OFTEN)
    • Ako su podaci pohranjeni u nizu <85000 b
    • Ako je potreban slučajan pristup velikom brzinom
  • LinkedList treba koristiti:

    • Ako trebate dodati ćelije na početak / sredinu / kraj popisa (često)
    • Ako je potrebno, samo sekvencijalni pristup (naprijed / nazad)
    • Ako trebate spremiti LARGE elemente, ali broj elemenata će biti nizak.
    • Bolje je ne koristiti za veliki broj elemenata jer koristi dodatne memorije za reference.

Više detalja:

2019

Uobičajeno je korištenje LinkedLista sljedeće:

Pretpostavimo da želite izbrisati više redaka s popisa velikih redaka, recimo 100.000. Možete pronaći redove za brisanje u HashSet dic, a vjeruje se da popis redaka sadrži od 30.000 do 60.000 takvih linija koje treba izbrisati.

Što je onda najbolja vrsta popisa za pohranjivanje 100.000 redaka? Odgovor: LinkedList. Ako se pohranjuju u ArrayList, onda ga ponovite i uklonite odgovarajuće retke koji će zahtijevati milijarde operacija, dok je potrebno oko 100.000 operacija pomoću iteratora i metode remove ().

 LinkedList<String> strings = readStrings(); HashSet<String> dic = readDic(); Iterator<String> iterator = strings.iterator(); while (iterator.hasNext()){ String string = iterator.next(); if (dic.contains(string)) iterator.remove(); } 
3
19 авг. Odgovori Tom 19 Aug. 2014-08-19 15:47 '14 u 15:47 2014-08-19 15:47

Ako trebate ugrađeni indeksirani pristup, sortiranje (i nakon ovog binarnog pretraživanja) i ToArray () metodu, trebate koristiti List.

2
04 окт. Odgovor je dao Michael Damatov 04. listopada. 2008-10-04 11:27 '08 u 11:27 2008-10-04 11:27

Prilagođen je od Tono Nam , koji je prihvatio odgovor, ispravivši u njemu nekoliko netočnih mjerenja.

Test:

 static void Main() { LinkedListPerformance.AddFirst_List(); // 12028 ms LinkedListPerformance.AddFirst_LinkedList(); // 33 ms LinkedListPerformance.AddLast_List(); // 33 ms LinkedListPerformance.AddLast_LinkedList(); // 32 ms LinkedListPerformance.Enumerate_List(); // 1.08 ms LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms //I tried below as fun exercise - not very meaningful, see code //sort of equivalent to insertion when having the reference to middle node LinkedListPerformance.AddMiddle_List(); // 5724 ms LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms Environment.Exit(-1); } 

I kod:

 using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace stackoverflow { static class LinkedListPerformance { class Temp { public decimal A, B, C, D; public Temp(decimal a, decimal b, decimal c, decimal d) { A = a; B = b; C = c; D = d; } } static readonly int start = 0; static readonly int end = 123456; static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp); static Temp temp(int i) { return new Temp(i, i, i, i); } static void StopAndPrint(this Stopwatch watch) { watch.Stop(); Console.WriteLine(watch.Elapsed.TotalMilliseconds); } public static void AddFirst_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Insert(0, temp(i)); watch.StopAndPrint(); } public static void AddFirst_LinkedList() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (int i = start; i < end; i++) list.AddFirst(temp(i)); watch.StopAndPrint(); } public static void AddLast_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Add(temp(i)); watch.StopAndPrint(); } public static void AddLast_LinkedList() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (int i = start; i < end; i++) list.AddLast(temp(i)); watch.StopAndPrint(); } public static void Enumerate_List() { var list = new List<Temp>(query); var watch = Stopwatch.StartNew(); foreach (var item in list) { } watch.StopAndPrint(); } public static void Enumerate_LinkedList() { var list = new LinkedList<Temp>(query); var watch = Stopwatch.StartNew(); foreach (var item in list) { } watch.StopAndPrint(); } //for the fun of it, I tried to time inserting to the middle of //linked list - this is by no means a realistic scenario! or may be //these make sense if you assume you have the reference to middle node //insertion to the middle of list public static void AddMiddle_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Insert(list.Count / 2, temp(i)); watch.StopAndPrint(); } //insertion in linked list in such a fashion that //it has the same effect as inserting into the middle of list public static void AddMiddle_LinkedList1() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); LinkedListNode<Temp> evenNode = null, oddNode = null; for (int i = start; i < end; i++) { if (list.Count == 0) oddNode = evenNode = list.AddLast(temp(i)); else if (list.Count % 2 == 1) oddNode = list.AddBefore(evenNode, temp(i)); else evenNode = list.AddAfter(oddNode, temp(i)); } watch.StopAndPrint(); } //another hacky way public static void AddMiddle_LinkedList2() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start + 1; i < end; i += 2) list.AddLast(temp(i)); for (int i = end - 2; i >= 0; i -= 2) list.AddLast(temp(i)); watch.StopAndPrint(); } //OP original more sensible approach, but I tried to filter out //the intermediate iteration cost in finding the middle node. public static void AddMiddle_LinkedList3() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) { if (list.Count == 0) list.AddLast(temp(i)); else { watch.Stop(); var curNode = list.First; for (var j = 0; j < list.Count / 2; j++) curNode = curNode.Next; watch.Start(); list.AddBefore(curNode, temp(i)); } } watch.StopAndPrint(); } } } imate referencu na srednji čvor using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace stackoverflow { static class LinkedListPerformance { class Temp { public decimal A, B, C, D; public Temp(decimal a, decimal b, decimal c, decimal d) { A = a; B = b; C = c; D = d; } } static readonly int start = 0; static readonly int end = 123456; static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp); static Temp temp(int i) { return new Temp(i, i, i, i); } static void StopAndPrint(this Stopwatch watch) { watch.Stop(); Console.WriteLine(watch.Elapsed.TotalMilliseconds); } public static void AddFirst_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Insert(0, temp(i)); watch.StopAndPrint(); } public static void AddFirst_LinkedList() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (int i = start; i < end; i++) list.AddFirst(temp(i)); watch.StopAndPrint(); } public static void AddLast_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Add(temp(i)); watch.StopAndPrint(); } public static void AddLast_LinkedList() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (int i = start; i < end; i++) list.AddLast(temp(i)); watch.StopAndPrint(); } public static void Enumerate_List() { var list = new List<Temp>(query); var watch = Stopwatch.StartNew(); foreach (var item in list) { } watch.StopAndPrint(); } public static void Enumerate_LinkedList() { var list = new LinkedList<Temp>(query); var watch = Stopwatch.StartNew(); foreach (var item in list) { } watch.StopAndPrint(); } //for the fun of it, I tried to time inserting to the middle of //linked list - this is by no means a realistic scenario! or may be //these make sense if you assume you have the reference to middle node //insertion to the middle of list public static void AddMiddle_List() { var list = new List<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) list.Insert(list.Count / 2, temp(i)); watch.StopAndPrint(); } //insertion in linked list in such a fashion that //it has the same effect as inserting into the middle of list public static void AddMiddle_LinkedList1() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); LinkedListNode<Temp> evenNode = null, oddNode = null; for (int i = start; i < end; i++) { if (list.Count == 0) oddNode = evenNode = list.AddLast(temp(i)); else if (list.Count % 2 == 1) oddNode = list.AddBefore(evenNode, temp(i)); else evenNode = list.AddAfter(oddNode, temp(i)); } watch.StopAndPrint(); } //another hacky way public static void AddMiddle_LinkedList2() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start + 1; i < end; i += 2) list.AddLast(temp(i)); for (int i = end - 2; i >= 0; i -= 2) list.AddLast(temp(i)); watch.StopAndPrint(); } //OP original more sensible approach, but I tried to filter out //the intermediate iteration cost in finding the middle node. public static void AddMiddle_LinkedList3() { var list = new LinkedList<Temp>(); var watch = Stopwatch.StartNew(); for (var i = start; i < end; i++) { if (list.Count == 0) list.AddLast(temp(i)); else { watch.Stop(); var curNode = list.First; for (var j = 0; j < list.Count / 2; j++) curNode = curNode.Next; watch.Start(); list.AddBefore(curNode, temp(i)); } } watch.StopAndPrint(); } } } 

Vidite da rezultati odgovaraju teoretskim pokazateljima opisanim u drugim dokumentima. Vrlo jasno - LinkedList<T> dobiva puno vremena u slučaju umetanja. Nisam testirao da uklonim iz sredine popisa, ali rezultat bi trebao biti isti. Naravno, List<T> ima druga područja gdje najbolje funkcionira kao O (1) slučajni pristup.

1
03 июля '14 в 3:29 2014-07-03 03:29 odgovor je dat nawfal 3. srpnja '14. u 3:29 2014-07-03 03:29

Toliko je prosječnih odgovora ...

U nekim implementacijama povezanih listova koriste se osnovni blokovi prethodno dodijeljenih čvorova. Ako to ne učine, onda je konstantno vrijeme / linearno vrijeme manje važno, budući da će performanse memorije biti loše, a performanse predmemorije još gore.

Koristite povezane popise kada

1) Potrebna vam je sigurnosna nit. Možete stvoriti poboljšani streaming alga. Troškovi blokiranja će dominirati listom paralelnih stilova.

2) Ako imate veliku strukturu, sličnu redu čekanja, i želite bilo gdje izbrisati ili dodati, osim kraja cijelo vrijeme. > 100K popisa postoji, ali ne tako često.

0
08 окт. odgovor dao user1496062 8. listopada 2016-10-08 07:01 '16 u 7:01 am 2016-10-08 07:01

Postavio sam slično pitanje vezano uz izvedbu zbirke LinkedList i pronašao rješenje za Stephen Cleary Implementing C # Deque . Za razliku od zbirke redova, Deque vam omogućuje pomicanje elemenata naprijed i natrag ispred i iza. Izgleda kao povezani popis, ali s poboljšanom izvedbom.

0
12 авг. odgovor dao Adam Cox 12. kolovoza. 2017-08-12 19:02 '17 u 19:02 2017-08-12 19:02

Koristite LinkedList<> kada

  • Ne znate koliko objekata prolazi kroz pristupnik. Na primjer, Token Stream .
  • Kada samo želite izbrisati umetnuti na kraju.

Za sve ostalo, bolje je koristiti List<> .

0
23 нояб. Odgovor daje Antony Thomas 23. studenog. 2012-11-23 19:24 '12 u 19:24 2012-11-23 19:24