Liste Veri Yapısı (List)

by admin · Published 14 Temmuz 2017 · Updated 18 Temmuz 2017

Liste, tutulan elemanların birbiri ardına konularak saklandığı ve önden arkaya doğru birer birer giderek erişilebildiği veri yapısıdır. Bu veri yapısındaki elemanları düz bir çizgi üzerinde birbirine bağlanarak sıralanmış olarak düşünebiliriz.

Aşağıda bu veri yapısı tanınmaktadır;

// Listede saklanacak her bir elemanı tanımlayan sınıf
class Item {
int val; // elemanın değeri
Item next; // sonraki elemanın erişim bilgisi

// yapıcı işlev, parametre değerlerini ilgili öz niteliklere atar
Item(int val, Item next) { … }
}

// Liste sınıfı
public class List {
private Item list; // İlk elemanın erişim bilgisini tutar

// yaratıcı işlev, ilk eleman erişim bilgisi olarak null atar
public List() { … }

// listenin başına yeni bir eleman ekler, değerini parametre olarak alır
public void insert(int val) { … }

// son elemanın erişim bilgisini döndürür
public Item atEnd() { … }

// listenin sonuna yeni bir eleman ekler, değerini parametre olarak alır
public void append(int val) { … }

// listenin (eğer varsa) val değerine sahip ilk elemanını bulup siler
public void remove(int val) { … }

// listedeki eleman sayısını bulup döndürür
public int length() { … }

// listenin elemanlarını ekrana yazar
public void display() { … }
}

Yukarıdaki tanımlamada da görüldüğü gibi liste veri yapısının sonuna ya da başına eleman ekleme işlemleri append ve insert işlemleriyle gerçekleştirilmektedir. remove işlemi ise verilen bir eleman değerini (listenin herhangi bir yerinde olabilir) listeden çıkarmaktadır. Liste veri yapısında elemanlar arasındaki sıralama sadece elemanların listedeki pozisyonlarına dayalı olacaktır.

Yukarıda List sınıfının tanımından önce Item adını verdiğimiz bir başka sınıf tanımı kullanılmıştır. Bu sınıf listede yer alacak elemanları belirlemektedir ve List tanımı ile yarattığımız listeler aslında Itemnesnelerinden oluşmaktadır. Yukarıdaki Item tanımına göre yaratılan liste yapısında tam sayılar eleman olarak yer alacaklardır. Sadece bu yapının tanımını değiştirerek farklı tür ve yapılarda elemanların yer alabileceği değişik listeler tanımlamak da mümkün olabilir. Bu tanımlamada val öz niteliği ile listenin elemanlarının türü belirtilirken, next değişkeni ile herhangi bir elemanı bir sonraki elemana bağlayacak referans tanımlanmıştır. Burada next, bir sonraki Item nesnesinin erişim bilgisini tutmaktadır. Liste tanımındaki insert, append gibi işlevlerle next değerlerini değiştirmek ve böylece yeni elemanı listede başka elemanlara bağlamak mümkün olmaktadır. Tanımlanan Item nesnesi, aşağıdaki şekilde de görüldüğü gibi liste elemanının saklandığı ve bir sonraki elemana bağlantıyı sağlayan referansın yer aldığı, iki farkli kısımdan oluşmaktadır.

Aşağıdaki şekilde ise Item tanımıyla elde edilen eleman (yani nesne) yapılarının oluşturduğu bir liste yer almaktadır.

Tanımlanan liste veri yapısına çeşitli elemanlar ekleyen ve çıkaran örneğe aşağıdaki bağlantıdan erişebilirsiniz.

Liste Uygulaması: Öğrenci Listesi

Bu dersimizde bir sınıftaki öğrencilerin bilgilerinin eleman olarak yer aldığı bir listede arama işlemini uygulama olarak inceleyeceğiz. Bu uygulamada öğrenci bilgilerinin yer aldığı bir listede arama yapılmaktadır. Öğrenci bilgileri öğrencinin adı, soyadı, numarası, adresi, kaçıncı sınıfta olduğu bilgilerini içermektedir. Item sınıfı, öğrenci bilgilerini içerecek şekilde aşağıda değiştirilmiştir.

class Item {
int stdno;
String name;
String surname;
String adress;
int year;
Item next;
}

Bu tanımlamada liste yapısının değişmediğine ancak Item sınıfında (bir int değeri yerine) öğrenci bilgilerinin kullanıldığına dikkat ediniz. Bu durumda, derste tanımlanan işlevlerde listeye sadece bir tam sayı eklenip çıkarıldığından fonksiyon parametrelerinde tam sayılar yer almıştı. Ancak bu yapıyla bu işlevleri kullanmak için bu parametreleri ve işlevlerin içerisindeki atamaları öğrenci bilgileri üzerinde çalışabilecek şekilde değiştirmek gerekmektedir.

Böylesi bir List sınıfına eklenebileceği düşünülen aşağıdaki örnek işlevde, öğrenci numarası verilen öğrenci bu yeni tanımladığımız listede aranmakta ve bu öğrenciye ait bilgiler ekrana gönderilmektedir.

public void search(int key) {
Item pt=liste; // listenin başından başla
while(pt!=null && pt.stdno!=key) // sona gelmediysek ve henüz bulamadıysak
pt=pt.next; // sonrakine geç
if(pt==null) // döngüden çıkış nedenimiz sona gelmekse
System.out.println(key+”: bu numaraya sahip ogrenci yok”); // yok demektir
else { // ama değilse, bulduk: bilgileri yaz
System.out.println(“Student No: “+pt.stdno);
System.out.println(“Student Name: “+pt.name);
System.out.println(“Student Surname: “+pt.surname);
System.out.println(“Student Adress: “+pt.adress);
System.out.println(“Student Class: “+pt.year);
}
}

