Bağlı Liste

Kısaca: Bağlı liste, her elemanın bir değerinin yanında bir de referans içerdiği veri yapısıdır. ...devamı ☟

Bağlı liste, her elemanın bir değerinin yanında bir de referans içerdiği veri yapısıdır.
BAĞLANTILI LİSTELER Birçok uygulamada problemleri çözebilmek için veri kümeleri üzerinde işlem yapmak gerekir. Veri sadece bir değerden oluşabildiği gibi birden çok değerlerden de oluşabilir. Bağlı listeler en basit ve en çok kullanılan veri yapılarındandır. Yığın, kuyruk gibi diğer soyut veri yapılarını gerçeklemek için sıklıkla kullanılır. Bağlı listeler pek çok programlama dili ile uygulanabilir. Lisp ve Scheme gibi dillerin içinde bağlı liste veri yapısı gömülü olarak vardır. 1955 yılında Allen Newell, Cliff Shaw ve Herbert Simon tarafından geliştirilmiştir. Örneğin, şirketler için bir personel takibi uygulaması geliştirilmek istenmektedir. Bu uygulamada şirkette çalışan personellerin tümü veri kümesini oluşturacaktır. Personel verisini tanımlayabilmek için birden çok bilgiye ihtiyaç olacaktır. Personelin adı, soyadı, çalıştığı bölüm, maaşı gibi bilgiler verimizi oluşturan alanları temsil eder. Uygulamada çalışanların listesini alacak bir raporlama geliştirirken veri kümesindeki bütün verilere (personel bilgileri) erişebilmeli ya da belirli bir personele ait maaşı hesaplarken o personele ait bilgilere veri kümesi üzerinden arama yaparak erişilebilmeli. Burada önemli olan nokta bu veri kümesini oluşturmaktır. Bu gibi uygulamalarda çözüm yolu olarak bağlı listeleri kullanabilir[1]. Aynı kümeye ait verilerin bellek üzerinde bir gösterici (pointer) yardımı ile birbirine bağlanması sonucu oluşturulan veri yapısına bağlantılı liste denir. Bu veri yapısındaki bütün elemanların ortak noktası kendi içlerinde bağlantı bilgisi içeren kendi türünden bir ya da daha fazla göstericiye sahip olmasıdır. Veri yapısı, kümedeki herhangi bir elemanın, kendisinden önce ve kendisinden sonra hangi elemanın bulunduğu bilgisi bu göstericilere değer vererek kurulur. Bağlantılı liste, temelde liste veri modelinin bir uygulamasıdır. Yapılan liste elemanlarının bellekte tutulma şekli ve elemanların liste özelliğini bozmadan aynı kümeye ait olduklarını gösteren bağlantıların yapılmasıdır. Bellekte bağlantılı liste verileri birbirlerine sanal olarak bağlanır. Bağlantılı listenin avantajı, hafızayı dinamik olarak kullanmasıdır. Buna göre hafızadan silinen bir bilgi için hafıza alanı boşaltılacak veya yeni eklenen bir bilgi için sadece o bilgiyi tutmaya yetecek kadar hafıza alanı ayrılacaktır[2]. Bağlantılar, veri parçalarının geliş sırasına göre olabileceği gibi belirli bir anahtar sözcüğe göre sıralı özellikte yapılabilir. Eğer bağlantılar, belirli bir anahtar sözcüğe göre sıralı özellikte yapılıyorsa sıralı bağlantılı liste olarak adlandırır. Geliş sırasına göre yapılıyorsa, yalın olarak bağlantılı liste(Linked List) denir[3]. Bağlantılı liste veri yapısının genel gösterimi Şekil 2.1 de gösterilmiştir. Bağlantılı liste veri yapısı birincisi veri kısmı ikinci bağ(adres) olmak üzere iki kısımdan oluşur. Şekil 2.1 Bağlantılı Liste Veri Yapısı Veri kısmı uygulamanın gereksimine göre bir karakterlik olabileceği gibi bir string, bir tamsayı, bir kesirli sayı veya bunların karışımından oluşan bir veri kümesi de olabilir. Bağ kısmı ise bağlantılı liste üzerinde bir sonraki veri parçasının yerini işaret eden bir adres veya indis bilgisi olabilir[4]. Şekil 2.2. de bağlantılı listenin bellekte tutulma biçimi gösterilmiştir. Şekil 2.2 Bağlantılı Liste Veri Yapısının Bellekte Tutulma Biçimi Bağlantılı listenin başlangıç noktası ilk (first) adlı bir değişken tarafından tutulur; liste üzerinde işlem yaparken başlangıç noktası bu değişkende tutulur. Liste üzerindeki ara düğümlere doğrudan erişilemez ilk önce ilk adlı değişken üzerinden başlanmalıdır. Şekil 2.3. te bağlantılı listelerin genel gösterimi yer almaktadır. Şekil 2.3 Bağlantılı Listelerin Genel Gösterimi Bağlantılı liste aynı kümeye ait veri parçalarının birbirlerine, bellek üzerinde, sanal olarak bağlanmasıyla oluşur. Dolayısıyla, bağlantılı liste veri yapısında biri veri, diğeri bağlantı bilgisi olmak üzere iki kısım bulunur. Veri yapısında o uygulama için gerekli bir veya birkaç bilgi bulunabilir; işaretçi olarak adlandırılan bağlantı kısmında ise bağlantının nereye yapılacağını gösteren bir veya birkaç adres bilgisi bulunabilir[5]. Bağlantılı listeler, başka veri yapılarının gerçekleştiriminde kullanılabildikleri gibi kendileri de veri yapısıdırlar. Başa ve sona olduğu gibi araya da eleman eklenebilir; baştan ve sondan olduğu gibi ortadan da eleman çıkarılabilir. Bağlantılı liste dolaşılarak herhangi bir elemanına erişilebilir. Bir bağlantılı listenin n. elemanına erişmek için n tane işlem yapmak yani kendinden önceki (n-1) eleman üzerinden geçmek gerekmektedir. Elemanların bellekteki yerleri dizilerdeki gibi sıralı olmadığından elemanlar ve sıraları ile yerleştikleri bellek bölgeleri arasında bir ilişki yoktur[6]. Bağlantılı listelerin diziler üzerine avantajı, bir grup eleman arasına eleman eklemede ve bir grup eleman arasından eleman çıkarmada ortaya çıkar. Dizilerde bir eleman silerken arada boşluk kalmasını engellemek için ilerisindeki (sağındaki) tüm elemanları bir geriye (sola) kaydırmak gerekir. Eleman eklemede de yer açmak için konulacağı yerdeki ve ilerisindeki elemanları bir ileriye (sağa) kaydırmak gerekecektir. Kaç tane elemanın yer değiştireceği (birer kaydırılacağı) dizi boyutuna bağlı olarak ve eklenecek elemanın yerine bağlı olarak değişecektir. Bağlantılı listelerde ise eleman ekleme ve çıkarma için yapılan iş liste boyutundan bağımsızdır. Bağlantılı listeler yapı bakımından iki gruba ayrılırlar; Doğrusal bağlantılı listeler ve çevrimsel (dairesel) bağlantılı listeler. Bu yapılar işleniş açısından kendi aralarında tek yönlü, çift yönlü doğrusal bağlantılı listeler ve tek yönlü dairesel, çift yönlü dairesel bağlantılı listeler olarak ayrılır. 2.1. Bağlantılı Liste Yapıları Bağlantılı Listeler gerek bellekte tutulma biçimleri gerek genel gösterimler bakımından kendi aralarında gruplara ayrılırlar. Bağlantılı listeler; 1. Doğrusal Bağlantılı Liste a. Tek yönlü doğrusal bağlantılı listeler b. Çift yönlü doğrusal bağlantılı listeler 2. Dairesel Yönlü Bağlantılı Liste a. Tek yönlü dairesel bağlantılı listeler b. Çift yönlü dairesel bağlantılı listeler olmak üzere dört grupta gösterilir. 2.1.1. Tek yönlü doğrusal bağlantılı liste: Listedeki elemanlar arasında sadece tek bir bağ vardır. Bu tür Bağlantılı listelerde hareket yönü sadece listenin başından sonuna doğrudur. Liste üzerindeki işlemler listenin başından başlar[7]. Şekil 2.4 Tek Yönlü Doğrusal Bağlantılı Liste Yapısı 2.1.2. Çift yönlü doğrusal bağlantılı liste: Düğümler arasındaki bağlantı iki yönlü yapıya sahiptir. Bir düğüm hem bir sonraki hem de bir önceki düğümü işaret eder. Dolayısıyla iki yönlü, hem listenin sonuna hem de başına doğru hareket edilebilir. Tek yönlü bağlantılı listeye göre daha esnek bir yapıya sahiptir ve algoritmaların geliştirilmesi daha kolay olur. Çift yönlü doğrusal bağlantılı listede bağlantı bilgisi tek yönlüye göre daha büyüktür. Bu yöntem daha esnek bir yapıya sahip olduğundan bazı problemlerin çözümünde daha işlevsel olabilmektedir[8]. Şekil 2.5 Çift Yönlü Doğrusal Bağlantılı Liste Yapısı 2.1.3. Tek yönlü dairesel bağlantılı liste: Listedeki elemanlar arasında tek yönlü bağ vardır. Tek yönlü bağlantılı listelerden tek farkı ise son elemanın göstericisi ilk listenin ilk elamanının adresini göstermesidir. Bu sayede eğer listedeki elemanlardan birinin adresini biliyorsak listedeki bütün elemanlara erişebiliriz[9]. Şekil 2.6 Tek Yönlü Dairesel Bağlantılı Liste Yapısı 2.1.4. Çift yönlü dairesel bağlantılı liste: Listedeki elemanlar arasında çift yönlü bir bağ vardır. Çift yönlü doğrusal bağlantılı listeden farklı olarak son elemanın göstericisi ilk elemanın adresini göstermesidir. Şekil 2.7 Çift Yönlü Dairesel Bağlantılı Liste Yapısı Dış bağlantılar * Bilgisayar Kavramları : Bağlı Liste (Linked List)

