Veri yapıları serimize kaldığımız yerden devam ediyoruz. Geçen hafta veri yapılarına giriş yapmıştık bu hafta da soyut veri yapılarından serimize devam edeceğiz. Soyut veri yapılarına geçmeden önce, konunun temelini oluşturduğu için dizileri ayrıntılı bir şekilde inceleyeceğiz. Bu sayede, yazının ilerleyen bölümlerinde ele alacağımız soyut veri yapılarını daha kolay anlayabileceksiniz. O zaman diziler ile yazımıza başlayalım.
Diziler (Array)
Dizi Nedir?
Diziler, aynı veri tipindeki elemanları bellekte art arda saklayan bir veri yapısıdır. Bu yapı, verilere sıralı ve düzenli bir şekilde erişim sağlar.Günlük hayattan bir örnekle açıklayalım: Bir kitap rafını dizi olarak düşünün. Raftaki her bir kitap, dizinin bir elemanını; rafın kendisi ise dizinin bütününü temsil eder. Diziler de tıpkı bu örnekteki gibi verileri sıralı bir şekilde bellekte saklar.
Önemli bir nokta: Bir diziyi tanımlarken hangi veri tipini (int, string vb.) belirlediyseniz, içine yalnızca o veri tipine ait elemanlar ekleyebilirsiniz.
Peki, art arda sıralanmış bu elemanlara nasıl erişiriz? Dizilerde her elemanın bir indeks değeri vardır. Bu indeksleme, çoğu programlama dilinde 0'dan başlar. Yani, dizinin ilk elemanına erişmek için 0. indeksi kullanmanız gerekir.
C++ Dilinden Örnekler:
DİPNOT: C, C++ gibi dillerde dizi tanımlaması yaparken dizinin kaç eleman barındıracağını belirtmek zorunludur.
int notlar[5] = {78,90,100,95,86};
notlar adındaki dizinin 1. elemanı olan 78 erişelim ve konsolda yazdıralım:
cout << "Dizinin 1. elemanı: " << notlar[0]; Çıktı: 78
// Diğer elemanlara da erişip ekranda yazdıralım:
cout << "Dizinin 2. elemanı: " << notlar[1]; Çıktı: 90
cout << "Dizinin 3. elemanı: " << notlar[2]; Çıktı: 100
cout << "Dizinin 4. elemanı: " << notlar[3]; Çıktı: 95
cout << "Dizinin 5. elemanı: " << notlar[4]; Çıktı: 86
Dizilerin Avantaj ve Dezavantajları
Bir program yazarken kullandığımız ve kullanacağımız veri yapıları ve bu veri yapılarının programın performansına etkisi oldukça önem taşır. Özellikle büyük çaplı projelerde bu husus oldukça önemlidir. Peki dizileri kullanırsak bize ne tür avantaj ve dezavantaj sağlar?
Avantajları:
- Hızlı Erişim: Dizilerdeki verilere indeksler yardımıyla erişebileceğimizi söylemiştik. Bu indeksleme ile istenen veriye anında erişebilirz.Bu işlem, teknik olarak O(1) karmaşıklığına sahiptir. Yani dizide 5 eleman da olsa, 5 milyon eleman da olsa, bir elemana erişim süresi neredeyse aynıdır. Bu, dizinin en büyük avantajıdır.
- Bellekte Bitişik Konumlandırma: Elemanların bellekte yan yana olması, bilgisayarın bu verilere daha hızlı erişmesini sağlar.
Dezavantajları:
-
Sabit Boyutlu Olması: Bir dizinin boyutu genellikle tanımlandığı anda belirlenir ve sonradan kolayca değiştirilemez. Eğer daha fazla eleman eklemek gerekirse, daha büyük yeni bir dizi oluşturup eski elemanları buraya kopyalaman gerekir. Bu da maliyetli bir işlemdir.
-
Ekleme/Silme İşlemlerinin Maliyeti: Dizinin ortasına bir eleman eklemek veya silmek, diğer elemanların yerini değiştirmeyi gerektirir. Bu işlem, dizinin boyutuyla doğru orantılı olarak uzun sürer (O(n) karmaşıklık).
Dizi Örneği
1. Dizi oluşturma:
// C++'da dizi oluşturma örneği
string isimler[3] = {"Ali", "Ayşe", "Mehmet"};
2. Elemanlara Erişim:
// İlk elemana erişim
cout << isimler[0]; // Çıktı: Ali
3. Eleman Güncelleme:
// İkinci elemanı güncelleme
cout<<isimler[1]; // Çıktı: Ayşe
isimler[1] = "Fatma";
cout<<isimler[1]; // Çıktı: Fatma
Dizilerin bellekteki sabit boyutu ve eleman ekleme/silme gibi işlemlerdeki performansı, bazı senaryolarda bizi zorlayabilir. İşte tam da bu noktada, bağlı listeler (linked list) devreye girer. Şimdi, dizilerin bu dezavantajlarına çözüm sunan bağlı listelerin ne olduğunu ve nasıl çalıştığını inceleyelim.
Bağlı Listeler (Linked List)
Bağlı Liste Nedir?
Bağlı listelerdeki elemanlar bellekte diziler gibi art arda saklanmaz. Bu nedenle de bağlı listedeki elemanlara inkesler ile erişilmez.
Bir bağlı listedeki her eleman, düğüm (node) adı verilen bir yapıdan oluşur ve bu düğümler iki kısımdan meydana gelir. Bu kısımlardan birine data (veri) denir ve o elemanın değeri tutulur, diğer kısıma ise pointer denebilir ve bir işaretçi (pointer) bulunur. Bu işaretçi bu elemandan sonraki elemanın bellekteki adresini işaret eder. Bu işaretçiler aracılığıyla birbirine bağlanan düğümler, bağlı liste veri yapısını oluşturur. Bağlı listelerin ilk elemanına yani ilk düğümünde head (baş) düğüm denir ve bağlı listelerin başlangıç noktasıdır. Liste üzerinde eleman ekleme, silme, güncelleme ve liste üzerinde dolaşabilme için bu referans düğüm (head) kullanılır.
Bağlı Listenin Avantaj ve Dezavantajları
Dizilerin aksine bağlı listeler, sabit bir bellek alanına bağlı kalmaz. Bu durum, bize eleman sayısı konusunda esneklik sunar. Ayrıca, dizilerde elemanlar bellekte art arda tutulmak zorundayken, bağlı listelerin düğümleri belleğin herhangi bir yerinde bulunabilir. Bu özellik, belleğin daha verimli kullanılmasına olanak tanır. Bağlı listelerin avantaj ve dezavantajlarına yakından bakalım:
Avantajları:
-
Esnek Boyut: Dizilerin aksine, bağlı listelerin boyutu sabit değildir. İhtiyaç duydukça yeni elemanları kolaylıkla ekleyebiliriz.
-
Hızlı Ekleme/Silme İşlemleri: Listeye yeni bir eleman eklemek veya mevcut bir elemanı silmek çok hızlıdır. Bu işlem, sadece birkaç işaretçi adresini değiştirmeyi gerektirir ve O(1) karmaşıklığına sahiptir. Bu, bağlı listelerin en büyük avantajıdır.
Dezavantajları:
-
Yavaş Erişim: Dizilerdeki gibi direkt indeksle erişim (random access) mümkün değildir. İstediğimiz elemana ulaşmak için listenin başından itibaren tüm düğümleri tek tek gezmek gerekir. Bu işlem, listedeki eleman sayısıyla doğru orantılıdır ve O(n) karmaşıklığına sahiptir.
-
Ek Bellek Kullanımı: Her düğümde veriye ek olarak bir de işaretçi saklandığı için, bağlı listeler dizilere göre daha fazla bellek kullanır.
Kod Örneği
C++ dilinde bağlı liste yapısı oluşturup işlem yapalım:
İlk aşama bağlı listenin her bir elemanını (düğümü) oluşturma:
class Node { // düğüm yapısı class ile veya struct veri yapısı ile oluşturulabilir
public:
int data; // Düğümün sakladığı veri
Node* next; // Bir sonraki düğümü gösteren işaretçi
Node(int val) {
data = val;
next = NULL;
}
};
Düğüm yapısını oluşturduktan sonraki aşamamız bağlı liste sınıfı oluşturmaktır. Böylece tüm düğümleri bağlı liste adı altında toplayabileceğiz.
class LinkedList {
public:
Node* head; // Listenin ilk düğümünü (başını) gösteren işaretçi
LinkedList() {
head = NULL; // Başlangıçta liste boş olduğu için head NULL'dur.
}
Listeye yeni bir düğüm ekleme fonksiyonu oluşturuyoruz.
void append(int val) {
// Yeni bir düğüm oluştur
Node* newNode = new Node(val);
// Liste boşsa, yeni düğüm ilk düğüm olur
if (head == NULL) {
head = newNode;
return;
}
// Liste boş değilse, son düğümü bul
Node* lastNode = head;
while (lastNode->next != NULL) {
lastNode = lastNode->next;
}
// Yeni düğümü son düğümün sonuna ekle
lastNode->next = newNode;
}
Listeyi ekrana yazdırma fonksiyonu
void printList() {
Node* temp = head;
while (temp != NULL) {
std::cout << temp->data << " -> ";
temp = temp->next;
}
std::cout << "NULL" << std::endl;
}
};
Main fonksiyonunda ise oluşturduğumuz bu yapıları kullanıyoruz:
int main() {
// ilk Bağlı liste nesnesi oluştururuyoruz
LinkedList myList;
// Oluşturduğumuz fonksiyonlar ile Listeye eleman ekliyoruz
myList.append(10);
myList.append(20);
myList.append(30);
// Listeyi ekrana yazdırma
std::cout << "Bagli Liste: ";
myList.printList(); // Çıktı: Bagli Liste: 10 -> 20 -> 30 -> NULL
return 0;
}
Vakit ayırdığınız için teşekkür ederim. Umarım faydalı olmuştur. Bir sonraki yazımızda stack ve queue veri yapılarını ele alarak serimize devam edeceğiz. Takipte Kalın!
Önceki bölüm olan “Veri Yapıları 1” yazısını okumak için tıklayın.