Siyahılar: təkbağlı və ikiqat bağlı siyahılar

5.1 Siyahının təyini və onun növləri

Siyahı — bu, elementlərdən (düyünlərdən) ibarət olan dinamik məlumat strukturu deməkdir. Hər bir düyün məlumatları və digər düyünlərə keçidləri saxlayır. Array-lardan fərqli olaraq, siyahılar proqramın icrası zamanı öz ölçüsünü dəyişə bilirlər.

Vacibdir! Burada Python-dakı list sinfi nəzərdə tutulmur, burada nəzərdə tutulur nəzəriyyədəki məlumat strukturu.

Siyahı növləri:

• Tək əlaqəli siyahı (Singly Linked List): Hər bir düyün məlumatları və növbəti düyünə keçidi saxlayır.
• İki əlaqəli siyahı (Doubly Linked List): Hər bir düyün məlumatları, növbəti düyünə keçidi və əvvəlki düyünə keçidi saxlayır.

5.2 Təkbağlantılı siyahının iş prinsipi

Təkbağlantılı siyahının strukturu:

• Node (Düyün): İki hissədən ibarətdir: məlumatlar və növbəti düyünün ünvanı.
• Head (Başlıq): Siyahının ilk düyününü göstərən göstərici.

İş prinsipi:

• Düyün əlavə etmək: Yeni bir düyün yaradılır və son düyünün ünvanı yeni düyünə yenilənir.
• Düyün silmək: Silinən düyünün əvvəlki düyünündən sonra gələn düyüne keçid ünvanı yenilənir.

Reallaşdırma nümunəsi:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# İstifadə nümunəsi:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Çıxış: 1 -> 2 -> 3 -> None

5.3 İkiqat bağlı siyahının işləmə prinsipi

İkiqat bağlı siyahının strukturu:

• Node (Düyün): Üç hissədən ibarətdir: məlumat, növbəti düyünə keçid və əvvəlki düyünə keçid.
• Head (Başlıq): Siyahının ilk düyününü işarə edən göstərici.
• Tail (Son): Siyahının son düyününü işarə edən göstərici (mütləq deyil, amma tez-tez istifadə olunur).

İşləmə prinsipi:

• Düyünün əlavə edilməsi: Yeni bir düyün yaradaraq və son düyünün keçidləri ilə yeni düyünün keçidlərini yeniləməklə baş verir.
• Düyünün silinməsi: Silinəcək düyünün əvvəlki və növbəti düyünlərinin keçidlərini yeniləməyi tələb edir.

Reallaşdırma nümunəsi:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# İstifadə nümunəsi:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Çıxış: 1 <-> 2 <-> 3 <-> None

5.4 Əsas əməliyyatlar

Əsas əməliyyatlar: əlavə etmə, silmə, axtarış

Əlavə etmə:

• Birbağlı siyahı: Siyahının sonuna yeni node əlavə etmək bütün nodelardan keçməyi tələb edir və sonuncu node-un linkini yeniləmək lazımdır.
• Cütbağlı siyahı: Siyahının sonuna yeni node əlavə etmək birbağlı siyahıya bənzəyir, amma əlavə olaraq prev linkini yeni node-dan əvvəlki node-a yönəltmək lazımdır.

Silmə:

• Birbağlı siyahı: Node-un silinməsi siyahıda silinəcək node-a qədər keçməyi tələb edir və əvvəlki node-dan silinən node-un növbəti node-una yönəldilən linki yeniləmək lazımdır.
• Cütbağlı siyahı: Node-un silinməsi üçün qonşu node-ların next və prev linklərini yeniləmək tələb olunur.

Axtarış: Siyahıda başdan sona doğru keçərək hər node-dakı məlumatları axtarılan dəyər ilə müqayisə etmək. Zaman mürəkkəbliyi — O(n).

5.5 Siyahıları istifadə nümunəsi

Gəl, nümunə olaraq, təkbağlı siyahı əsasında bir stack (yığın) yaradacağıq.

Stack-i təkbağlı siyahıdan istifadə edərək asanlıqla reallaşdırmaq mümkündür. Bunun üçün push (əlavə etmə) və pop (çıxarma) metodlarından istifadə edirik. Stack-in 2 metodu olmalıdır:

• push — siyahıya yeni element əlavə edir
• pop — siyahının sonundakı elementi çıxarır

Reallaşdırma nümunəsi:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# İstifadə nümunəsi:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Çıxış: 3 -> 2 -> 1 -> None
print(stack.pop())  # Çıxış: 3
stack.display()  # Çıxış: 2 -> 1 -> None