Linked List Operations

Bog'langan ro'yxat ustida turli xil amallarni bajarish mumkin. Masalan, kiritish (insertion) amali ro'yxatga yangi element qo'shsa, o'chirish (deletion) amali keraksiz tugunni ro'yxatdan olib tashlaydi.

Ushbu darsda biz quyidagi asosiy amallarni ko'rib chiqamiz:

• Aylanib chiqish (Traversal) — ro'yxatdagi har bir elementga ketma-ket murojaat qilish
• Qo'shish (Insertion) — ro'yxatga yangi element kiritish
• O'chirish (Deletion) — mavjud elementlarni o'chirish
• Qidirish (Search) — ro'yxatdan kerakli tugunni topish
• Saralash (Sort) — ro'yxat tugunlarini tartiblash

Ushbu amallarni batafsil o'rganishdan oldin Linked List darsini bilib olishingiz tavsiya etiladi.

Quyidagi amallarda shuni yodda tutish lozim:

• head har doim bog'langan ro'yxatning birinchi tuguniga ishora qiladi.
• Oxirgi tugunning next ko'rsatkichi NULL (Go tilida nil) bo'ladi, ya'ni keyingi ko'rsatkich NULL bo'lsa, ro'yxat oxiriga yetganimizni anglatadi.

Quyidagi barcha misollarda 1 ---> 2 ---> 3 ko'rinishidagi bog'langan ro'yxatdan foydalanamiz:

type Node struct {
    data int
    next *Node
}

Bog'langan ro'yxatni aylanib chiqish

Bog'langan ro'yxat elementlarini ekranga chiqarish juda oddiy. temp nomli vaqtinchalik ko'rsatkichni har safar keyingi tugunga surib boramiz va uning qiymatini chop etamiz.

Qachonki temp ko'rsatkichi nil ga teng bo'lsa, ro'yxat oxiriga yetganimiz ma'lum bo'ladi va sikldan chiqamiz:

temp := head
fmt.Println("List elements are -")
for temp != nil {
    fmt.Printf("%d ---> ", temp.data)
    temp = temp.next
}

Ushbu dasturning natijasi quyidagicha bo'ladi:

List elements are - 1 --->2 --->3 --->

Bog'langan ro'yxatga element qo'shish

Siz elementlarni bog'langan ro'yxatning boshiga, o'rtasiga yoki oxiriga qo'shishingiz mumkin.

1. Insert at Beginning

Boshiga qo'shish:

1. Yangi tugun uchun xotira ajratish va ma'lumotni kiritish
2. Yangi tugunning next ko'rsatkichini head ga yo'naltirish
3. head ko'rsatkichini yangi yaratilgan tugunga o'zgartirish

newNode := &Node{data: 4}
newNode.next = head
head = newNode

2. Insert at End

Oxiriga qo'shish:

1. Yangi tugun uchun xotira ajratish va ma'lumotni kiritish
2. Ro'yxatning oxirgi tugunigacha aylanib borish
3. Oxirgi tugunning next ko'rsatkichini yangi tugunga yo'naltirish

newNode := &Node{data: 4}
if head == nil {
    head = newNode
} else {
    temp := head
    for temp.next != nil {
        temp = temp.next
    }
    temp.next = newNode
}

3. Insert at Middle

O'rtasiga qo'shish:

1. Yangi tugun yaratish va ma'lumotni saqlash
2. Yangi tugun joylashishi kerak bo'lgan pozitsiyadan bitta oldingi tugungacha borish
3. Yangi tugunni oraga kiritish uchun next ko'rsatkichlarini bog'lash

newNode := &Node{data: 4}
temp := head
for i := 2; i < position; i++ {
    if temp.next != nil {
        temp = temp.next
    }
}
newNode.next = temp.next
temp.next = newNode

Bog'langan ro'yxatdan element o'chirish

Elementlarni ro'yxatning boshidan, oxiridan yoki ma'lum bir pozitsiyasidan o'chirish mumkin.

1. Delete from Beginning

Boshidan o'chirish:

head ko'rsatkichini ikkinchi tugunga yo'naltirish kifoya:

if head != nil {
    head = head.next
}

2. Delete from End

Oxiridan o'chirish:

1. Ro'yxatning oxiridan bitta oldingi tugunigacha borish
2. Uning next ko'rsatkichini nil qilib o'rnatish

temp := head
for temp.next.next != nil {
    temp = temp.next
}
temp.next = nil

3. Delete from Middle

O'rtasidan o'chirish:

1. O'chirilishi kerak bo'lgan tugundan bitta oldingi tugungacha borish
2. Ushbu tugunning next ko'rsatkichini o'chirilayotgan tugundan keyingi tugunga bog'lab, uni zanjirdan chetlatish

