Java documentation for the ADT List okuma diyor

Liste listesi arayüzü elemanları için (endeksli) konumsal erişim için dört yöntem sağlar. Listeleri (Java diziler gibi) sıfır tabanlı. Bu işlemler bazı uygulamaları (LinkedList sınıfı, örneğin) için endeks değeri ile doğru orantılı zamanında yürütmek unutmayın. Böylece, bir listedeki öğeleri üzerinden yineleme eğer arayan uygulanması biliyor mu yoksa genelde içinden indeksleme için tercih edilir.

Tam olarak bu ne anlama geliyor? Çıkartılan sonuç, anlamıyorum.

Bağlantılı liste, her elemanı bir sonraki elemanı gösteren bir işaretçi vardır:

head -> item1 -> item2 -> item3 -> etc.

Erişim için item3, sana ulaşmak yapamazsınız, çünkü item3, doğrudan atlamak kadar her düğüm ile kafa yürüyerek gerektiğini açıkça görebilirsiniz.

Eğer bu yazarsam her öğenin değerini yazdırmak istesem böylece:

for(int i = 0; i < 4; i  ) {
    System.out.println(list.get(i));
}

ne olur bu

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

Bukorkunç verimsizçünkü her zaman listenin en başında yeniden dizin oluşturma ve her maddenin içinden geçiyor. Bu karmaşıklığı etkin O(N^2) sadece gez listesi olduğu anlamına gelir!

Bunun yerine yaptığım bu

for(String s: list) {
    System.out.println(s);
}

olay şöyle gelişir:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

O(N) tek bir geçiş,.

Şimdi, basit bir dizi tarafından desteklenen ArrayList, List diğer uygulama olacak. Bu durumda yukarıdaki dolaşımları de bir dizi keyfi pozisyonlar için rastgele atlar sağlar çok bitişik olduğu için eşdeğerdir.