LinkedList kolleksiyası ilə tanışlıq

1. LinkedList Tarixi

Java-da başqa bir kolleksiya sinfi də var ki, bu, Java-ya C++ dilindən miras qalıb. Bu sinif LinkedList adlanır, "Bağlı Siyahı" kimi tərcümə olunur.

Xaricdən baxanda LinkedList, ArrayList ilə eyni siyahıdır. LinkedList sinifinin ArrayList sinfi ilə eyni metodları var. Prinsipcə, həmişə LinkedList-dən ArrayList-in yerinə istifadə edə bilərsiniz və hər şey işləyəcək.

Bəs niyə başqa bir siyahı sinfi lazımdır?

Söhbət LinkedList sinfinin daxili quruluşundadır. Orada massiv yerinə iki bağlı siyahı istifadə olunur. Bunun nə olduğunu bir az sonra danışacağıq.

Başqa bir daxili quruluş sayəsində LinkedList sinfinin siyahının ortasına elementlər yerləşdirmək əməliyyatı çox sürətlidir.

İnternetdə tez-tez ArrayList və LinkedList siniflərinin belə bir müqayisəsini görmək olar:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Hər şey başa düşüləndir kimi görünür: əgər siyahıya tez-tez elementlər əlavə etmək lazımdırsa, LinkedList-dən istifadə edin, əks halda ArrayList. Amma əslində vəziyyət bir az fərqlidir.

2. Heç kim LinkedList-dən istifadə etmir

Heç kim LinkedList-dən istifadə etmir.

Hətta yaxınlarda LinkedList sinifinin müəllifi öz Twitter-də bir post yazıb: "Dostlar, ümumiyyətlə kimsə LinkedList-dən istifadə edir? 20 il ərzində mən heç vaxt ondan istifadə etməmişəm!".

Bəs problem nədədir?

Birincisi, ArrayList sinfi elementləri siyahının ortasına çox sürətlə əlavə edir. Siyahının ortasına bir elementi əlavə etmək üçün lazım olan elementlərin hamısını siyahının sonuna doğru bir addım sürüşdürmək lazım olur. Əvvəllər bu vaxt alırdı.

Ancaq indi hər şey dəyişib. Mətrisin bütün elementləri eyni yaddaş blokunda yerləşir, buna görə də elementlərin sürüşdürülməsi əməliyyatı çox aşağı səviyyəli sürətli System.arraycopy() komandasını istifadə etməklə həyata keçirilir.

Bundan əlavə, müasir prosessorların böyük keşləri var və adətən bütün mətrisi keşə yerləşdirir, buna görə də elementlərin sürüşdürülməsi yaddaşda deyil, prosessorun keşində baş verir. Bir milyon element bir millisekundda asanlıqla sürüşdürülür.

İkincisi, LinkedList sinfi elementləri çox sürətlə əlavə edir, əgər iterator vasitəsilə əlavə edirsinizsə. Əgər iterator vasitəsilə LinkedList siyahısından keçirsinizsə və davamlı yeni elementlər əlavə edirsinizsə (və ya mövcud olanları silirsinizsə), bu, həqiqətən, super sürətli bir əməliyyatdır.

Əgər sadəcə olaraq dövrədə LinkedList-ə elementlər əlavə edirsinizsə, hər sürətli əlavə əməliyyatına əlavə olaraq "elementin əldə olunması" adlı yavaş əməliyyat əlavə olunur.

Reallıq daha çox bu vəziyyətə bənzəyir:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Bəs niyə LinkedList-də elementin əldə olunması əməliyyatı bu qədər yavaşdır?

Bu sualın cavabını öyrənmək istəyirsinizsə, LinkedList-in quruluşunu bir az araşdırın

3. LinkedList-in quruluşu

LinkedList daxili struktur olaraq ArrayList ilə müqayisədə alternativ bir quruluşa malikdir. Elementləri saxlamaq üçün daxilində massiv yoxdur. Bunun yerinə iki bağlı siyahı adlanan bir məlumat strukturu istifadə edir.

