Types of Linked List

Bog'langan ro'yxat turlarini o'rganishdan oldin, Bog'langan ro'yxat (Linked List) ma'lumotlar tuzilmasi haqidagi asosiy tushunchalarni bilishingiz lozim.

Bog'langan ro'yxatning uchta asosiy turi mavjud:

1. Bir tomonlama bog'langan ro'yxat (Singly Linked List)
2. Ikki tomonlama bog'langan ro'yxat (Doubly Linked List)
3. Aylanma bog'langan ro'yxat (Circular Linked List)

Bir tomonlama bog'langan ro'yxat

Bu eng keng tarqalgan bog'langan ro'yxat turidir. Unda har bir tugun o'z ma'lumotini va faqat keyingi tugunning manzilini (next pointer) saqlaydi.

Tugun Go tilida quyidagicha ifodalanadi:

type Node struct {
    data int
    next *Node
}

Uchta a'zodan iborat bir tomonlama bog'langan ro'yxatni quyidagicha yaratish mumkin:

// 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 tugun manzilini head ga saqlash
head = one

Ikki tomonlama bog'langan ro'yxat

Ikki tomonlama bog'langan ro'yxatda har bir tugunga oldingi tugun ko'rsatkichi (prev pointer) ham qo'shiladi. Natijada biz ro'yxat bo'ylab ikkala yo'nalishda — ham oldinga, ham orqaga harakatlana olamiz.

Tugun Go tilida quyidagicha ifodalanadi:

type Node struct {
    data int
    next *Node
    prev *Node
}

Uchta a'zodan iborat ikki tomonlama bog'langan ro'yxatni quyidagicha yaratish mumkin:

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

// Tugunlarni ikki tomonlama bog'lash
one.next = two
one.prev = nil

two.next = three
two.prev = one

three.next = nil
three.prev = two

// Birinchi tugun manzilini head ga saqlash
head = one

Aylanma bog'langan ro'yxat

Aylanma bog'langan ro'yxat — bu oddiy bog'langan ro'yxatning o'zgaruvchan shakli bo'lib, unda ro'yxatning eng oxirgi elementi birinchi elementga ulanadi. Natijada u uzluksiz doiraviy siklni hosil qiladi.

Aylanma bog'langan ro'yxat bir tomonlama (singly) yoki ikki tomonlama (doubly) bo'lishi mumkin:

• Bir tomonlama aylanma ro'yxatda oxirgi elementning next ko'rsatkichi birinchi elementga ishora qiladi.
• Ikki tomonlama aylanma ro'yxatda oxirgi element birinchisiga ishora qilishidan tashqari, birinchi elementning prev ko'rsatkichi ham oxirgi elementga ishora qiladi.

Uchta a'zodan iborat bir tomonlama aylanma bog'langan ro'yxatni quyidagicha yaratish mumkin:

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

// Tugunlarni aylanma zanjirga bog'lash
one.next = two
two.next = three
three.next = one // Oxirgi tugun birinchi tugunga ishora qiladi

// Birinchi tugun manzilini head ga saqlash
head = one