31 Soru: LinkedList Java'da ArrayList üzerinden ne zaman kullanılır?

tarafından oluşturulan soru Tue, Sep 11, 2018 12:00 AM

Her zaman basitçe kullanacak biri oldum:

 
List<String> names = new ArrayList<>();

Arabirimi, taşınabilirlik için tür adı olarak kullanırım, böylece bu gibi sorular sorduğumda kodumu yeniden çalıştırabilirim.

Ne zaman LinkedList ne zaman kullanılmalıdır ArrayList ve tersi?

    
2863
  1. 2016-10-12 03: 58: 29Z
  2. Sadece LinkedList'in yazarından alıntıyı görün stackoverflow.com/a/42529652/2032701 ve konuyla ilgili pratik bir fikir edineceksiniz.
    2017-12-26 19: 17: 59Z
30 Yanıtlar                              30                         

Özet ArrayList ile ArrayDeque, birçok 'da LinkedList’dan daha fazla kullanım durumunda tercih edilir. Emin değilseniz - sadece ArrayList ile başlayın.


LinkedList ve ArrayList, Liste arayüzünün iki farklı uygulamasıdır. LinkedList, çift bağlantılı bir liste ile uygular. ArrayList, dinamik olarak yeniden boyutlandırma dizisiyle uygular.

Standart bağlantılı liste ve dizi işlemlerinde olduğu gibi, çeşitli yöntemler farklı algoritmik çalışma sürelerine sahip olacaktır.

LinkedList<E>

için
  •  get(int index), O (n) (ortalama n /4 adımla)
  •  add(E element), 0 (1)
  •  add(int index, E element), O (n) (ortalama n /4 adımla), ancak 0 (1) , index = 0 - --- LinkedList<E>’un ana faydası
  •  remove(int index), O (n) (ortalama n /4 adımla)
  •  Iterator.remove(), 0 (1) . < --- LinkedList<E>’un ana parası
  •  ListIterator.add(E element): O (1) Bu, LinkedList<E>'un ana yararlarından biridir.

Not: İşlemlerin birçoğunun ortalama olarak n /4 adıma, en iyi durumda sabit adım sayısına (örneğin, index = 0) ve n /2 en kötü durumda adımlar (listenin ortasında)

ArrayList<E>

için
  •  get(int index), 0 (1) 'dir; ArrayList<E>’un ana yararı
  •  add(E element), 0 (1) itfa edildi, ancak dizinin yeniden boyutlandırılması ve kopyalanması gerektiğinden O (n) en kötü durum
  •  add(int index, E element), O (n) 'dir (ortalama olarak n /2 adımlarla)
  •  remove(int index), O (n) 'dir (ortalama olarak n /2 adımlarla)
  •  Iterator.remove(), O (n) 'dir (ortalama olarak n /2 adımlarla)
  •  ListIterator.add(E element), O (n) 'dir (ortalama olarak n /2 adımlarla)

Not: İşlemlerin birçoğunun ortalama olarak n /2 adıma, en iyi durumda (listenin sonunda) sabit adım sayısına ihtiyacı vardır. > n en kötü durumda olan adımlar (listenin başlangıcı)

LinkedList<E>, yineleyiciler kullanarak sabit zamanlı ekleme veya kaldırma işlemlerine izin verir , ancak öğelere yalnızca sıralı erişim sağlar. Başka bir deyişle, listeyi ileri ya da geri götürebilirsiniz, ancak listede bir konum bulmak listenin boyutuyla orantılı olarak zaman alır. Javadoc, "listeye endekslenen işlemler listeyi baştan veya sondan, hangisi daha yakınsa oradan geçecek" diyor, bu nedenle bu yöntemler O (n) ( n /4 adım) ortalama olarak, index = 0 için O (1) .

ArrayList<E> ise hızlı rasgele okuma erişimine izin veriyor, böylece herhangi bir öğeyi sabit bir zamanda tutabilirsiniz. Ancak herhangi bir yerden ekleme veya çıkarma ancak son, bir açılış yapmak veya boşluğu doldurmak için tüm sonraki öğelerin kaydırılmasını gerektirir. Ayrıca, temel dizinin kapasitesinden daha fazla öğe eklerseniz, yeni bir dizi (boyutun 1,5 katı) atanır ve eski dizi yenisine kopyalanır, böylece ArrayList'a ekleme O (n ) en kötü durumda ancak ortalama olarak sabit.

Yani, yaptığınız işlemlere bağlı olarak intBunu yapmak için uygulamaları uygun şekilde seçmelisin. Her iki tür Liste üzerinde yineleme yapmak pratik olarak aynı derecede ucuzdur. (ArrayList’un üzerinde yineleme yapmak teknik olarak daha hızlıdır, ancak performansa duyarlı bir şey yapmadığınız sürece bu konuda endişelenmemelisiniz - ikisi de sabittir.)

LinkedList kullanmanın asıl yararı, öğeleri eklemek ve kaldırmak için varolan yineleyicileri yeniden kullandığınızda ortaya çıkar. Bu işlemler daha sonra O (1) 'de sadece listeyi yerel olarak değiştirerek yapılabilir. Bir dizi listesinde, dizinin geri kalanının taşınması (örneğin kopyalanması) gerekir. Diğer taraftan, LinkedList'da arama yapmak en kötü durum için O (n) ( n /2 adımlarındaki) bağlantıları takip etmek anlamına gelir, oysa ki ArrayList'da istenen konum matematiksel olarak hesaplanmalı ve O (1) içinden erişilebilir.

LinkedList kullanmanın bir başka yararı da listenin başına eklediğinizde veya kaldırdığınızda ortaya çıkar, çünkü bu işlemler O (1) iken, O (n) ArrayList için. ArrayDeque'un kafadan ekleme ve çıkarma için LinkedList'a iyi bir alternatif olabileceğini unutmayın, ancak List değildir.

Ayrıca, büyük listeleriniz varsa, bellek kullanımının da farklı olduğunu unutmayın. LinkedList'un her bir elemanı daha fazla ek yüke sahiptir, çünkü bir sonraki ve bir önceki elemana işaretçiler de depolanır. ArrayLists bu ek yükü yok. Ancak, ArrayLists, gerçekte eklenmiş olsun veya olmasın, kapasite için ayrılan kadar bellek kullanır.

