Array vs Linked list

Xotira qanday ishlaydi?

Kompyuter xotirasini kichik javonlardan tashkil topgan ulkan javonga o'xshatish mumkin.

Har bir javonda 1 ta element, ya'ni ma'lumot saqlanadi.

Xotiradagi har bir katak o'z manziliga ega.

Har safar ma'lumotlarni xotirada saqlamoqchi bo'lganingizda, siz kompyuterdan uning xotirasidan joy so'raysiz va kompyuter sizga ma'lumotingiz uchun bo'sh xotira joyining manzilini beradi va sizning ma'lumotlaringiz shu manzildagi katakchaga borib joylashadi. Agar siz bir nechta elementlarni saqlamoqchi bo'lsangiz, buni amalga oshirishning ikkita oddatiy usuli mavjud: array va linked list .

Ushbu postda array, linked list va ularning afzalliklari va kamchiliklari haqida gaplashamiz.

Array

Tasavvur qiling, siz 5 do'stingiz bilan futbol ko'rish uchun futbol maydoniga bordingiz va siz 5 kishi sig'adigan joy topib, shu erga borib o'tirdingiz. 20 daqiqadan so'ng yana 2 ta do'stingiz sizlar bilan futbol ko'rgisi kelib qoldi, lekin yoningizda bo'sh joy yo'q. Xo'sh, nima qilasiz? Agar siz oqibatli, ayirlmas do'stlar bo'lsangiz, turib stadiondan 7 kishilik joy topib, o'sha joyga borasiz. Ya'ni, arrayni shunaqa oqibatli bir-biridan ajralmas jigarlar desak bo'ladi).

Array xotirada yonma-yon joylashganligi sababli, qidirish (read) uchun O(1) vaqt kerak bo'ladi . Bu arrayning eng katta afzalliklaridan biridir. Lekin qo'shish(insert) uchun O(n) vaqt kerak bo'ladi , chunki har safar yangi element qo'shilayotganda butun array elementlari xotiradagi boshqa joyga ko'chishga majbur bo'ladi.

Linked List

Linked listni biroz oqibtasizroq do'stlar desak bo'ladi, chunki ular maydonda(xotirada) o'zlari uchun bo'sh joy topishi bilanoq o'sha joyga borib joylashadilar.

Linked List tugunladan(nodes) tashkil topgan ro'yxatdir . Har bir node o'z qiymatini va keyingi nodening manzilini saqlaydi .

Keyingi nodening manzilini saqlaydi nima degani?

Misol tariqasida yana o'sha futbol stadionini olaylik. Yuqoridagi rasmni stadion o'rindig'lari deb tasavvur qiling. Aytaylik, Aziz 1-o‘rinda, Alisher 2-o‘rinda, G‘anisher 3-o‘rindiqda o‘tirishdi. Aziz o'zidan keyin kelgan Alisher qaysi o‘rindiqda o‘tirganini biladi. Alisher esa o'zidan keyin kelgan G‘anisherning o‘tirgan manzilini aniq biladi. Bu Linked listdan ma'lumot o'qish(read) uchun O (n) vaqt kerakligini anglatadi . Insert uchun esa O(1), chunki linked listda har bir elementni ko'chirish shart emas bosh joy topadi va osha joyga borib saqlanadi, ya'ni 1ta operatsiya yetarli.

Shunday qilib, ikkalasining ham o'ziga xos afzalliklari va kamchiliklari bor. Array ni ham, linked list ni ham o‘zining ishlatiladigan joyi bor. Shuning uchun ikkisi orasidagi farqni bilish zarar qilmaydi.

Inglizcha versiyasi:

Maqolaning inglizcha versiyasi bu yerda .

Ali Ismailov, 02.03.24

Italiya, Messina