Aşağıdaki çizimlerde search işlevinin, verilen l1 listesi için l1.search(3456) şeklinde çağrıldığında ki işletimini inceleyebilirsiniz:

1) l1 listesi

2) l1.search(l1,3456) çağrısı yapıldığında pt referansının durumu

3) İşlevdeki while döngüsü işletildiğinde pt referansının durumu

4) if-else yapısıyla ekrana gönderilen veri

Student No: 3456
Student Name: Tanyel
Student Surname: Türkaslan
Student Adress: ODTÜ Mim. Fak.
Student Class: 5th year

Liste İşlemlerinin Gerçekleştirimi

Liste üzerindeki işlemlerin ne gibi sonuçlar verdiğini inceledikten sonra şimdi bu işlemlerin gerçekleştirmesini daha detaylı inceleyebiliriz.

Bir önceki bölümde verilen sınıf tanımındaki işlemler aşağıda tanımlanmış, Item.java ve List.java dosyalarında verilmiştir:

// Listede saklanacak her bir elemanı tanımlayan sınıf
class Item {
int val; // elemanın değeri
Item next; // sonraki elemanın erişim bilgisi// yapıcı işlev, parametre değerlerinin ilgili öz niteliklere atar
Item(int val, Item next) {
this.val=val;
this.next=next;
}
}

// Liste sınıfı
public class List {
private Item list; // İlk elemanın erişim bilgisini tutar

// yaratıcı işlev, ilk eleman erişim bilgisi olarak null atar
public List() {
list=null;
}

// listenin başına yeni bir eleman ekler, değerini parametre olarak alır
public void insert(int val) {
Item t=new Item(val,list); // eklenen elemanın değeri val, sonrası ise eski ilk eleman
list=t; // listenin başında artık bu yeni ilk eleman var
}

// son elemanın erişim bilgisini döndürür
public Item atEnd() {
Item t;
if(list==null) return null;   // liste boşsa, son eleman da yok
t=list;                       // listenin başından başla
while(t.next!=null) t=t.next; // son elemana (next öz niteliği null olan) kadar git
return t;                     // bu son elemanın erişim bilgisini döndür
}

// listenin sonuna yeni bir eleman ekler, değerini parametre olarak alır
public void append(int val) {
Item t=new Item(val,null); // eklenen elemanın değeri val, sonrası ise yok
if(list==null)              // liste zaten boşsa,
list=t;                   // ilk eleman da bu yeni eklenen
else                        // değilse,
atEnd().next=t;           // son elemanın sonrası yeni eklenen eleman
}

// listenin (eğer varsa) val değerine sahip ilk elemanını bulup siler
public void remove(int val) {
Item t=list;
if(t==null) return; // liste boşsa yapacak işlem yok
if(t.val==val)       // listenin ilk elemanı val değerine sahipse,
list=t.next;       // 2. eleman artık listenin başında
else {               // değilse,
Item prev=t;       // prev, t’nin baktığı elemanın öncesini tutsun
t=t.next;          // t de, bakmaya 2. elemandan başlasın
while(t!=null && t.val!=val) { // t sona gelmediyse ve değeri val’dan farklı ise
prev=prev.next;               // hem prev,
t=t.next;                     // hem t bir ilerlesin
}
if(t==null) return; // döngüden çıkış nedeni sona gelmiş olmaksa, bulamadık demek
prev.next=t.next;    // ama değilse, bulduk: prev’in sonrası, artık t’nin sonrası
}                      // yani t elemanı listeden kopartıldı, aradan çıkartıldı
}

// listedeki eleman sayısını bulup döndürür
public int length() {
Item t=list;      // listenin başından başla
int i=0;          // sayaç 0
while(t!=null) { // sona gelmediysek
i++;            // sayacı artır
t=t.next;       // sonraki elemana geç
}
return i;         // sayaç değerini döndür
}

// listenin elemanlarını ekrana yazar
public void display() {
Item t=list; // listenin başından başla
while(t!=null) { // sona gelmediysek
System.out.print(t.val+” “); // elemanın değerini yaz
t=t.next; // sonraki elemana geç
}
}
}

Yukarıda tanımlanan işlevlerde insert ve append listenin başına ve sonuna eleman ekleme işlemlerini gerçekleştirmektedir. Burada append işlevinde, listenin son elemanının bulunması için atEnd işlevi kullanılmıştır. remove işlevinde ise, ilk if ifadesinde eğer listenin ilk elemanı val parametresinde belirtilen değere sahip ise, bu eleman listeden çıkarılmakta, else kısmında yer alan döngüde ise eğer listenin ortasında uygun bir eleman varsa, bu eleman listeden çıkarılmaktadır. Listenin başında yer alan bir elemanın silinmesi için list göstergecinin bir sonra ki elemanı gösterir hale getirilmesi yeterliyken, listenin ortasındaki bir elemanın silinmesi için aşağıdaki şekilde de gösterildiği gibi, ek bir işlem olarak silinecek elemandan bir önceki elemanın next referansı, silinecek elemandan bir sonraki elemanın erişim bilgisini tutan bir hale getirilmektedir. Bu farklı iki durumdan dolayı, remove fonksiyonu iki ayrı bölümden oluşmaktadır.

Yine bu veri yapısı için de bir yaratıcı işlev tanımlanmış olup, burada liste elemanlarının ilkinin erişim bilgisini tutan list öz niteliğine, listede henüz eleman bulunmadığı için null değeri atanmıştır.Ayrıca listenin uzunluğunu bulan ve listenin elemanlarını gösteren işlevler, length ve display tanımlanmıştır.