ArrayList'un varsayılan başlangıç ​​kapasitesi oldukça küçüktür (10'dan Java 1.4 - 1.8'e kadar). Ancak, temel uygulama bir dizi olduğundan, çok sayıda öğe eklerseniz dizinin yeniden boyutlandırılması gerekir. Çok sayıda öğe ekleyeceğinizi bildiğiniz zaman yeniden boyutlandırma maliyetinin yüksek olmasından kaçınmak için ArrayList'u daha yüksek bir başlangıç ​​kapasitesiyle oluşturun.

    
3135
2019-05-03 00: 36: 52Z
  1. Ekleme maliyetlerinden bahsetmeyi unuttum. LinkedList'te, doğru konuma sahip olduğunuzda, ekleme O (1) olurken, bir ArrayList'te O (n) 'e gider - ekleme noktasından sonraki tüm öğeler taşınmalıdır.
    2008-11-27 07: 20: 28Z
  2. Vektör kullanımıyla ilgili: Gerçekten Vektöre geri dönmeye gerek yok. Bunu yapmanın yolu, tercih ettiğiniz Liste uygulamasını ve senkronize bir sarıcıyı vermek için synchronizedList'e yapılan bir çağrıdır. Bakınız: java.sun.com/docs/books/tutorial/koleksiyonları /uygulamaları /...
    2008-11-27 12: 19: 18Z
  3. Hayır, LinkedList için, pozisyonu bilseniz bile, alma hala O (n) olur, çünkü bu pozisyona ulaşmak için, temeldeki uygulamanın yürümesi gerekir. bağlantılı listenin “sonraki” işaretçisi, bu pozisyonun değerine ulaşır. Rasgele erişim diye bir şey yoktur. Pozisyon 2 için, işaretçilerin yürüyüşü ucuz olabilir, ama pozisyon 1 milyon için, o kadar ucuz değil. Mesele şu ki, pozisyonla orantılı, bu da O (n) olduğu anlamına geliyor.
    2011-03-11 19: 03: 11Z
  4. @ Kevin Belleğin "birbirine yakın" olması önemli olabilir. Donanım, bitişik bellek bloklarını (dinamik RAM) L1 veya L2 önbelleğinde daha hızlı statik RAM'de önbelleğe alır. Teoride ve çoğu zaman pratik olarak, hafıza rastgele erişim olarak ele alınabilir. Ancak gerçekte, sırayla hafızadan okumak, rastgele sıraya göre biraz daha hızlı olacaktır. Performans açısından kritik bir döngü için bu önemli olabilir. Buna "mekânsal konum" veya referansın yeri diyorlar.
    2011-05-05 20: 25: 10Z
  5. O(n/2) veya O(n/4) diye bir şey yoktur. Büyük O notasyonu size bir işleminin n ile nasıl ölçeklendiğini gösterir. ve n/2 basamağa ihtiyaç duyan bir işlem tam olarak n basamağa ihtiyaç duyan bir işlem gibi ölçeklenir; bu nedenle sabit yazımların veya faktörlerin kaldırılmasının nedeni budur. O(n/2) ve O(n/4)'un her ikisi de sadece O(n)'dur. LinkedList ve ArrayList'un yine de farklı sabit faktörleri vardır, bu nedenle, her ikisinin de yalnızca doğrusal ölçeklendirme işlemlerini ifade ettiği gibi, O(n/2)’dan birinin O(n/4)’u diğerini LinkedList ile karşılaştırması söz konusu olmaz.
    2016-07-04 09: 57: 35Z

Şimdiye kadar, hiç kimse ArrayList’un LinkedLists’dan “çok daha fazla” olduğu şeklindeki genel fikir birliğinin yanı sıra, bu listelerin her birinin bellek ayak izini de ele almamış gibi görünüyor. Boş referanslar.

Referanslar göreceli sistemlerinde 32 veya 64 bit (boş olsalar bile) olduğundan, 32 ve 64 bit ArrayLists ve ArrayList için 4 veri seti ekledim.

Not: ArrayList satırları için gösterilen boyutlar kesilmiş listeler içindir - Uygulamada, bir LinkedList'daki destek dizisinin kapasitesi genellikle geçerli öğesinden daha büyüktür sayın.

Not 2: (teşekkürler BeeOnRope) CompressedOops varsayılan JDK6 ve üstü sürümlerde varsayılan olduğundan, 64 bit makineler için aşağıdaki değerler temel olarak 32 bit değerleriyle eşleşir meslektaşları, elbette özellikle kapatmazsanız.


LinkedList ve ArrayList Öğeleri x Bayt Sayısı


Sonuç, ArrayList’un LinkedLists’dan çok daha fazla olduğunu, özellikle de çok yüksek bir eleman sayısına sahip olduğunu göstermektedir. Bellek bir faktör ise, ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)'dan uzak durun.

Kullandığım formüller izleyin, yanlış bir şey yapıp yapmadığımı ve düzelteceğimi bana bildirin. 'b', 32 veya 64 bit sistemler için 4 veya 8'dir ve 'n', öğelerin sayısıdır. Modların nedeninin, java'daki tüm nesnelerin, kullanılmasına veya kullanılmamasına bakılmaksızın 8 baytlık bir alan kaplayacağından not edin.

ArrayList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

LinkedList:

