DSA bog‘langan ro‘yxatlar
Bog‘langan ro‘yxat (Linked List), nomidan ko‘rinib turganidek, tugunlari o‘zaro bog‘langan ro‘yxatdir. Har bir tugun ma’lumot va ko‘rsatkichni o‘z ichiga oladi. Ular shunday bog‘langanki, har bir tugun keyingi tugun xotiraning qayerida joylashganini ko‘rsatadi.
Bog‘langan ro‘yxatlar
Bog‘langan ro‘yxat biror turdagi ma’lumotga hamda keyingi tugunga ko‘rsatkich yoki havolaga ega tugunlardan iborat.
Bog‘langan ro‘yxatlardan foydalanishning katta afzalligi shundaki, tugunlar xotiraning qayerida bo‘sh joy bo‘lsa, o‘sha yerda saqlanadi, ya’ni tugunlar massiv elementlari kabi ketma-ket, bir-biridan keyin saqlanishi shart emas. Bog‘langan ro‘yxatlarning yana bir qulay jihati — tugunlar qo‘shilganda yoki o‘chirilganda ro‘yxatdagi qolgan tugunlarni siljitish shart emas.
Bog‘langan ro‘yxatlar va massivlar
Bog‘langan ro‘yxatlarni tushunishning eng oson yo‘li, ehtimol, ularni massivlar bilan solishtirishdir.
Bog‘langan ro‘yxatlar tugunlardan iborat bo‘lib, biz o‘zimiz yaratadigan chiziqli ma’lumotlar tuzilmasidir; massivlar esa, aksincha, dasturlash tilida mavjud bo‘lgan va biz foydalanishimiz mumkin bo‘lgan ma’lumotlar tuzilmasidir.
Bog‘langan ro‘yxatdagi tugunlar boshqa tugunlarga havolalarni saqlaydi, massiv elementlari esa boshqa elementlarga havolalarni saqlashi shart emas.
Eslatma: Bog‘langan ro‘yxatlar va massivlar xotirada qanday saqlanishi keyingi sahifada batafsilroq tushuntiriladi.
Bog‘langan ro‘yxatlar nima ekanini yaxshiroq tushunish uchun quyidagi jadvalda bog‘langan ro‘yxatlar massivlar bilan solishtirilgan.
| Massivlar | Bog‘langan ro‘yxatlar | |
|---|---|---|
| Dasturlash tilida tayyor mavjud ma’lumotlar tuzilmasi | Ha | Yo‘q |
| Xotirada o‘lchami o‘zgarmas | Ha | Yo‘q |
| Elementlar yoki tugunlar xotirada bevosita birin-ketin saqlanadi (uzluksiz) | Ha | Yo‘q |
| Memory usage is low (each node only contains data, no links to other nodes) |
Ha | Yo‘q |
| Elementlar yoki tugunlarga to‘g‘ridan-to‘g‘ri murojaat qilish mumkin (random access) | Ha | Yo‘q |
| Elementlar yoki tugunlarni o‘zgarmas vaqtda qo‘shish yoki o‘chirish mumkin, xotirada siljitish amallari kerak emas. | Yo‘q | Ha |
Bu farqlarni batafsilroq tushuntirish uchun keyingi sahifada bog‘langan ro‘yxatlar va massivlar xotirada qanday saqlanishiga e’tibor qaratiladi.
DSA mashqlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!