Linked List

Bog'langan ro'yxat (Linked list) — bu o'zaro bog'langan tugunlar (nodes) ketma-ketligidan iborat chiziqli ma'lumotlar tuzilmasidir. Unda har bir tugun o'z ma'lumotini (data) va keyingi tugunning xotiradagi manzilini (address / pointer) saqlaydi. Masalan:

Ro'yxatni o'qishni qaerdandir boshlash kerak, shuning uchun biz birinchi tugunning manziliga HEAD degan maxsus nom beramiz. Shuningdek, bog'langan ro'yxatning oxirgi tugunini uning keyingi qismi (next) NULL (yoki Go tilida nil) ga ishora qilishidan aniqlash mumkin.

Bog'langan ro'yxatlarning bir nechta turlari mavjud: bir tomonlama bog'langan (singly), ikki tomonlama bog'langan (doubly) va aylanma (circular) bog'langan ro'yxatlar. Ushbu maqolada biz bir tomonlama bog'langan ro'yxatga e'tibor qaratamiz. Boshqa turlari haqida ma'lumot olish uchun Types of Linked List darsiga qarang.

[!NOTE] Siz "Xazina izlash" (Treasure Hunt) o'yinini o'ynagan bo'lsangiz kerak: unda har bir topilgan ishora keyingi ishoraning qayerdaligi haqida ma'lumot beradi. Bog'langan ro'yxat ham xuddi shu tarzda ishlaydi.

Bog'langan ro'yxatning ifodalanishi

Keling, bog'langan ro'yxatning har bir tuguni qanday tuzilganini ko'rib chiqaylik. Har bir tugun quyidagilardan iborat:

• Ma'lumot qiymati (data item)
• Boshqa tugunning manzili (address of another node)

Biz ma'lumot va keyingi tugun ko'rsatkichini bitta tuzilma (struct) ichiga o'raymiz:

type Node struct {
    data int
    next *Node
}

Tugun tuzilishini tushunish bog'langan ro'yxatni to'liq o'zlashtirishning kalitidir.

Har bir tugun ma'lumot elementiga va boshqa tugunga ko'rsatkichga ega. Keling, bu qanday ishlashini tushunish uchun uchta elementdan iborat oddiy bog'langan ro'yxat tuzamiz:

// Tugunlarni e'lon qilish va xotira ajratish
var head *Node
one := &Node{data: 1}
two := &Node{data: 2}
three := &Node{data: 3}

// Tugunlarni bir-biriga bog'lash
one.next = two
two.next = three
three.next = nil

// Birinchi tugunning manzilini head ko'rsatkichiga saqlash
head = one

Bir necha oddiy qadamlar yordamida biz uchta tugundan iborat bog'langan ro'yxatni yaratdik.

Bog'langan ro'yxatning asosiy kuchi zanjirni osonlikcha uzish va qayta ulash imkoniyatidadir. Masalan, agar siz 1 va 2 orasiga yangi 4 elementini qo'shmoqchi bo'lsangiz, quyidagi amallar bajariladi:

1. Yangi tugun yaratish va unga xotira ajratish.
2. Uning ma'lumot qiymatini 4 qilib belgilash.
3. Uning next ko'rsatkichini 2 qiymatli tugunga yo'naltirish.
4. 1 qiymatli tugunning next ko'rsatkichini yangi yaratilgan tugunga yo'naltirish.

Massivda xuddi shu ishni bajarish uchun yangi elementdan keyin keluvchi barcha elementlarni xotirada bittadan o'ngga surib chiqish talab qilingan bo'lardi.

Bog'langan ro'yxatning amaliy ahamiyati

Ro'yxatlar eng ommabop va samarali ma'lumotlar tuzilmalaridan biri bo'lib, C, C++, Python, Java, Go va C# kabi barcha zamonaviy dasturlash tillarida keng qo'llaniladi.

Bundan tashqari, bog'langan ro'yxatlar ko'rsatkichlar (pointers) va havolalar (references) qanday ishlashini chuqur tushunish uchun ajoyib amaliy vositadir. Bog'langan ro'yxatlarni boshqarishni yaxshi o'zlashtirish orqali siz daraxtlar (trees) va graflar (graphs) kabi murakkabroq ma'lumotlar tuzilmalarini o'rganishga puxta tayyorgarlik ko'rasiz.

Bog'langan ro'yxatning Go, Python, Java, C va C++ tillaridagi dasturiy kodi

// Linked list implementation in Go
package main

import "fmt"

// Tugun (Node) yaratish
type Node struct {
	value int
	next  *Node
}

// Bog'langan ro'yxat qiymatlarini chop etish
func printLinkedList(p *Node) {
	for p != nil {
		fmt.Printf("%d ", p.value)
		p = p.next
	}
	fmt.Println()
}

func main() {
	// Tugunlarni yaratish
	one := &Node{value: 1}
	two := &Node{value: 2}
	three := &Node{value: 3}

	// Tugunlarni o'zaro bog'lash
	one.next = two
	two.next = three
	three.next = nil

	// Ro'yxat boshini head ga saqlash va chop etish
	head := one
	printLinkedList(head)
}

Bog'langan ro'yxat murakkabligi

Vaqt murakkabligi

Xotira murakkabligi

Bog'langan ro'yxatning xotira murakkabligi: O(n).

Bog'langan ro'yxatning qo'llanilishi

Bog'langan ro'yxatlar quyidagi sohalarda keng qo'llaniladi:

• Dinamik xotira taqsimoti (dynamic memory allocation)
• Stack va Queue ma'lumotlar tuzilmalarini amalga oshirishda
• Dasturlardagi bekor qilish (undo) funksiyasini yaratishda
• Hash table (Xesh-jadvallar) va Graph (Graflar)ni ifodalashda