int

    
588
2018-12-11 22: 15: 07Z
  1. LinkedList'in tek bir öğeyi depolamak için ArrayList kadar bellek gerektirdiğini görmek oldukça ilginç. Ne kadar sezgisel! Örneğinizi -XX: + UseCompressedOops ile çalıştırırsanız ne olur?
    2013-04-17 15: 31: 56Z
  2. Matematiğinizdeki sorun, grafiğinizin etkisini büyük ölçüde abartmasıdır. Her biri yalnızca CompressedOops, yani 4 veya 8 bayt veri içeren nesneleri modelliyorsunuz. Bağlantılı listede, temel olarak ek yüklerin 4 "kelimesi" vardır. Böylece grafiğiniz, bağlantılı listelerin dizi listelerinin depolanmasını "beş kez" kullandığı izlenimini verir. Bu yanlış. Tepegöz, ölçeklendirme faktörü değil, ilave ayar olarak nesne başına 16 veya 32 bayttır.
    2013-09-06 00: 18: 13Z
  3. ArrayList /LinkedList /Node nesnelerinin hiçbiri yalnızca bir int içermiyor, bu yüzden orada ne dediğinizi anlamadım. Netleştirmek için 'nesne yükü' ifadesini 'nesne üstbilgisine' verdim - sistemden bağımsız olarak her nesne için 8 baytlık bir başlık var ve evet, hepsi mümkün olduğu kadar doğru sayılan tüm Düğüm nesnelerini içeren söylemek. Bu arada, tekrar bakarken, LinkedList'teki matematiğimle ilgili birkaç problem daha buldum, bu da onu bölüp ArrayList'i daha da kötüleştirir . Güncellemeye devam etmekten mutluyum, bu nedenle lütfen daha fazla açıklığa kavuşturmak ve daha ayrıntılı bilgi almaktan çekinmeyin.
    2013-10-17 06: 24: 16Z
  4. ArrayList'un tüm son JDK'larda (7, 8 ve 6'nın birkaç yıldır güncelleştirilmesi) varsayılan olduğu, 64-bit yapamayacağı bir nedenden dolayı sıkıştırılmış ayraçları açıkça kapatmadıysanız, LinkedList veya ArrayList boyutlarında bir fark.
    2013-11-07 05: 29: 09Z
  5. Grafiğin resmi ticari kullanım için uygun mu? Kullanmak istiyorum.
    2015-09-05 07: 03: 47Z

LinkedList istediğin şey. LinkedList neredeyse her zaman (performans) bir hatadır.

Neden ArrayList berbat:

  • Çok sayıda küçük bellek nesnesi kullanır ve buradaFore işlem boyunca performansı etkiler.
  • Çok sayıda küçük nesne önbellek yerelliği için zararlıdır.
  • Dizine alınmış herhangi bir işlem bir geçiş gerektirir, yani O (n) performansı vardır. Bu, kaynak kodda açık değildir ve ArrayList'un kullanılmasından daha yavaş O (n) algoritmalarına neden olur.
  • İyi performans elde etmek zor.
  • Büyük O performansı LinkedList ile aynı olsa bile, muhtemelen yine de önemli ölçüde yavaşlayacaktır.
  • Kaynakta LinkedList'u görmek sıkıcıdır, çünkü muhtemelen yanlış bir seçimdir.
223
2017-10-09 13: 27: 37Z
  1. Üzgünüz. seni işaretledi. LinkedList emmez. LinkedList'in kullanılacak doğru sınıf olduğu durumlar vardır. Bir arylistten daha iyi olduğu birçok durum olmadığı konusunda hemfikirim, ama varlar. Aptalca şeyler yapan insanları eğitin!
    2008-11-27 17: 50: 43Z
  2. Bunun için çok fazla oy kullandığınız için üzgünüm. Java'nın LinkedList'ini kullanmak için gerçekten çok az sebep var. Kötü performansın yanı sıra, diğer somut Liste sınıflarından çok daha fazla bellek kullanır (her düğümde iki ek işaretçi bulunur ve her düğüm, onlarla birlikte gelen ek yük baytlarına sahip ayrı bir sarmalayıcı nesnesidir.
    ).
    2010-03-23 ​​00: 46: 34Z
  3. Bu, buradaki en yararlı cevaplardan biridir. Bu, bir çok programcının (a) soyut veri türleri ve somut uygulamalar arasındaki farkı ve (b) sabit faktörlerin ve genel giderlerin genel giderindeki performansı belirleme konusundaki farkın gerçek dünyadaki önemini anlayamaması çok yazık.
    2010-09-10 17: 25: 59Z
  4. - 1: Bu oldukça göz kamaştırıcı bir görünüm. Evet, ArrayList'in çok yönlü bir araçtır. Ancak, sınırlamaları vardır. Bunun size sıkıntıya neden olacağı durumlar vardır ve LinkedList'i kullanmak zorunda kalacaksınız. Tabii ki, bu çok özel bir çözüm ve herhangi bir özel araç olarak, çoğu durumda çok yönlü bir çözümden daha iyi bir performans sergiliyor. Ancak bu, "berbat" veya benzeri bir şey olduğu anlamına gelmez, ne zaman kullanacağınızı bilmeniz gerekir.
    2011-08-08 13: 43: 14Z
  5. @ DavidTurner: Varlar, ancak bence Tom'un amacı, sormak zorundaysanız muhtemelen ArrayList'i istemenizdi.
    2013-01-18 05: 07: 51Z

Yaklaşık on yıldır çok büyük ölçekli SOA web servislerinde operasyonel performans mühendisliği yapan biri olarak, LinkedList'in ArrayList'e göre davranışını tercih ederim. LinkedList'in kararlı durum verimi daha kötü olsa da bu nedenle daha fazla donanım satın almaya yol açabilir - ArrayList'in baskı altındaki davranışı, kümelerdeki uygulamaların dizileri yakın eşzamanlılıkta ve büyük dizi boyutları için genişletmesine neden olabilir uygulamada ve bir kesinti, baskı altındayken, bu felaket bir davranıştır.

Benzer şekilde, varsayılan iş hacmine sahip çöp toplayıcısından bir uygulamada daha iyi verim elde edebilirsiniz, ancak bir kez 10 GB'lık yığınlarla java uygulamaları elde ettiğinizde, zaman aşımına ve arızalara neden olan bir Tam GC sırasında uygulamayı 25 saniye kilitleyerek kapatabilirsiniz SOA uygulamalarında, SLA'larınızı çok sık meydana gelirse patlatır. CMS toplayıcısı daha fazla kaynak alsa ve aynı ham iş hacmine ulaşmasa da, daha iyi bir seçim çünkü daha öngörülebilir ve daha küçük gecikme süresi var.

ArrayList, yalnızca performanstan kastettiğin tüm verim ise ve gecikmeyi görmezden gelebilirsen performans için daha iyi bir seçimdir. İşimdeki deneyimime göre, en kötü gecikmeyi göz ardı edemem.

    
134
2011-01-01 20: 23: 52Z
  1. Başka bir çözüm, ArrayList'in sureCapacity () yöntemini kullanarak listenin boyutunu programlı olarak yönetemez mi? Benim sorumneden bir çok kırılgan veri yapısında önbellekleme veya db mekanizmasında daha iyi saklanabilecekleri bir çok şey saklanıyor? Geçen gün ArrayList'in kötülükleri hakkında aşağı yukarı yemin ettikleri bir röportaj yaptım, ama buraya geldim ve karmaşıklık analizinin her yerde daha iyi olduğunu gördüm! TARTIŞMA İÇİN BÜYÜK NOKTA. TEŞEKKÜRLER!
    2012-10-30 05: 33: 47Z
  2. 10GB'lık yığınlarla java uygulamaları edindikten sonra, tam zaman aşımına neden olan Tam GC'ler sırasında 25 saniye boyunca uygulamayı kilitleyerek kurulabilir LinkedList, çöp toplayıcısını tüm GC'ler sırasında öldürdüğünüzde, her düğümde önbellek özlemiyle aşırı büyük LinkedList'i yinelemelidir.
    2014-12-17 20: 15: 47Z
  3. Bu ... korkunç bir çözüm. temelde, sizin için temizlik yapan GC'ye güveniyorsunuz, ki bu oldukça pahalı bir şey, bir arrail için bunun yerine useCapacity () yöntemini çağırabilirsiniz ...
    2015-06-19 14: 03: 14Z
  4. @ Andreas: A ArrayList her zaman belleği, düz bir referans dizisinden beş kez ayırır, bu nedenle geçici olarak 2,5 kez gerektiren 2,53 Hafıza geri kazanılmamış olsa bile daha az hafıza. Büyük dizi tahsisi Eden alanını atladığından, gerçekten yeterli bellek olmadıkça GC davranışı üzerinde hiçbir etkisi olmaz, bu durumda LinkedList çok daha erken patladı…
    2016-07-05 09: 04: 52Z
  5. @ Andreas Diğer sorun belleğin nasıl tahsis edildiğidir. LinkedList, bir sonraki elemana ayırmak için sadece küçük bir boş hafıza parçasına ihtiyaç duyar. ArrayList, yeniden boyutlandırılmış diziyi tahsis etmek için büyük ve sürekli bir boş alan bloğuna ihtiyaç duyacaktır. Yığın parçalanırsa, GC uygun bir tek bellek bloğunu boşaltmak için tüm yığını yeniden sıralayabilir.
    2016-11-01 23: 12: 45Z
 
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritmalar: Büyük-Oh Notasyonu

ArrayLists, bir kez oku-birçok-oku veya ekleyici için iyidir, ancak önden veya ortadan ekleme /kaldırmada kötüdür.

    
119
2016-07-28 08: 46: 18Z
  1. Büyük-O değerlerini sabit faktörleri düşünmeden doğrudan karşılaştıramazsınız. Küçük listeler için (ve çoğu liste küçüktür), ArrayList'in O (N) LinkedList'in O'dan (1) daha hızlıdır.
    2010-09-10 17: 23: 15Z
  2. Küçük listelerin performansı umurumda değil ve bilgisayarım da bir döngüde kullanılmadığı sürece.
    2011-08-18 16: 35: 34Z
  3. LinkedList, O(1)'da tam ortasına eklenemez. Ekleme noktasını bulmak için listenin yarısını geçmesi gerekir.
    2011-12-30 15: 02: 56Z
  4. LinkedList: ortadaki O (1) - WRONG! LinkedList boyutunun 1/10 pozisyonuna yerleştirmenin bile, bir ArrayList'in 1/10 pozisyonuna bir eleman eklemekten daha yavaş olduğunu öğrendim. Ve daha da kötüsü: koleksiyonun sonu. ArrayList’in son konumlarına (en sonuncusuna değil) ekleme, LinkedList’in son konumlarına (sonuncusuna değil) daha hızlıdır
    2012-05-13 14: 29: 12Z
  5. @ kachanov LinkedList'da ekleme , O(1) ekleme konumunda bir yineleyiciniz varsa , yani ListIterator.add sözde O(1) için LinkedList.
    2013-08-18 08: 13: 07Z

Evet, biliyorum, bu eski bir soru, ancak iki sentimi de atacağım:

LinkedList neredeyse her zaman yanlış seçimdir, performans açısından. LinkedList'in çağrıldığı bazı çok özel algoritmalar vardır, ancak bunlar çok nadirdir ve algoritma genellikle LinkedList'in listenin ortasındaki öğeleri nispeten hızlı bir şekilde yerleştirdiğiniz ve sildiğiniz yeteneğine bağlıdır. ListIterator ile.

LinkedList'in ArrayList'ten daha iyi bir performans gösterdiği yaygın bir kullanım durumu vardır: bir sıranınki. Ancak, hedefiniz performanssa, LinkedList yerine bir ArrayBlockingQueue kullanmayı da düşünmelisiniz (zamanın başında kuyruk büyüklüğünüze bir üst sınır belirleyebilirseniz ve tüm bellekleri önceden tahsis edebiliyorsanız), href = "http://www.javaspecialists.eu/archive/Issue027.html" rel = "noreferrer"> CircularArrayList uygulaması . (Evet, 2001’den beri, bu nedenle onu yeniden tanımlamanız gerekecek, ancak makalede geçenlerde JVM’de belirtilenler ile karşılaştırılabilir performans oranları aldım)

    
101
2009-05-19 11: 21: 20Z
  1. Java 6'dan ArrayDeque'u kullanabilirsiniz. docs.oracle.com/javase/6/docs/aPI /java /util /ArrayDeque.html
    2011-12-30 15: 01: 32Z
  2. ArrayDeque, tüm işlemler aynı tarafta olmadıkça LinkedList'dan daha yavaştır. Yığın olarak kullanıldığında tamamdır, ancak iyi bir sıra oluşturmaz.
    2015-04-30 02: 12: 27Z
  3. Doğru Değil - en azından jdk1.7.0_60 ve sonraki testte Oracle'ın uygulaması için. 10 milyon kez döngü oluşturduğum bir test oluşturdum ve 10 milyon rastgele Tamsayı Deque'im var. Döngünün içinde bir elementi çağırırım ve sabit bir eleman öneririm. Bilgisayarımda LinkedList, ArrayDeque'den 10 kat daha yavaş ve daha az bellek kullanıyor). Bunun nedeni, ArrayList'ten farklı olarak ArrayDeque'in, dizinin başlığına bir işaretçi tutmasıdır; böylece, kafa kaldırıldığında tüm öğeleri taşımak zorunda kalmaz.
    2015-05-22 10: 18: 58Z
  4. ArrayDeque'un yığın olarak kullanıldığında Stack'dan daha hızlı ve bir sıra olarak kullanıldığında LinkedList'dan daha hızlı olması muhtemeldir.
    2015-06-17 15: 44: 47Z
  5. akhil_mittal'ın yorumunun ArrayDeque belgesinden alıntı olduğunu unutmayın.
    2015-11-28 22: 47: 55Z

Bu bir verimlilik sorusudur. LinkedList, öğe eklemek ve silmek için hızlı, ancak belirli bir öğeye erişmek için yavaş. ArrayList belirli bir öğeye erişmek için hızlı, ancak her iki ucuna eklemek için yavaş ve özellikle ortada silmek için yavaş olabilir.

Dizi vs ArrayList vs LinkedList vs Vector , daha derinlemesine gider Bağlantılı Liste .

    
59
2018-04-20 06: 12: 45Z

Doğru veya Yanlış: Lütfen yerel olarak test uygulayın ve kendinize karar verin!

Düzenle /Kaldır LinkedList'da ArrayList'dan daha hızlı.

ArrayList tarafından desteklenen ve boyutunun iki katı olması gereken Array büyük hacimli uygulamalarda daha kötü.

Her işlem için birim test sonucu aşağıdadır. Zamanlama Nanosaniye cinsinden verilmiştir.


 
Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

İşte kod:

 
import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}
    