for i := 2; i < position; i++ {
    if temp.next != nil {
        temp = temp.next
    }
}
temp.next = temp.next.next

Bog'langan ro'yxatdan element qidirish

Ro'yxatdan kerakli elementni (item) sikl orqali quyidagi bosqichlarda qidirish mumkin:

1. head ko'rsatkichini joriy tugun (current) qilib belgilash.
2. Joriy tugun nil bo'lmaguncha siklni davom ettirish.
3. Har bir iteratsiyada tugun qiymatini qidirilayotgan qiymat bilan solishtirish. Agar mos kelsa true, ro'yxat tugagach mos kelmasa false qaytariladi.

// Tugunni qidirish
func searchNode(head *Node, key int) bool {
    current := head
    for current != nil {
        if current.data == key {
            return true
        }
        current = current.next
    }
    return false
}

Bog'langan ro'yxatni saralash

Bog'langan ro'yxat elementlarini o'sish tartibida saralash uchun oddiy Bubble Sort algoritmidan foydalanish mumkin:

1. head ni joriy tugun (current) qilib belgilash va qo'shimcha index ko'rsatkichini yaratish.
2. Agar head bo'sh bo'lsa, qaytish.
3. Aks holda, oxirgi tugungacha siklni yurgizish.
4. Har bir iteratsiyada current dan keyingi tugunni index ga saqlash.
5. Agar current ning ma'lumoti index ning ma'lumotidan katta bo'lsa, ularning qiymatlarini almashtirish (swap).

// Bog'langan ro'yxatni saralash
func sortLinkedList(head *Node) {
    if head == nil {
        return
    }
    current := head
    for current != nil {
        index := current.next
        for index != nil {
            if current.data > index.data {
                current.data, index.data = index.data, current.data
            }
            index = index.next
        }
        current = current.next
    }
}

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

// Linked list operations in Go
package main

import "fmt"

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

type LinkedList struct {
	head *Node
}

// Boshiga element qo'shish
func (ll *LinkedList) insertAtBeginning(newData int) {
	newNode := &Node{data: newData}
	newNode.next = ll.head
	ll.head = newNode
}

// Berilgan tugundan keyin element qo'shish
func (ll *LinkedList) insertAfter(prevNode *Node, newData int) {
	if prevNode == nil {
		fmt.Println("The given previous node cannot be null")
		return
	}
	newNode := &Node{data: newData}
	newNode.next = prevNode.next
	prevNode.next = newNode
}

// Oxiriga element qo'shish
func (ll *LinkedList) insertAtEnd(newData int) {
	newNode := &Node{data: newData}
	if ll.head == nil {
		ll.head = newNode
		return
	}
	last := ll.head
	for last.next != nil {
		last = last.next
	}
	last.next = newNode
}

// Berilgan pozitsiyadagi tugunni o'chirish
func (ll *LinkedList) deleteNode(position int) {
	if ll.head == nil {
		return
	}
	temp := ll.head
	if position == 0 {
		ll.head = temp.next
		return
	}

	for i := 0; temp != nil && i < position-1; i++ {
		temp = temp.next
	}

	if temp == nil || temp.next == nil {
		return
	}

	next := temp.next.next
	temp.next = next
}

// Elementni qidirish
func (ll *LinkedList) search(key int) bool {
	current := ll.head
	for current != nil {
		if current.data == key {
			return true
		}
		current = current.next
	}
	return false
}

// Bog'langan ro'yxatni saralash (Bubble sort)
func (ll *LinkedList) sortLinkedList() {
	current := ll.head
	var index *Node

	if current == nil {
		return
	}

	for current != nil {
		index = current.next
		for index != nil {
			if current.data > index.data {
				current.data, index.data = index.data, current.data
			}
			index = index.next
		}
		current = current.next
	}
}

// Bog'langan ro'yxatni chop etish
func (ll *LinkedList) printList() {
	temp := ll.head
	for temp != nil {
		fmt.Printf("%d ", temp.data)
		temp = temp.next
	}
	fmt.Println()
}

func main() {
	llist := &LinkedList{}

	llist.insertAtEnd(1)
	llist.insertAtBeginning(2)
	llist.insertAtBeginning(3)
	llist.insertAtEnd(4)
	llist.insertAfter(llist.head.next, 5)

	fmt.Println("Linked list:")
	llist.printList()

	fmt.Println("After deleting an element:")
	llist.deleteNode(3)
	llist.printList()

	itemToFind := 3
	if llist.search(itemToFind) {
		fmt.Printf("%d is found\n", itemToFind)
	} else {
		fmt.Printf("%d is not found\n", itemToFind)
	}

	llist.sortLinkedList()
	fmt.Println("Sorted List:")
	llist.printList()
}