LinkedList kolleksiyasi bilan tanishuv

1. LinkedList tarixi

Java'da yana bir kolleksiya klassi mavjud, bu Java'ga C++ tilidan meros bo'lib o'tgan. Bu LinkedList klassi, bu "Bog'langan ro'yxat" deb tarjima qilinadi.

Tashqi ko'rinishida LinkedList — ArrayList kabi bir xil ro'yxat. LinkedList klassida ArrayList klassida bo'lgan barcha metodlar mavjud. Va aslida siz har doim LinkedList ishlatishingiz mumkin ArrayList o'rniga, va hammasi ishlaydi.

Xo'sh, nega yana bir klass-ro'yxat kerak?

Barcha gap LinkedList klassining ichki tuzilishida. U yerda massiv o'rniga ikki bog'langan ro'yxat ishlatiladi. Bu nima ekanligi haqida birozdan keyin gaplashamiz.

Lekin boshqa ichki tuzilish hisobiga LinkedList klassda — ro'yxat o'rtasiga elementlarni qo'shishning eng tezkor operatsiyasi mavjud.

Internetda tez-tez ArrayList va LinkedList klasslarini bunday taqqoslashni ko'rish mumkin:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Hammasi tushunarli: agar ko'p marta elementlarni ro'yxatga qo'shish kerak bo'lsa, LinkedList ishlating, aks holda ArrayList. Ammo aslida bu ancha boshqacha.

2. Hech kim LinkedList ishlatmaydi

Hech kim LinkedList ishlatmaydi.

Yaqinda o'zining muallifi LinkedList klassi koda Twitterda post qildi: "Biron nima qilayotganlar bormi LinkedList? 20 yildan beri uni bir marta ham ishlatmadim!"

Bu bilan bog'liq nima muammo bor?

Birinchidan, ArrayListklass o'rtacha ko'rsatkichdagi elementni juda tez qo'sha boshladi. Ro'yxat o'rtasiga element qo'shish kerak bo'lganda, kerakli elementdan keyin barcha elementlarni 1 ta pozitsiyaga qo'shish kerak. Oldinda bu vaqtni olardi.

Lekin hozir hammasi o'zgardi. Barcha massiv elementlari bir blok xotirada joylashgan, shuning uchun massiv elementlarining joyini o'zgartirib qo'yish operatsiyasi juda tez chuqur darajadagi buyruq bilan amalga oshiriladi System.arraycopy().

Hamda, hozirda protsessorlarda katta kesh bor, va odatda barcha massiv keshga kiritiladi, shuning uchun massiv elementlari xotirada emas, balki protsessor keshida joylashtiriladi. Bir million elementni o'zgartirish bir milisekundaga oson erishiladi.

Ikkinchidan, klass LinkedList elementlarni tez qo'shadi, agar siz ularni iterator orqali qo'shsangiz. Agar siz LinkedList ro'yxatini iterator orqali o'tib,yangi elementlarni qo'shsangiz (yoki mavjud elementlarni o'chirsangiz), bu rostdan juda tez operatsiya.

Agar shunchaki LinkedList klassi ichiga bir tsiklda elementlarni qo'shsangiz, har bir tez qo'shish operatsiyasiga "elementni olish" so'nggi sekin operatsiya qo'shiladi.

Asl holat yanada yaqinroq bo'ladi:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Nega LinkedList da elementni olish operatsiyasi juda sekin?

Siz LinkedList tuzilmasi bilan biroz tanishsangiz, bunga javob topasiz.

3. LinkedList tuzilmasi

LinkedList ichki tuzilmasi ArrayList bilan solishtirilganda boshqacha. Elementlar saqlash uchun massiv yo'q. Buning o'rniga u ikki bog'langan ro'yxat deb ataladigan ma'lumotlar strukturasi ishlatiladi.

