Array va linked list farqi: xotira va Big-O

Assalomu Alaykum hammaga bugungi mavzu array va linkedlist farqlari va ularning kompyuter xotirasini qanday ishlatishi va qaysi hollarda samaraliroqligini ko`rib chiqamiz.

Array

Ba’zan siz bir guruh ma’lumotlarni xotirada saqlashingiz kerek. Bu xohlagan ma’lumot bo'lishi mumkin o'qigan kitoblaringiz , do'stlaringizning telefon raqamlari va hokazo .Xo'sh biz uni arrayda (massiv) saqlaganimiz yaxshiroqmi yoki linkedlist ? Biz ikki holatniyam ko'rib chiqamiz . Arraydan boshlaymiz ,chunki uni xotiradan o'qib olish osonroq . Arrayda barcha malumotlar xotirada ketma-ket saqlanadi .

Keyin siz yana bir yangi do'stingizni raqamini qo'shishni xohladingiz lekin undan keyingi bo'sh joy yoq .Siz xuddi bu holatda do'stlaringiz bilan kino ko'rishga bordingiz va joylar oldingiz ammo keyin yana do'stingiz kelib qoldi va bo'sh joy yoq sizlar yangi u do'stingiz ham sig'adigan joy topishingiz zarur .Kompyuterda xuddi shunday jarayon bo'lib xotiradan yangi joy qidiradi va barcha ma’lumotlarni yangi joyga olib o'tadi.Agarda yana shunday hol takrorlansa bu holat qayta-qayta takrorlanaveradi bu yangi malumot qo'shishni sekinlashishiga olib keladi.Buni qanday oldini olish mumkin yoki bartaraf etish mumkin .Sizga keragidan ko'proq xotiradan joy olasiz masalan sizda 3 ta element bor ammo siz 10 ta element uchun joy olasiz va yangi kelganlarini oxiriga qo'shib boraverasiz xotirada joyni o'zgartirmasdan .Bu juda yaxshi yechim ammo buning yomon taraflarini bilish zarur (downsides):

• Balki siz so'ragan qo'shimcha xotira kerak bo'lmas va bu xotira shunchaki sarflanadi .Siz bu xotiradan foydalanmaysiz ammo boshqa kishi ham foydalanolmaydi .

• Sizga keyinchalik siz so'ragandan ko'proq xotira kerak bo'lar va bu yana avvalgi holatni takrorlashga olib keladi.

Arrayda biror bir elementni oqish O(1)ga teng bo'ladi chunki elementlar ketma-ket saqlanadi va array sifatida o`zgaruvchida birinchi element xotira addresi bo'ladi. sizga N chi element kerak bo'lsa shu birnchi katakdan N-1 katakdagi qiymat bo'ladi va buni xotirada o`qish ancha osonlashadi.

Yangi elementlar qo`shish muammosini linkedlist yecha oladi .

Linked list

Linked listda siz elementlaringizni xotiraning xohlagan bo'sh joyida saqlashingiz mumkin. Bu holatda elementlar o'zidan keyingi element addressini o'zida saqlaydi . Bir guruh random computer xotiralari birgalikda ulanadi.

Siz 1-elementga borasiz va keyingi element addressini olasiz va unga borasiz va shunday davom etadi . Yangi element qo'shish qisman osonlashadi siz uni xotiraning xohlagan joyiga saqlaysiz va undan oldingi elementga addressini berib borasiz (ammo shu oxirgi elementgacha har bir elementni o'qib borishingiz kerak bo'ladi bu esa O(n) ). Linkedlistda siz hech qachon elementlarni joyini o'zgartirmaysiz .Tepadagi holat bo'lsa do'stlaringiz bilan alohida bo'lib kinoni tomosha qilaverasiz (ammo alohida joylarda) .

Xo'sh agarda linkedlist yangi element qo'shishda samaraliroq bo'lsa ,nega biz odatda array ishlatamiz ? Endi ularni farqi va qachon ishlatish kerakligini ko`ramiz.

Ularning bir biridan farqi

Tassavur qiling siz linkedlistni oxirgi elementini olmoqchisiz ammo uning addressini bilmaysiz shu sababdan siz 1-elementdan boshlab uni qidirib borasiz.Agar siz hamma elementni birdaniga o'qimoqchi bo'lsangiz linkedlist juda qulay, chunki siz element o'qiysiz va address bilan keyingi elementga yo'l olasiz .Ammo siz elementlar orasida aylanib yurmoqchi bo'lsangiz linkedlist bu uchun juda noqulay.

Arrayda esa bu juda boshqacha u elementlarni ketma ket joylaydi va shu sababli siz xohlagan elementni juda tez olib bera oladi va bu holat uchun juda samarali.

Xo'sh biz elementni eng oxiriga qo'shishni ko'rib o'tdik agarda elementni malumotlar o'rtasiga qo'shmoqchi bo'lsakchi ?

List bilan bu juda oson undan oldingi element(agarda bilmasangiz yana boshidan boshlab topib kelishingiz kerak) addressini o'zgartirasiz tamom muammo hal .Ammo array bilan bu juda og'ir chunki siz undan keyingi elementlarni hammasini 1 katakdan surishingiz kerak va agar xotira yetmay qolsa bularning hammasini yangi xotiraga olib o'tish zarur. Bu holatda linked list g'olib keldi. Ammo real hayotda odatda array yutib chiqadi chunki ikkalasida ham n ta amal bajarish kerak ammo arrayda elementlar ketma ket joylashgan va bular Operatsion sistema orqali cachega tushishi va har xil joyda yotgan elementlarni o'qib kelishdan tezroq bo'ladi .

O'chirib yuborish

Agarda biz elementni o'chirishni xohlasakchi ? Yana bu listlar bilan osongina bitadi undan oldingi elementda address o'zgartiriladi xolos , har doim aytganimizdek agarda shu berilgan elementdan oldingi element addresi bo'lsa va bu O(n) bo'ladi . Arrayda esa bu holatda undan keyingi elementlar hammasi 1 katak chapga surilishi kerak. Ammo bundan yangi element qo'shishdagidek xotira to'lib qolish holati kuzatilmaydi .

Pastdagi rasmda siz odatiy operatsiyalar uchun qancha vaqt ketishini ko`rishingiz mumkin :

Gibrid uslub

Qaysi biri ko'proq ishlatiladi ? Bu umumiy holatga va ishlatilish joyiga qarab tanlanadi.Lekin odatda Array ishlatiladi chunki u elementlarga random access(xohlagan elementni tez olish) imkonini beradi .Linkedlist esa sequential access(ketma-ket) ga imkon beradi ya'ni elementlarni ketma -ket o'qiladigan holat . Ammo lekin biz hybrid structure ishlatishimiz mumkin . Masalan siz do'stingizni telefon raqamini ismi orqali topmoqchisiz va bosh harflari bilan 26 ta elementlik array yaratamiz va unga linkedlistning addressini berib qo'yamiz bu qaysidir manoda performanceni oshiradi. Siz bu holatni quyidagi rasmda ko'rishingiz mumkin. Va bu uslub hashmap deyiladi .

Xulosa

Xulosa qilib aytadigan bo'lsak agarda siz biror harakat qilmoqchi bo'lgan elementni oldindan bilsangiz unda Linkedlist tezroq ishaydi ammo bilmasangiz uni topishga har doim vaqt ketadi. Shuning uchun tarqoq xotira va ketma-ket xotira tanlash kerak bo'lganda qaysi holatlarga duch kelishni hisobga olish kerak bo'ladi.

Kamchiliklar uchun uzr. Ajratgan vaqtingiz uchun rahmat!!