52
2018-04-20 06: 23: 23Z
  1. ArrayList'in kesin olması için iki katına çıkarılması gerekmez. Lütfen önce kaynakları kontrol edin.
    2013-05-06 14: 40: 49Z
  2. Örneğinizin hatalı olduğu belirtilmelidir ... Aşağıdakilerden bir dizgeden çıkarıyorsunuz: 18 + [2, 12] bayt ("true0false", "true500000false "), ortadaki öğelerin boyutları olan ortalama 25 bayt. Öğe baytı boyutu arttıkça bağlantılı liste daha iyi performans gösterir, liste boyutu arttıkça bitişik bir dizi (liste) daha iyi hale gelir. En önemlisi, dizgelerde .equals () yapıyorsunuz - ki bu ucuz bir işlem değil. Bunun yerine tamsayılar kullandıysanız, bir fark olacağını düşünüyorum.
    2014-08-21 09: 40: 10Z
  3. - - ve bu da muhtemelen /include /içeren için çok az bir farkın bulunmasının nedenidir.
    2014-08-21 09: 46: 05Z
  4. "... büyük hacimli uygulamalarda daha kötü ": Bu bir yanlış anlama. LinkedList ek yükü çok daha fazla belleğe sahip çünkü her element için beş alanlı bir düğüm nesnesi var. 20 bayt havai yapan birçok sistemde. ArrayList için öğe başına düşen ortalama ek yük, en kötü durumda 6 bayt ve 8 bayt yapan bir buçuk sözcüktür.
    2015-09-15 09: 53: 40Z
  5. Kriterinizin daha iyi bir versiyonunu yaptım burada, sonuçlarla - Arylist için en son eklenen performans sizin için yapay olarak düşüktür, çünkü addAll bir EXACTLY başlangıç ​​boyutunda bir depolama dizisi verir, bu nedenle ilk ekleme her zaman bir diziyi tetikler. Ayrıca, veri toplanmadan önce JIT derlemesine izin vermek için ısınma döngüleri de dahildir.
    2016-03-10 18: 48: 54Z

ArrayList, esasen bir dizidir. LinkedList, çift bağlantılı bir liste olarak uygulanır.

get oldukça açık. ArrayList için O (1), çünkü ArrayList, endeks kullanarak rastgele erişime izin veriyor. O (n) LinkedList için, çünkü önce dizini bulması gerekiyor. Not: add ve remove'un farklı sürümleri vardır.

LinkedList, ekleme ve çıkarma işlemlerinde daha hızlıdır, ancak alma işlemi daha yavaştır. Kısacası, LinkedList, eğer tercih edilmeli:

  1. öğeye çok sayıda rasgele erişim yok
  2. çok sayıda ekleme /çıkarma işlemi var

=== ArrayList ===

  • ekle (E e)
    • ArrayList'in sonuna ekleyin
    • bellek boyutlandırma maliyetini gerektirir.
    • O (n) en kötü, O (1) amortize edildi
  • add (int index, E öğesi)
    • belirli bir dizin konumuna ekle
    • vites değiştirmeyi & olası bellek yeniden boyutlandırma maliyeti
    • O (n)
  • kaldır (int index)
    • belirtilen bir öğeyi kaldır
    • vites değiştirmeyi & olası bellek yeniden boyutlandırma maliyeti
    • O (n)
  • kaldır (Object o)
    • belirtilen öğenin ilk oluşumunu bu listeden kaldırın
    • önce öğeyi aramalı, sonra & olası bellek yeniden boyutlandırma maliyeti
    • O (n)

=== LinkedList ===

  • ekle (E e)

    • listenin sonuna ekleyin
    • O (1)
  • add (int index, E öğesi)

    • belirtilen konuma yerleştirin
    • önce pozisyonu bulmamız gerekiyor
    • O (n)
  • çıkarın ()
    • listenin ilk öğesini kaldır
    • O (1)
  • kaldır (int index)
    • belirtilen dizini içeren öğeyi kaldır
    • önce öğeyi bulmanız gerekiyor
    • O (n)
  • kaldır (Object o)
    • belirtilen öğenin ilk oluşumunu kaldırın
    • önce öğeyi bulmanız gerekiyor
    • O (n)

İşte programcreek.com 'dan bir rakam > (add ve remove, ilk türdür, yani listenin sonuna bir öğe ekleyin ve öğeyi listede belirtilen konumda kaldırın.): ​​

resim tanımını buraya girin

    
46
2018-05-27 10: 29: 49Z
  1. "LinkedList, eklemek /kaldırmaktan daha hızlıdır". Yanlış, yukarıdaki yanıtı kontrol edin stackoverflow.com/a/7507740/638670
    2013-11-05 10: 00: 00Z

