Mustafa Kemal Üniversitesi

Algoritma Geliştirme ve Veri Yapıları – 7
Liste ve Bağlantılı Liste
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Liste birbiriyle ilişkili verileri içeren bir kümedir,
programlama açısından liste en basitinden bir dizi
üzerinde tutulur. Dizi elemanları art arda gelen
bellek gözlerinde tutulur.
• Bağlantılı liste ise aynı kümeye ait verilerin
birbirlerine bellek üzerinde sanal bağlar ile
bağlanması ile oluşur.
• Bağlantılı listenin zayıf yönü, liste üzerindeki ara
elemanlara kolayca erişilememesi ve sık sık arama
gerektiren uygulamalarda arama karmaşıklığının
göreceli olarak büyük olmasıdır.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Uzunluk: Liste üzerindeki düğümlerin sayısıdır.
• Anahtar Sözcük: Liste üzerinde arama yapılacağı
veya listenin sıralanacağı durumlarda kullanılacak
veri parçasıdır.
• Öncelikli Liste: Listeye yeni verilerin eklenmesi
işleminde eklemenin bir bir anahtar değere göre
sıralı yapılmasıdır(Öğrenci numarasına göre).
• Boş Liste: Liste veya bağlantılı listenin hiçbir
elemanı olmaması; üzerinde hiçbir veri
tutulmamasıdır. Bu durumda ilk ve son
işaretçilerinde boş anlamında NULL değer tutulur.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Bağlantılı liste türleri:
o Tek Yönlü Bağlantılı Liste
• Birbirini izleyen düğümler arasında tek-yönlü
bir bağlantı vardır. Ekleme, arama, listeleme gibi
işlemlerin karmaşıklığı O(n) dir. Listenin
oluşturulması için iki tane işaretçi kullanılırsa
ekleme karmaşıklığı O(1), arama ve listeleme
karmaşıklığı O(n) olur.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Bağlantılı liste türleri:
o Çift Yönlü Bağlantılı Liste
• Düğümler arasındaki bağlantı hem ileri hem de öne
doğru ilerleyecek şekilde iki yönlüdür. Yani bir düğüm
hem bir sonraki hem de bir önceki düğümü işaret eder.
• Çift yönlü bağlantılı liste araya ekleme ve silme
işlemlerini de kolaylaştırır. Çünkü silinecek düğümün
hem arkasındaki hem de önündeki düğüm bilindiği için
silmeyi sağlayacak bağlantı düzenlemesi kolayca yapılır.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Bağlantılı liste türleri:
o Çevrimsel Bağlantılı Liste
• Düğümler arasında çevrimsel bir bağlantı vardır.
Yani listenin son düğümü ilk düğümünü işaret
eder. Böylece çevrimsel bir yapı oluşturulur.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Gereksinimler
o İşaretçi değişkenler ve liste için gerekli veri
yapısının tanımlanması
o Dinamik bellek ihtiyacı
• Bellek ihtiyaçları malloc() veya benzeri bir fonksiyon ile
sağlanır belleğin kullanımının ardından free() veya
benzeri bir fonksiyonla bellek kullanımı durdurulabilir.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Dinamik
bellek
kullanılması
sebebiyle tanımlamalar işaretçi
kullanılarak gerçekleştirilir.
• Bağlantılı liste boş iken her iki
değerde NULL dur.
• İlk eleman içi bellekten yer tahsis
edilmesi şekilde gösterilmiştir.
• Oluşturulan
elemanı
bellek
yönetimine geri iade etmek için
free(p) fonksiyonunu kullanmak
yeterlidir.
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Bağlantılı Liste Veri Yapısı
struct baglantililiste{
int sayi;
struct baglantililiste *arka;
};
struct baglantililiste *ilk=NULL, *son=NULL;
baglantililiste *p;
p=(baglantililiste *)malloc(sizeof(struct baglantililiste));
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Ekleme işlemi
baglantililiste *p=(baglantililiste *)malloc(sizeof(struct baglantililiste));
if(p!=NULL){
if(ilk==NULL){
ilk=p; son=p;
ilk->arka=NULL; son->arka=NULL;
}else{
son->arka=p; son=p;
p->arka=NULL;
}}
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Listeleme İşlemi
baglantili *adr =ilk ;
while(adr!=NULL)
{
cout<<(adr->sayi)<<endl;
adr=adr->arka;
}
Mustafa Kemal Üniversitesi
Liste ve Bağlantılı Liste
• Silme İşlemi
baglantili *adr=ilk,*onceki=ilk,*silinecekveri=silinecek;
while(adr!=NULL){
if(adr ==silinecekveri){
onceki->arka=adr->arka;
free(adr);
Break;
}
onceki=adr;
adr=adr->arka;
}
Mustafa Kemal Üniversitesi