Diziler, bağlı listeler, yığıtlar ve kuyruklar

Dizinin bellekte nasıl durduğunu, dinamik dizinin neden amortize O(1) sürede eleman eklediğini, bağlı listelerin nasıl çalıştığını, yığıt ve kuyrukların nerede kullanıldığını öğren.

  • Üniversite
  • 25 dk
  • 10 soru
  • Ders 47 / 59

Bu derste öğreneceklerin

  • Bir dizi elemanının adresini hesaplamak ve O(1) erişimi açıklamak
  • Dinamik diziye eklemenin amortize maliyetini kanıtlamak
  • Dizi ile bağlı listeyi işlemlerin karmaşıklığına göre karşılaştırmak
  • Bir problem için yığıt ya da kuyruk seçip uygulamak

Tarayıcıda “Geri” düğmesine bastığında en son açtığın sayfaya dönersin; bir hizmet merkezindeki elektronik kuyrukta ise ilk bileti alan ilk hizmet alır. Bu iki gündelik kural, iki temel veri yapısının, yani yığıtın (stack) ve kuyruğun (queue) özüdür. Onların altında daha da basit tuğlalar vardır: dizi ve bağlı liste. Her yapının güçlü ve zayıf yanlarını bilmek, programın hızını çoğu zaman algoritmadan bile fazla belirler.

Dizi ve dinamik dizi

DiziTanım

Eşit boyutlu elemanların bellekte art arda, boşluksuz saklandığı yapı. Bir elemanın adresi indeksinden basit bir formülle hesaplanır; bu yüzden herhangi bir elemana erişim O(1) sürer.

addr(A[i]) = base + i · s

Burada