LinkedList'in yazarı Joshua Bloch:

  

Gerçekten LinkedList kullanan var mı? Yazdım ve asla kullanmam.

Bağlantı: https://twitter.com/joshbloch/status/5838139190195748 //p >

Diğer cevaplar kadar bilgilendirici olmadığı için cevap için özür dilerim, ancak bunun en ilginç ve açıklayıcı olacağını düşündüm.

    
34
2017-04-25 10: 23: 06Z
  1. Bu konuya yalnızca Joshua'nın tweet'inden söz edilip edilmediğini kontrol etmek için geldim. Bu :)
    2018-01-15 15: 54: 30Z

ArrayList rasgele erişilebilirken, LinkedList öğeleri genişletmek ve kaldırmak için gerçekten ucuz. Çoğu durumda, ArrayList iyidir.

Büyük listeler oluşturmadıysanız ve bir darboğaz ölçtüyseniz, muhtemelen fark için endişelenmenize gerek kalmayacak.

    
33
2018-04-20 06: 14: 16Z
  1. LinkedList öğelerine ekleme yapmak kolay değil. ArrayList'e bir milyon öğe eklemek, onları LinkedList'e eklemekten daha hızlıdır. Ve gerçek dünya kodundaki listelerin çoğu bir milyon element bile değildir.
    2010-09-10 17: 21: 52Z
  2. Herhangi bir noktada, LinkedList'inize bir öğe eklemenin maliyetini biliyorsunuz. ArrayList değilsiniz (genel olarak). Bir milyon öğeyi içeren bir ArrayList'e tek bir öğe eklemek, çok uzun zaman alabilir - bu bir O (n) işlemidir, ayrıca önceden tahsis edilmediğiniz sürece depolamayı iki katına çıkarır. LinkedList'e bir öğe eklemek O (1) şeklindedir. Son ifadem geçerli.
    2010-09-10 23: 03: 04Z
  3. Bir ArrayList'e tek bir öğe eklemek, 1 milyon veya 1 milyar olursa olsun, O (1) olur. LinkedList'e bir öğe eklemek de O (1). "Ekleme", SONA EKLEME demek.
    2012-05-13 14: 36: 09Z
  4. Uygulamayı benden farklı okumuş olmalısınız. Deneyimlerime göre, 1 milyar element dizisini kopyalamak 1 milyon element dizisini kopyalamaktan daha uzun sürer.
    2012-05-14 05: 57: 35Z
  5. @ kachanov, Dustin'i yanlış anlamalısınız. 1 milyar ürün dizisi bildirmediyseniz, sonunda dizinizi yeniden boyutlandırmanız gerekecek, bu durumda tüm öğeleri daha büyük bir diziye kopyalamanız gerekecek, bu nedenle bazen O (N) olacak O (1) olsun
    2013-03-18 21: 51: 39Z

Kodunuzda add(0) ve remove(0) varsa, bir LinkedList kullanın ve bu daha addFirst() ve removeFirst() yöntemleriyle daha uygundur. Aksi takdirde, ArrayList'u kullanın.

Ve tabii ki, Guava 'nın ImmutableList en iyi arkadaşın.

    
22
2018-04-20 06: 16: 46Z
  1. Küçük listeler için, ArrayList.add (0) yine de her zaman LinkedList.addFirst () öğesinden daha hızlı olacaktır.
    2010-09-10 17: 20: 32Z
  2. - 1. ArrayDeque bu durum için daha iyi.
    2014-08-22 13: 19: 16Z
  3. @ Porculus Sürekli olarak bu argümanı duyuyorum, küçük listeler için ArrayList.add (0) daha hızlı olacak, bu küçüklük ne kadar küçük? 10 element, 10 milyon,?
    2016-09-20 12: 07: 08Z
  4. @ garg10may küçük, 10'dan küçük.
    2016-09-21 14: 53: 12Z

Bunun eski bir yazı olduğunu biliyorum, ama dürüst olmak gerekirse, LinkedList’un Deque’u uyguladığını kimse söylememiştir. Sadece Deque'daki (ve Queue) yöntemlere bakın; Adil bir karşılaştırma yapmak istiyorsanız, LinkedList'a karşı ArrayDeque'u çalıştırmayı deneyin ve özellik için bir karşılaştırma yapın.

    
21
2018-04-20 06: 29: 50Z

ArrayList ve LinkedList'daki ve aynı zamanda CopyOnWrite-ArrayList'daki Büyük O gösterimi:

ArrayList

 
get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

 
get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

 
get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Bunlara dayanarak ne seçeceğine karar vermelisin. :)

    
19
2018-04-20 06: 29: 10Z
  1. > > > > ArrayList add - > O (1) - gerçek değil. Bazı durumlarda, ArrayList'in bir öğe daha eklemek için büyümesi gerekebilir
    2013-02-08 00: 54: 05Z
  2. LinkedList kaldırması O (1) değil, kaldırılacak öğeyi araması gerekiyor, bu nedenle en kötü durumda O (n) ve ortalama O (n /2 )
    2016-09-20 12: 05: 51Z

LinkedList ve ArrayList w.r.t. parametrelerin altında:

1. Uygulama

  

ArrayList , liste arayüzünün yeniden boyutlandırılabilir dizi uygulamasıdır.      

LinkedList , liste arabiriminin Çift bağlantılı liste uygulamasıdır.


2. Performans

  • get (int index) veya arama işlemi

      

    ArrayList get (int index) işlemi sürekli çalışır, yani O (1) iken

         

    LinkedList get (int index) işleminin çalışma süresi O (n) 'dir.

    ArrayList 'in LinkedList'ten daha hızlı olmasının sebebi, ArrayList'in dahili olarak bir dizi veri yapısını kullandığı için öğeleri için dizin tabanlı bir sistem kullanmasıdır,

    LinkedList , belirtilen öğe dizinindeki düğümü almak için başından veya sonundan (hangisi daha yakınsa) yinelendiği için, öğelerine dizin tabanlı erişim sağlamaz.

  • insert () veya add (Object) işlemi

      

    LinkedList içindeki ekler genellikle ArrayList ile karşılaştırıldığında hızlıdır. LinkedList'te ekleme veya ekleme O (1) işlemidir.

         

    ArrayList 'de, dizi tam yani en kötü durum ise, dizi yeniden boyutlandırma ve öğeleri yeni diziye kopyalamanın ekstra bir maliyeti vardır, bu ArrayList O'da ekleme işlemi çalışma zamanı yapar ( n) aksi takdirde O (1) 'dir.

  • (int) işlemini kaldır

    LinkedL'deki işlemi kaldırist, genellikle ArrayList yani O (n) ile aynıdır.

      

    LinkedList 'de iki aşırı yüklenmiş kaldırma yöntemi vardır. bunlardan biri listenin başını kaldıran ve O (1) sabit sürelerinde çalışan herhangi bir parametre olmadan remove () işlevidir. LinkedList'teki diğer aşırı yüklenmiş kaldırma yöntemi, Object'i veya parametre olarak geçirilen int'yi kaldıran remove (int) veya remove (Object) 'dir. Bu yöntem, Object'i bulana ve orijinal listeden bağlantısını kaldırana kadar LinkedList'i geçirir. Dolayısıyla bu yöntem çalışma zamanı O (n) 'dir.

         

    ArrayList 'de remove (int) yöntemi, öğeleri eski diziden yeni güncellenmiş diziye kopyalamayı içerir, dolayısıyla çalışma zamanı O (n)' dir.


3. Ters Yineleyici

  

LinkedList , descendingIterator () iken

kullanılarak ters yönde yinelenebilir.      