Kaynaklar

Vikipedi

yiğit arslan - 3 yıl önce
kardeşim daha birleşik yaz ki anlayamayalım biz orayı hiç .

Görüş/mesaj gerekli.
Markdown kullanılabilir.

Düğüm (bilgisayar bilimleri)
6 yıl önce

Düğüm; ağaç, bağlı liste ve bilgisayar tabanlı örüntüler gibi veri yapıları oluşturmaya yarayan temel soyut birime verilen addır. Her düğüm bir miktar...

Hash Fonksiyonu
3 yıl önce

itibaren bağlı liste olarak dallanma başlarlar. Örneğin, 2 anahtarına ait 3 farklı veri geldi bu veriler 2 anahtarından itibaren bağlı liste kuracaklardır...

Ultratop
6 yıl önce

listelerini oluşturup yayınlayan bir kuruluştur. Oluşturulan liste de aynı adı kullanmaktadır. Uluslararası Fonogram Endüstrisi Federasyonu'na bağlı Belgian...

Atatürk Kültür Merkezi Başkanlığı
6 yıl önce

etmiştir. Liste bölgesel kalkınma, binalar, ulaşım, hidroloji ve endüstri alt başlıklarını taşımaktadır. Bu projenin ilk etabı da o liste içerisinde...

Atatürk Kültür Merkezi Başkanlığı, 1983
Kahverengi cüceler listesi
3 yıl önce

listelenmeiştir. Liste henüz tamamlanmamıştır. Ana yıldızın Sağ açıklıkna göre sıralanmıştır. 3 kahverengi cüce alanı listelenmiştir. Liste tamamlanmamıştır...

1957 Türkiye Genel Seçimleri
6 yıl önce

dereceli liste usulü çoğunluk sisteminin uygulandığı seçimler sonucunda, DP 44 ilde tam liste halinde, 3 ilde karma listeler içinde, CHP 18 ilde tam liste halinde...

Türkiye biteyi, Moltkia
6 yıl önce

Türkiye biteyinde, Moltkia cinsine bağlı toplam 2 takson bulunmaktadır. Endemik takson sayısı 1'dir. Bu liste son halidir. Moltkia aurea Boiss. Afyon,...

Türkiye biteyi, Vaccinium
6 yıl önce

Vaccinium cinsine bağlı toplam 5 takson bulunmaktadır. Bunlar 4 tür ve buna bağlı 2 varyeteden oluşur. Endemik takson sayısı 1'dir. Bu liste son halidir. Vaccinium...