Yan yana

DizivsBağlı Liste

Dizi ile bağlı liste arasındaki fark nedir?

Güncellendi 30 Eylül 20262 dk okuma7 fark

Kısaca

Dizi elemanları bellekte yan yana tutar, her elemana indeksiyle anında ulaşılır; bağlı liste ise düğümleri işaretçilerle bağlar: ekleme ucuz, arama yavaştır.

Programlamanın Temelleris. 15

Dizi

Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.

Dizi sayfasını oku

Veri Yapılarıs. 4

Bağlı Liste

Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.

Bağlı Liste sayfasını oku

Dizi ve Bağlı Liste karşılaştırması

Özellik	Dizi	Bağlı Liste
Bellek düzeni	Tek bir bitişik bellek bloğu	Bellekte herhangi bir yere dağılmış, işaretçilerle bağlı ayrı düğümler
İndeksle erişim	O(1): doğrudan istenen konuma atlanır	O(n): liste baştan gezilir
Başa ekleme ya da baştan silme	O(n): sonraki her eleman kaydırılmalı	O(1): bir iki işaretçi güncellenir
Sona ekleme	Dinamik dizilerde amortize O(1)	Liste bir kuyruk işaretçisi tutuyorsa O(1)
Bellek yükü	Düşük: yalnızca elemanlar ve yedek kapasite	Daha yüksek: her düğüm ayrıca bir ya da iki işaretçi tutar
Önbellek performansı	Mükemmel: komşular birlikte yüklenir	Zayıf: her düğüm bellekte herhangi bir yerde olabilir
En uygun olduğu yer	İndeksle erişim, dolaşma ve günlük listelerin çoğu	Bilinen konumlarda sık ekleme ve çıkarma

Fark, açıklamalı

Dizi, elemanları sıralı biçimde tutan bitişik bir bellek bloğudur; bu yüzden i numaralı elemanın yeri doğrudan hesaplanabilir. Bağlı liste ise düğümlerden oluşan bir zincirdir; her düğüm bir değer ile bir sonraki düğüme bir işaretçi (referans) tutar, çift bağlı listede ayrıca bir öncekine de.

Fark bellek düzeninden gelir. Dizi elemanları yan yana durduğu için arr[500] okumak sabit zaman, O(1), alır; ama başa eleman eklemek diğer tüm elemanları kaydırmak demektir, O(n). Bağlı liste, komşusuna bir referans tuttuğunuzda bir düğümü O(1)'de ekleyip çıkarabilir; ama 500. elemana ulaşmak, ondan önceki 499'u tek tek gezmek demektir.

Çoğu kodda varsayılan olan dizilerdir; JavaScript dizileri, Python listeleri ve Java'nın ArrayList'i gibi dinamik diziler dolduklarında daha büyük bir bloğa kopyalanarak kendiliğinden büyür. Bağlı listeler ise genellikle kuyruklar, LRU önbellekleri ve hash tablosu kovaları gibi başka yapıların içinde görünür; oralarda ucuz ekleme ve çıkarma, indeksle erişimden daha önemlidir.

Sık yapılan bir yanlış, bağlı listelerin genel olarak eklemede daha hızlı olduğu düşüncesidir. O(1) ekleme yalnızca doğru düğüme zaten sahipken geçerlidir; onu bulmak O(n)'dir ve dizi elemanları CPU önbellek satırlarını paylaştığı için, çok ekleme yapılan iş yüklerinde bile diziler pratikte çoğu zaman daha hızlıdır.

Hangisini kullanmalısınız?

Dizi şu durumlarda doğru seçim:

Elemanları sık sık indeksle okuyorsunuz.
Çoğunlukla eleman ekleyip üzerlerinde döngü kuruyorsunuz.
Bellek verimliliği ve önbellek hızı önemli.

Bağlı Liste şu durumlarda doğru seçim:

Başa ya da ortaya sürekli eleman ekleyip çıkarıyorsunuz.
Değiştirdiğiniz düğümlere zaten referansınız var.
Bir kuyruk, çift uçlu kuyruk (deque) ya da LRU önbelleği kuruyorsunuz.

Her yapıda erişim ve ekleme

Dizipython

# Array (a Python list): instant access by index
items = [10, 20, 30, 40]
print(items[2])      # 30, O(1)

items.append(50)     # amortized O(1) at the end
items.insert(0, 5)   # O(n): every item shifts right

Bağlı Listepython

# Linked list: each node points to the next one
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(10, Node(20, Node(30)))
head = Node(5, head)  # O(1): new head, nothing shifts

node = head
while node.next:      # O(n) to reach the end
    node = node.next

Sık sorulan sorular

Diziler neden genellikle bağlı listelerden daha hızlıdır?

Dizi elemanları yan yana saklandığı için CPU herhangi bir konumu doğrudan hesaplayabilir ve birkaç komşuyu aynı anda önbelleğine yükleyebilir. Bağlı liste düğümleri dağınıktır; bu yüzden her adım belleğe yapılan yavaş bir yolculuk olabilir.

Bağlı listeyi ne zaman kullanmalıyım?

Kuyruklarda, LRU önbelleklerinde ya da geri alma geçmişlerinde olduğu gibi, referansına zaten sahip olduğunuz konumlara sık sık eleman ekleyip çıkardığınızda ve indeksle erişime nadiren ihtiyaç duyduğunuzda.

JavaScript dizisi bir bağlı liste midir?

Hayır. JavaScript motorları dizileri dinamik dizi olarak saklar; çok seyrek olanlar için sözlüğe benzer bir düzene geçer. Bu yüzden indeksle erişim hızlıdır.