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[3].
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[1].
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[4].
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[2].
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[2].
Ş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[4].
Ş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[2].
Ş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ı