ArrayList 'de descendingIterator () yok, bu nedenle ArrayList üzerinde ters yönde yineleme yapmak için kendi kodumuzu yazmamız gerekiyor.


4. İlk Kapasite

  

Yapıcı aşırı yüklenmediyse, ArrayList başlangıç ​​kapasitesi 10 olan boş bir liste oluşturur.      

LinkedList boş listeyi yalnızca başlangıç ​​kapasitesi olmadan oluşturur.


5. Bellek Yükü

  

LinkedList 'deki bellek ek yükü, bir sonraki ve önceki düğümün adreslerini korumak için LinkedList'teki bir düğüm gibi ArrayList ile karşılaştırıldığında daha fazladır. İken

     

ArrayList 'te her bir dizin yalnızca gerçek nesneyi (verileri) tutar.


Kaynak

    
15
2018-07-24 15: 49: 31Z

TL; DR , modern bilgisayar mimarisi nedeniyle, ArrayList hemen hemen tüm olası kullanım durumları için önemli ölçüde daha verimli olacaktır - ve bu nedenle çok benzersiz ve aşırı durumlar dışında LinkedList'dan kaçınılmalıdır.


Teoride LinkedList, add(E element) için bir O (1) değerine sahiptir

Ayrıca listenin ortasına bir öğe eklemek çok verimli olmalıdır.

Alıştırma çok farklı, çünkü LinkedList bir Önbellek Düşmanı Veri yapısı. POV performansından - LinkedList’un Önbellek dostu ArrayList’dan daha iyi performans gösterebileceği çok az durum vardır.

Burada, rasgele konumlara öğe ekleyen bir kıyaslama testinin sonuçları verilmiştir. Gördüğünüz gibi - çok daha verimli ise dizi listesi, teoride listenin ortasındaki her bir ek, dizinin sonraki öğelerinde n öğelerinin "taşınmasını" gerektirir (düşük değerler daha iyidir):

 buraya resim açıklamasını girin

Sonraki nesil bir donanımda çalışmak (daha büyük, daha verimli önbellek) - sonuçlar daha da kesindir:

 buraya resim açıklamasını girin

LinkedList, aynı işi başarmak için çok daha fazla zaman alır. kaynak Kaynak Kodu

Bunun iki ana nedeni var:

  1. Temelde - LinkedList'un düğümlerinin bellek üzerinde rastgele dağıldığını gösterir. RAM ("Random Access Memory") gerçekten rastgele değildir ve önbellek için hafıza bloklarının alınması gerekir. Bu işlem zaman alıyor ve bu tür alımlar sık ​​sık gerçekleştiğinde - önbellekteki bellek sayfalarının her zaman değiştirilmesi gerekiyor - > Önbellek özlüyor - > Önbellek verimli değil.  ArrayList öğe sürekli bellekte depolanır - bu da tam olarak modern CPU mimarisinin en iyi duruma getirdiği şeydir.

  2. İkincil LinkedList, ileri /geri işaretleyicileri tutmak için gerekliydi; bu, ArrayList'a kıyasla depolanan değer başına bellek tüketiminin 3 katı anlamına gelir.

DynamicIntArray , btw, Int (ilkel tür) ve Object'leri içeren özel bir ArrayList uygulamasıdır - bu nedenle tüm veriler gerçekten bitişik olarak depolanır - dolayısıyla daha da verimlidir.

Hatırlanması gereken en önemli unsurlardan biri, bellek bloğunu getirmenin maliyetinin, tek bir hafıza hücresine erişen maliyetten daha önemlidir. Bu nedenle, 1 MB sıralı bellek okuyucusunun farklı bellek bloklarından bu miktarda veri okumaktan x400 kat daha hızlı olması:

 
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Kaynak: Her Programcının Bilmesi Gereken Gecikme Numaraları

Sadece noktayı daha da netleştirmek için lütfen listenin başına öğe ekleme kriterini kontrol edin. Bu, teoride LinkedList'un gerçekten parlaması ve ArrayList'un kötü veya daha kötü durum sonuçları sunması gereken bir kullanım durumudur:

 buraya resim açıklamasını girin

Not: Bu, C ++ Std lib'in bir ölçütüdür, ancak önceki deneyimim C ++ ve Java sonuçlarının çok benzer olduğunu gösterdi. Kaynak Kodu

Sıralı bir bellek yığınını kopyalamak, modern CPU'lar tarafından optimize edilmiş bir işlemdir - teoriyi değiştirir ve aslında ArrayList /Vector'u çok daha verimli hale getirir


Krediler: Burada yayınlanan tüm kriterler Kjell Hedström tarafından oluşturulmuştur. blogu

'da daha da fazla veri bulunabilir.     
15
2018-10-19 03: 06: 19Z
  1. Benzersiz veya aşırı bir sıra istemem! Beşinci sıra, ArrayList yerine LinkedList'te çok daha kolaydır. ArrayList'teki bir kabus, kendi başlangıcınızı izlemek, durdurmak ve kendi yeniden tahsisinizi yapmak zorundasınız, bir dizi de kullanabilirsiniz, ancak Bağlantılı Liste bir ikiye ayrıldı. Java'nın uygulanmasından emin değilim, ancak LinkedList, hem kuyruk hem de temizleme işlemleri için O (1) yapabilir (java’nın sahip olduğunu varsaydığım ama kaldırdığım için kuyruk öğesine özel bir işaretçi gerektirir. .)
    2018-12-28 18: 26: 46Z

Yukarıdaki diğer iyi argümanlara ek olarak, ArrayList'un RandomAccess arabirimini uygularken LinkedList'un Queue'u uygulayacağını fark etmelisiniz.

Yani, bir şekilde verimlilik ve davranış farklılığıyla biraz farklı sorunları ele alıyorlar (yöntem listesine bakınız).

    
13
2018-04-20 06: 15: 53Z
9
2011-09-05 06: 33: 52Z
  1. Merhaba @chharvey, Link sadece cevaplar 6 Alındı ​​mı? Lütfen bağlantıyı destekleyebilecek bazı noktalar ekleyin. Peki ya Oracle bağlantılarını değiştirirse?
    2017-11-14 06: 08: 22Z

Bir dizi listesi, temel olarak öğe vb. ekleme yöntemlerini içeren bir dizidir (bunun yerine genel bir liste kullanmanız gerekir). Dizin oluşturucudan erişilebilen bir öğe koleksiyonudur (örneğin [0]). Bir öğeden diğerine ilerleme anlamına gelir.

Bağlantılı bir liste, bir öğeden diğerine bir ilerleme belirtir (Öğe a - > öğe b). Bir dizi listesiyle aynı etkiyi elde edebilirsiniz, ancak bağlantılı bir liste kesinlikle hangi öğenin önceki öğeyi izlemesi gerektiğini söylüyor.

    
8
2010-04-20 15: 32: 01Z

Bu, Listede hangi işlemleri daha çok yapacağınıza bağlıdır.

ArrayList iİndekslenmiş bir değere erişmek için daha hızlı. Nesne eklerken veya silerken çok daha kötü.

Daha fazla bilgi için, diziler ve bağlantılı listeler arasındaki farktan bahseden tüm makaleleri okuyun.

    
8
2018-04-20 06: 14: 59Z
  1. Daha fazlasını öğrenmek için okuma, sadece kodu yaz. ArrayList uygulamasının yerleştirme ve silme işleminde LinkedList'ten daha hızlı olduğunu göreceksiniz.
    2012-05-18 02: 53: 36Z

Genelde, belirli bir Listede gerçekleştirdiğim işlemlerin zaman karmaşıklığına bağlı olarak bir başkasını kullanırım.

 
|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|
    
8
2019-02-18 07: 08: 01Z
  1. ArrayDeque, ön /arkaya ekleme /çıkarma işlemlerinin tümü O (1) olduğu için Dizilere göre işleri biraz daha dengede tutar. gezinirken (Yineleyici işlemleri).
    2019-02-21 18: 24: 59Z