base
dizinin başlangıç adresi (A[0]'ın adresi)
i
eleman indeksi (0'dan başlar)
s
bir elemanın boyutu, bayt

İndekslerin 0'dan başlamasının nedeni de budur: i, elemanın başlangıçtan kaç adım uzakta olduğunu gösterir.

Örnek 1: adres hesabı

Problem

4 baytlık tam sayılardan oluşan bir dizi 1000 adresinden başlıyor. A[25] hangi adrestedir? A[5]'ten A[6]'ya geçince adres ne kadar değişir?

Çözümü gösterÇözümü gizle

Çözüm

addr(A[25]) = 1000 + 25 · 4 = 1000 + 100 = 1100.
Komşu elemanlar arasındaki fark s = 4 bayt'tır.
Hesap, i ne olursa olsun bir çarpma ve bir toplamadır; erişimin O(1) olmasının nedeni budur.

Bunun bir bedeli var: dizinin ortasına eleman eklemek için sağdaki bütün elemanlar bir yer kaydırılmalıdır, yani O(n). Boyut da önceden sabittir. Dinamik dizi (Python list, Java ArrayList, C++ vector) bunu şöyle çözer: yer bitince iki kat büyük yeni bir dizi ayırır ve eski elemanları oraya kopyalar.

(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n

Burada

n
eklenen eleman sayısı
1 + 2 + … + 2ᵏ
tüm büyütmelerde kopyalanan eleman sayısı (< 2n)

Amortize maliyet: n eklemenin toplam işi 3n'den azdır; yani ara sıra yapılan “pahalı” büyütmelere rağmen bir ekleme ortalama O(1)'dir.

Python
class DynamicArray:
    def __init__(self):
        self.cap, self.n, self.copies = 1, 0, 0
        self.data = [None]

    def append(self, x):
        if self.n == self.cap:
            self.cap *= 2
            new = [None] * self.cap
            for i in range(self.n):
                new[i] = self.data[i]
                self.copies += 1
            self.data = new
        self.data[self.n] = x
        self.n += 1

arr = DynamicArray()
for k in range(1, 1025):
    arr.append(k)
    if k in (1, 2, 3, 5, 9, 17, 1024):
        print(k, arr.cap, arr.copies)
print('copies per append:', arr.copies / arr.n)
Beklenen çıktı
1 1 0
2 2 1
3 4 3
5 8 7
9 16 15
17 32 31
1024 1024 1023
copies per append: 0.9990234375
Sütunlar: eleman sayısı, kapasite, toplam kopya sayısı. Büyütme yalnızca 2., 3., 5., 9., 17.… eklemede olur; 1024 eklemeden sonra toplam yalnızca 1023 kopya yapılmıştır, yani ekleme başına birden az.

Okumaya devam etmek için ücretsiz kaydol

Dersin geri kalan bölümleri, test ve notlar Educora hesabıyla açılır. Kayıt bir dakika sürer; ilerlemen tüm cihazlarında saklanır.

Bağlı listeler

Bağlı listeTanım

Her düğümün bir değer ve sonraki düğüme bir işaretçi tuttuğu zincir. Düğümler belleğin herhangi bir yerinde olabilir; ilk düğüme baş (head) denir. Çift yönlü bağlı listede her düğüm bir öncekini de gösterir.

İşlemDinamik diziTek yönlü bağlı liste
i. elemana erişimO(1)O(n)
başa ekleme / baştan silmeO(n)O(1)
sona eklemeamortize O(1)O(1) (tail işaretçisiyle)
bilinen bir düğümden sonra eklemeO(n) (kaydırma)O(1)
değere göre aramaO(n)O(n)
belleksıkışık, önbellek dostudüğüm başına ek işaretçi, dağınık
Seçim: sık sık indeksle okuyorsan dizi; başta veya ortada çok ekleme/silme yapıyorsan bağlı liste.
Python
class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next
class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):
        self.head = Node(value, self.head)
    def reverse(self):
        prev, cur = None, self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        self.head = prev
    def items(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
lst = LinkedList()
for city in ['Shaki', 'Ganja', 'Baku']: lst.push_front(city)
print(list(lst.items()))
lst.reverse()
print(list(lst.items()))
Beklenen çıktı
['Baku', 'Ganja', 'Shaki']
['Shaki', 'Ganja', 'Baku']
push_front yeni düğümü başa O(1)'de bağlar. reverse, her düğümün işaretçisini geriye çevirerek listeyi tek geçişte, O(n) zaman ve O(1) ek bellekle ters çevirir. Bu, mülakatların klasik bir sorusudur.

Yığıt (LIFO) ve kuyruk (FIFO)

Yapıİlkeİşlemler (hepsi O(1))Kullanım alanları
YığıtLIFO — son giren ilk çıkarpush, pop, peekçağrı yığıtı, geri alma, parantez denetimi, DFS
KuyrukFIFO — ilk giren ilk çıkarenqueue, dequeue, frontyazdırma kuyruğu, ağ tamponları, görev zamanlayıcıları, BFS

Örnek 2: sonek ifadeyi yığıtla hesaplamak

Problem

Sonek (ters Leh) gösteriminde işleç, işlenenlerinden sonra gelir. 5 1 2 + 4 * + 3 - ifadesini yığıtla hesapla.

Çözümü gösterÇözümü gizle

Çözüm

Kural: sayı → push; işleç → iki sayıyı pop et, sonucu push et.
5 → [5]
1 → [5, 1]
2 → [5, 1, 2]
+ → 1 + 2 = 3 → [5, 3]
4 → [5, 3, 4]
* → 3 · 4 = 12 → [5, 12]
+ → 5 + 12 = 17 → [17]
3 → [17, 3]
- → 17 − 3 = 14 → [14]
Cevap: 14 (olağan gösterimde 5 + (1 + 2) · 4 − 3). Her simge bir kez işlenir → O(n).
Python
from collections import deque

def balanced(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for s in ['(a[i] + b) * {c}', '(]', '((x)']:
    print(s, balanced(s))

queue = deque(['Aysel', 'Murad', 'Leyla'])
queue.append('Elvin')
print(queue.popleft(), 'is served;', list(queue), 'wait')
Beklenen çıktı
(a[i] + b) * {c} True
(] False
((x) False
Aysel is served; ['Murad', 'Leyla', 'Elvin'] wait
Yığıt açılan parantezleri tutar: her kapanan parantez yığıtın tepesiyle eşleşmeli, sonunda yığıt boş kalmalıdır. deque iki uçtan da O(1)'de ekleme ve silme yapar; ideal bir kuyruktur.

Kuyruk sabit boyutlu bir dizi üzerinde de kurulabilir: dairesel tampon baş (head) ve kuyruk (tail) indekslerini tutar, dizinin sonuna gelince mod işlemiyle başa “sarar”. Böyle bir kuyruk bellek ayırmaz; ağ kartlarında, ses kartlarında ve klavye tamponunda kullanılır.

tail = (head + size) mod mnext(i) = (i + 1) mod m

Burada

head
kuyruğun ilk elemanının indeksi
size
kuyruktaki eleman sayısı
m
dizinin kapasitesi
tail
sonraki elemanın yazılacağı indeks

Örnek 3: dairesel tampon

Problem

Kapasitesi m = 6 olan dairesel bir tamponda head = 4, size = 3. Yeni eleman hangi indekse yazılır? Ardından iki eleman çıkarılıyor. head kaç olur?

Çözümü gösterÇözümü gizle

Çözüm

Elemanlar 4, 5, 0 indekslerindedir.
tail = (4 + 3) mod 6 = 7 mod 6 = 1 → yeni eleman A[1]'e yazılır, size = 4.
İki çıkarma: head = (4 + 1) mod 6 = 5, sonra (5 + 1) mod 6 = 0; size = 2.

Klasik bir mülakat sorusu: iki yığıttan kuyruk kurmak. Yeni elemanlar in yığıtına push edilir. Çıkarma gerektiğinde out yığıtı boşsa, in'deki bütün elemanlar tek tek out'a taşınır; bu sırada sıra tersine döner ve en eski eleman tepeye çıkar. Tek bir çıkarma O(n) sürebilir, ama her eleman en fazla bir kez taşınır; bu yüzden n işlemin toplamı O(n), yani işlem başına amortize O(1)'dir.

Unutma

  • Dizi elemanının adresi base + i · s'dir; erişim O(1), ortaya ekleme O(n).
  • Dinamik dizi kapasitesini geometrik artırır; bu yüzden sona ekleme amortize O(1)'dir.
  • Bağlı listede başa veya bilinen düğümden sonra ekleme O(1), indeksle erişim ise O(n)'dir.
  • Yığıt LIFO'dur (çağrılar, geri alma, parantezler), kuyruk FIFO'dur (tamponlar, BFS); ikisinin de işlemleri O(1)'dir.
  • Dairesel tampon indeksleri mod m ile sarar ve sabit bellekte bir kuyruk sağlar.
Bu derste bir hata ya da yanlışlık mı gördün?

Kendini test et

10 soru. Her doğru cevap XP kazandırır.

Soru 1 / 10

Soru 1 / 10. Kapasitesi 1'den başlayıp her seferinde iki katına çıkan dinamik bir diziye 64 eleman ekleniyor. Toplam kaç eleman kopyalanır?