İki bağlı siyahının hər elementi əvvəlki və sonrakı elementlərə istinadları saxlayır. Bu, bir növ növbəyə bənzəyir, burada hər bir insan qarşısındakı və arxasındakı insanı yadda saxlayır.

Belə bir siyahının yaddaşda necə göründüyünə baxaq:

Kənarlarda (boz fon) first və last dəyişənləri var, onlar Node tipindəki obyektlərə istinadları saxlayır.

Ortada isə Node tipindəki obyektlərin zəncirini görürsünüz (dəyişənlər deyil, obyektlər). Hər biri üç sahədən ibarətdir:

• prev — əvvəlki Node obyektinə istinadı saxlayır (sarı fon).
• value — siyahının elementi olan deyəri saxlayır (yaşıl fon).
• next — növbəti Node obyektinə istinadı saxlayır (mavi fon).

İkinci obyekt (ünvan == F24) birincinin növbətisi (next) və üçüncünün əvvəlkisi (prev) olur. Üçüncü obyektin sarı sahəsi F24 istinadını saxlayır, birinci obyektin mavi sahəsi isə yenə F24 istinadını saxlayır.

Birinci və üçüncü obyektlərin oxları eyni ikinci obyektə işarə edir. Buna görə də, oxları belə çəkmək daha düzgün olardı.

4. Bağlantılı siyahıya elementi daxil etmək

Belə bir növbəyə insan əlavə etmək üçün sadəcə iki qonşunun razılığı lazımdır. Onlardan birincisi yeni gələn haqqında belə deyir: "bu adam məndən sonra gəlir", ikincisi isə: "bu adam məndən əvvəl gəlir".

Sadəcə olaraq iki qonşu obyektin istinadlarını dəyişmək lazımdır:

Biz siyahımıza yeni bir element əlavə etdik və ikinci və üçüncü obyektlərin istinadlarını dəyişdik. İndi yeni gələn ikinci obyektdən sonra və üçüncü obyekt üçün əvvəlki olaraq yerləşdirilib. Və elə həmin yeni gələn obyektin özü üçün də düzgün istinadlar daxil edilməlidir: əvvəlki obyekt - ikinci, növbəti obyekt - üçüncü.

Silinmə daha da sadədir. Əgər biz məsələn 100-cü obyekti siyahıdan silmək istəyiriksə, sadəcə 99-cu obyektin next-ini dəyişib onu 101-ci obyektə göstərmək lazımdır, 101-ci obyektin isə prev-ini dəyişib onu 99-a göstərmək lazımdır. Vəssalam.

Lakin sadəcə olaraq 100-cü obyekti tapmaq heç də asan deyil.

5. Siyahının elementini əldə etmək

Bağlı siyahının 100-cü elementini əldə etmək üçün:

1-ci obyektə keçid almaq: ona first dəyişəni vasitəsilə LinkedList obyektində müraciət olunur. 1-ci obyektin 2-ci obyektə keçidi ( next sahəsi) var. Bunun vasitəsilə ikinci obyekti əldə edirik. 2-ci obyektin üçüncü obyektə keçidi var və s.

Əgər 100-cü obyektə keçid lazım olsa, bir-bir 1-dən 100-ə qədər bütün obyektləri ardıcıl olaraq keçmək gərəkir. Əgər siyahıda milyonuncu elementi tapmaq lazım olsa, bağlamada olan milyon obyektləri bir-bir yoxlamaq lazımdır!

Əlavə olaraq, əgər bu obyektlər siyahıya fərqli vaxtlarda daxil edilibsə, onlar yaddaşın müxtəlif yerlərində yerləşəcəklər və çox güman ki, bir anda prosessorun keşinə daxil olmayacaqlar. Bu da o deməkdir ki, bağlı siyahıda elementlərin ardıcıl axtarışı – yavaş yox, həddindən artıq yavaş bir işdir.

Belə işlər.

Bəs niyə bu yavaş LinkedList-in necə qurulduğunu öyrənirik?

Məsələ ondadır ki, iş müsahibəsində sizdən mütləq soruşacaqlar ki, LinkedList və ArrayList arasındakı fərqlər nədir. Mütləq.