Bağlantılı bir listenin (başka bir cevabında okumadığım) önemli bir özelliği iki listenin birleştirilmesidir. Bir diziyle bu, O (n) 'dir (+ bazı yeniden tahsislerin ek yükü) bağlantılı bir listeyle bu sadece O (1) veya O (2) ;-)

Önemli : Java için LinkedList bu doğru değil! Bkz. Java’daki bağlantılı liste için hızlı bir concat yöntemi var mı?

    
7
2017-05-23 12: 02: 46Z
  1. Bu nasıl? Bağlantılı liste veri yapıları için bu doğru olabilir ancak bir Java LinkList nesnesi olmayabilir. Bir next'u bir listeden ikinci listedeki ilk düğüme gösteremezsiniz. Tek yol, elemanları sırayla ekleyen addAll()'u kullanmaktır, bununla birlikte, her bir eleman için döngü yapmak ve add()'u aramaktan daha iyidir. Bunu O (1) 'de hızlı bir şekilde yapmak için, bir kompozisyon sınıfına (org.apache.commons.collections.collection.CompositeCollection gibi) ihtiyacınız olacak, ancak daha sonra bu her türlü Liste /Koleksiyon için işe yarayacaktır.
    2010-03-23 ​​00: 42: 31Z
  2. evet, doğru. Cevabı buna göre düzenledim. ancak LinkedList ile 'nasıl' yapılacağı için bu cevaba bakınız: stackoverflow.com/questions/2494031/…
    2010-03-23 ​​12: 47: 46Z

Yanıtları okudum, ancak bir ArrayList üzerinde her zaman LinkedList'i kullanarak fikirleri paylaşmak için paylaşmak istediğim bir senaryo var:

Bir DB'den elde edilen verilerin listesini döndüren bir yöntemim olduğunda, her zaman LinkedList kullanırım.

Benim mantığım şuydu, ne kadar sonuç aldığımı tam olarak bilmek imkansız olduğundan, hafızanın boşa harcanmayacağı (kapasite ve gerçek öğe sayısı arasındaki ArrayList'teki gibi) ve zamanın olmayacağıydı. kapasiteyi çoğaltmaya çalışırken boşa.

Bir ArrayList'e kadar, dizilerin çoğaltılmasını olabildiğince asgariye indirmek için en azından yapıcıyı her zaman başlangıç ​​kapasitesiyle kullanmanız gerektiğine katılıyorum.

    
6
2011-10-03 23: 23: 00Z

ArrayList ve LinkedList’in kendi avantajları ve dezavantajları vardır.

ArrayList, bir sonraki düğüme doğru işaretçiler kullanan LinkedList ile karşılaştırıldığında bitişik bellek adresini kullanır. Bu nedenle, bir ArrayList'teki bir öğeyi aramak istediğinizde LinkedList ile yineleme yapmaktan daha hızlıdır.

Diğer yandan, LinkedList'e ekleme ve silme işlemi çok daha kolaydır, çünkü yalnızca işaretçileri değiştirmeniz gerekir; oysa ArrayList, herhangi bir ekleme veya silme için vardiya işlemi kullanımı anlamına gelir.

Uygulamanızda sık sık alım işlemleriniz varsa, bir ArrayList kullanın. Sık sık ekleme ve silme işlemine sahipseniz LinkedList kullanın.

    
6
2017-10-21 01: 58: 43Z

ArrayList ve LinkedList, List interface'u uygular ve bunların yöntemleri ve sonuçları neredeyse aynıdır. Ancak, gereksinime bağlı olarak birbirini daha iyi yapan, aralarında çok az fark vardır.

ArrayList - LinkedList

1) Search: ArrayList arama işlemi, LinkedList arama işlemine kıyasla oldukça hızlıdır. get(int index)’da ArrayList, O(1)’un performansını verirken, LinkedList’un O(n)’u

Reason: ArrayList, dizi veri yapısını dolaylı olarak kullandığı için listesindeki bir öğeyi aramayı daha hızlı hale getirdiğinden, öğeleri için dizin tabanlı sistemi korur. Diğer taraftan LinkedList, bir eleman aramak için tüm elemanlar arasında geçişi gerektiren iki kat bağlantılı bir liste uygular.

2) Deletion: LinkedList kaldırma işlemi O(1) performans verirken ArrayList değişken performans verir: en kötü durumda O(n) (ilk elemanı kaldırırken) ve en iyi durumda O(1) (son elemanı kaldırırken).

  

Sonuç: LinkedList öğesinin silinmesi karşılaştırıldığında daha hızlı   ArrayList.

Sebep: LinkedList’in her öğesi, listedeki her iki komşu öğeye de işaret eden iki işaretçi (adres) tutar. Bu nedenle kaldırılması, yalnızca kaldırılacak olan düğümün iki komşu düğümündeki (eleman) işaretçi konumunda değişiklik gerektirir. ArrayList'te, kaldırılan öğenin oluşturduğu boşluğu doldurmak için tüm öğelerin kaydırılması gerekir.

3) Inserts Performance: LinkedList ekleme yöntemi O(1) performans verirken, ArrayList en kötü durumda O(n) verir. Sebep, kaldırma için açıklananla aynı.

4) Memory Overhead: ArrayList, dizinleri ve öğe verilerini korurken, LinkedList, öğe verilerini ve komşu düğümler için iki işaretçiyi korur

  

bu nedenle, LinkedList'te bellek tüketimi nispeten yüksektir.

Bu sınıflar arasında aşağıdaki gibi bir kaç benzerlik vardır:

  • Hem ArrayList hem de LinkedList, Liste arabiriminin uygulamasıdır.
  • Her ikisi de öğe ekleme sırasını korur, bu da ArrayList ve LinkedList öğelerini görüntülerken sonuç kümesinin, öğelerin Listeye eklendiği sırayla aynı olacağı anlamına gelir.
  • Her iki sınıf da senkronize değildir ve Collections.synchronizedList yöntemi kullanılarak açık bir şekilde senkronize edilebilir.
  • Bu sınıflar tarafından döndürülen iterator ve listIterator, fail-fast'dur (liste, yineleyici oluşturulduktan sonra herhangi bir zamanda yapısal olarak değiştirilirse, iterator’s'un kendi çıkarması veya ekleme yöntemleri dışında herhangi bir şekilde yineleyici, throw'un ConcurrentModificationException'u olacaktır). /li>

LinkedList ne zaman ve ArrayList ne zaman kullanılır?

  • Yukarıda açıklandığı gibi, ekleme ve çıkarma işlemleri (O(1))'daki LinkedList'a kıyasla ArrayList(O(n))'da iyi performans verir.
      

    Dolayısıyla, uygulamada sık sık ekleme ve silme gereksinimi varsa, LinkedList en iyi seçimdir.

  • Arama (get method) işlemleri Arraylist (O(1))’da hızlıdır ancak LinkedList (O(n))’da
      

    bu nedenle daha az ekleme ve kaldırma işlemi ve daha fazla arama işlemi gereksinimi varsa, ArrayList en iyi bahsiniz olur.

5
2016-11-02 09: 00: 23Z

ArrayList'te işlem (i), LinkedList'ten daha hızlıdır, çünkü:
ArrayList: Liste arabiriminin yeniden boyutlandırılabilir dizisi uygulaması
LinkedList: Doubly Liste ve Deque arayüzlerinin bağlantılı liste uygulaması

OperasyonlarListedeki bu dizin, belirtilen dizine hangisi daha yakınsa listeyi en baştan veya en sondan başlatacak.

    
5
2016-11-09 10: 48: 34Z

1) Temel Veri Yapısı