Har bir element ikki bog'langan ro'yxatda oldingi va keyingi elementlarga havolalarni saqlaydi. Bu, kimlarni oldiga kim kim kelayotgani va kim ortida kim borligini eslab qoladigan navbat ga o'xshaydi.

Xotirada bunday ro'yxat qanday ko'rinishda:

Yondan (kulrang fon) first va last o'zgaruvchilar, ular Node turidagi obyektlarga havolalarni saqlaydi.

O'rtada siz obyektlar zanjirini ko'rasiz (aniq obyektlar, o'zgaruvchilar emas) Node turidagi. Har biri uchta maydondan iborat:

• prev — oldingi Node tipidagi obyektga havola saqlaydi (sariq fon).
• value — qiymatni saqlaydi — ro'yxat elementi (yashil fon).
• next — keyingi Node tipidagi obyektga havola saqlaydi (ko'k fon)

Ikkinchi obyekt (manzil == F24) birinchi uchun keyingi (next) va uchinchi uchun oldingi (prev). Uchinchining sariq maydoni F24 havolani, birinchi obyektning ko'k maydoni F24 havolani saqlaydi.

Birinchi va uchinchi obyektlarning o'qilari bir xil ikkinchi ob'ektga ishora qiladi. Shuning uchun o'qlarni shunday chizish to'g'riroq bo'ladi.

4. Bog'langan ro'yxatga element qo'shish

Bunday navbatga odam qo'shish uchun, faqat ikki qo'shni odamning roziligi kerak. Ulardan birinchisi yangi kelgan odamni "bu odamdan keyin" sifatida eslab qoladi, ikkinchisi esa yangi kelgan odamni "bu odamdan oldin" sifatida eslab qoladi.

Faqat qo'shni ob'ektlarning havolalarini o'zgartirish kerak:

Biz ro'yxatimizga yangi element qo'shdik va ikkinchi va uchinchi ob'ektlarning havolalarini o'zgartirdik. Endi ikkinchi dan keyin yangi kelgan odam va uchinchi uchun oldingi odam. Yangi ob'ektning havolalarini to'g'ri ko'rsatish kerak: oldingi ob'ekt — ikkinchi, keyingi ob'ekt — uchinchi.

O'chirish yanada sodda. Agar biz, masalan 100-chi ob'ektni ro'yxatdan o'chirishni istasak, 99-chi ob'ektning next ni o'zgartirish kerak, 99-chi va 101-chi ob'ektning prev ni o'zgartirish, 99-chi ob'ektga ishora qilishi kerak. Va hammasi.

Lekin 100-chi ob'ektni olish juda qiyin.

5. Ro'yxatning elementini olish

Ro'yxatning 100-chi elementini olish uchun:

1-chi ob'ektni olish: bu ob'ektiga LinkedList havolalangan first havola qiladi. 1-chi ob'ektda 2-chi ob'ektga havola (maydon next) mavjud. Uning yordami bilan ikkinchi ob'ektni olish mumkin. 2-chi ob'ektda uchinchiga havolani mavjud, va h.k.

Agar biz 100-chi ob'ektga havola olishni istasak, biz 1-dan 100-chi ob'ektgacha barcha ob'ektlarni ketma-ket ko'rib chiqishimiz kerak. Va agar biz ro'yxatning millioninchi elementini olishni istasak, million ob'ektlarni ketma-ket ko'rib chiqishimiz kerak bo'ladi.

Agar bu ob'ektlar ro'yxatga har xil vaqtlarda qo'shilgan bo'lsa, ular xotiraning turli joylarida joylashgan va ular bir vaqtda protsessor keshiga kiritilishi mumkin emas. Bu, ketma-ket bog'langani ro'yxat elementi katta sekinligini anglatadi.

Ishlar shunday.

Xo'sh, nima uchun biz bu yerda bu sekin LinkedList ni qanday tuzilganini o'rganmoqdamiz?

Barcha gap shundaki, suhbatda sizga majburiy savol berishadi, LinkedList ArrayList dan qanday farq qiladi. Majburiy.