ArrayList ile LinkedList arasındaki ilk fark, ArrayList'in ArrayList tarafından desteklenirken LinkedList LinkedList tarafından desteklendiğinden kaynaklanmaktadır. Bu, performansta daha fazla farklılıklara yol açacaktır.

2) LinkedList, Deque uygular

ArrayList ve LinkedList arasındaki diğer bir fark, List arabiriminin yanı sıra, LinkedList'in add () ve poll () ve diğer birçok Deque işlevi için ilk giren ilk çalıştırma işlemlerini sağlayan Deque arabirimini de uygulamasıdır. 3) ArrayList öğelerinde öğe ekleme ArrayList öğesinde öğe ekleme, Array öğesinin yeniden boyutlandırılmasını tetiklemezse O (1) işlemidir, bu durumda O (log (n)) olur, diğer taraftan, LinkedList, herhangi bir gezinme gerektirmediğinden O (1) işlemidir.

4) Bir öğeyi bir konumdan kaldırma

Bir öğeyi belirli bir dizinden kaldırmak için; remove (index) öğesini çağırarak, ArrayList, O (n) konumuna yakın olan bir kopya işlemi gerçekleştirir, LinkedList bu noktaya geçmelidir, bu da onu O (n /2) konumuna getirir, çünkü her iki yönden de yaklaşabilir. .

5) ArrayList veya LinkedList'te yineleme

Yineleme, LinkedList ve ArrayList öğelerinin her ikisi için de bir öğe olduğu O (n) işlemidir.

6) Öğeyi bir konumdan alma

get (index) işlemi ArrayList'teki O (1) iken LinkedList'teki O (n /2), o girdiye kadar geçmesi gerekir. Yine de, Büyük O'da notasyon O (n /2) sadece O (n) çünkü oradaki sabitleri görmezden geliyoruz.

7) Bellek

Linkedinist, ArrayList yalnızca Array öğesinde veri depolarken, sonraki ve önceki iki düğümü saklamak için statik bir iç içe sınıf olan Entry, bir sarmalayıcı nesnesi kullanır.

Bu nedenle, ArrayList durumunda, içeriği Array'den diğerine kopyaladığında, Array'in yeniden boyutlandırma işlemini gerçekleştirdiği durumlar dışında, bellek gereksinimi daha az görünür.

Dizi yeterince büyükse, bu noktada çok fazla bellek alabilir ve yanıt süresini yavaşlatabilecek Çöp toplamasını tetikleyebilir.

ArrayList ile LinkedList arasındaki tüm yukarıdaki farklılıklardan ArrayList, neredeyse her durumda, remove () veya get () işlevinden daha sık bir add () işlemi yaptığınız durumlar dışında, ArrayList'in LinkedList'ten daha iyi bir seçim olduğunu gösterir.

Bağlantılı bir listeyi değiştirmek ArrayList'ten daha kolaydır, özellikle de baştan veya sondan eleman ekler veya çıkarırsanız, bağlantılı liste dahili olarak bu konumların referanslarını tutar ve O (1) zamanında erişilebilir durumda olur.

Başka bir deyişle, eleman eklemek istediğiniz pozisyona ulaşmak için bağlantılı listede dolaşmanız gerekmez, bu durumda toplama O (n) işlemi olur. Örneğin, bağlantılı bir listenin ortasına bir öğe ekleme veya silme.

Benim düşünceme göre, Java'daki pratik amaçların çoğu için LinkedList üzerinden ArrayList kullanın.

    
5
2018-07-24 16: 01: 05Z
  1. Bence buradaki tüm grubun en iyi belirtilen cevabı. Doğru ve bilgilendirici. Son satırın değiştirilmesini öneririm - sonunda, bağlantılı listeler için hiçbir anlam ifade etmeyen çok önemli yapılar olan "kuyrukların yanı sıra" eklemeyi de tavsiye ederim.
    2018-12-28 18: 33: 04Z

Hem remove () hem de insert (), ArrayLists ve LinkedLists için O (n) çalışma zamanı verimliliğine sahiptir. Bununla birlikte, doğrusal işlem süresinin arkasındaki neden iki çok farklı sebepten kaynaklanmaktadır:

Bir ArrayList'te, O (1) öğesindeki öğeye ulaşırsınız, ancak aslında bir şeyin kaldırılması veya eklenmesi O (n) öğesini yapar, çünkü aşağıdaki tüm öğelerin değiştirilmesi gerekir.

LinkedList'te aslında istenen öğeye ulaşmak için O (n) gerekir, çünkü istenen dizine ulaşana kadar en baştan başlamak zorundayız. Aslında kaldırma veya takma sabittir, çünkü bizyalnızca remove () için 1 referansı ve insert () için 2 referansı değiştirmek zorundasınız.

Takma ve çıkarma için ikisinden hangisinin daha hızlı olduğu, nerede olduğuna bağlıdır. Eğer başlangıcımıza daha yakın olursak LinkedList daha hızlı olacaktır çünkü nispeten az sayıda elementten geçmek zorundayız. Sona yaklaşırsak, bir ArrayList daha hızlı olacaktır, çünkü oraya sabit zamanda varacağız ve onu takip eden sadece birkaç kalan öğeyi değiştirmek zorunda kalacağız. Kesin olarak ortada yapıldığında LinkedList daha hızlı olacaktır çünkü n elemanlarından geçmek hareketli n değerlerinden daha hızlıdır.

Bonus: Bir ArrayList için bu iki yöntemi O (1) yapmanın bir yolu olmamasına rağmen, aslında LinkedLists'ta bunu yapmanın bir yolu yoktur. Diyelim ki tüm Listeyi yolumuza ekleyip öğeleri ekleyerek geçmek istiyoruz. Genellikle LinkedList'i kullanarak her bir eleman için en baştan başlarsınız, üzerinde çalıştığımız mevcut öğeyi bir Yineleyici ile “kaydedebiliriz”. Yineleyici yardımıyla, LinkedList'te çalışırken remove () ve insert () için O (1) verimlilik elde ediyoruz. Bunu tek performans avantajı yaparak LinkedList'in her zaman bir ArrayList'ten daha iyi olduğunun farkındayım.

    
2
2018-07-24 16: 14: 23Z

ArrayList, AbstractList'i genişletir ve Liste Arayüzünü uygular. ArrayList, dinamik bir dizidir.
Dizilerin dezavantajlarının üstesinden gelmek için temelde oluşturulduğu söylenebilir

LinkedList sınıfı, AbstractSequentialList öğesini genişletir ve List, Deque ve Queue arabirimini uygular.
Performans
arraylist.get(), O (1) iken, linkedlist.get(), O (n) 'dir. arraylist.add(), O (1) ve linkedlist.add(), 0 (1)' dir. n)
arraylist.contains(), O (1) ve linkedlist.contains(), O (1)
arraylist.next(), O (n), linkedlist.next(), O (1)
Arraylist'te arraylist.remove(), O (n) 'dır, oysa bağlantılı listede, linkedlist.remove(), O (1) dir.

    
1
2018-02-20 21: 51: 19Z

Burada gördüğüm testlerden biri testi sadece bir kez yapıyor. Ama farkettim ki, bu testleri bir çok kez denemeniz gerekiyor ve sonunda onların zamanları birleşiyor. Temel olarak JVM'nin ısınması gerekiyor. Özel kullanım durumum için, yaklaşık 500 öğeye ulaşan bir son ürüne ekleme /çıkarma yapmam gerekiyordu. Testlerimde iterator.remove() daha hızlı çıktı, iterator.remove()'u yaklaşık 50.000 NS geliyor ve LinkedList'u yaklaşık 90.000 NS geliyor ... ver ya da al. Aşağıdaki koda bakın.

 LinkedList     
1
2018-08-04 18: 52: 06Z
ArrayList
kaynak yerleştirildi İşte