"Enter"a basıp içeriğe geçin

Linked List

 

Arraylistlerde araya eleman eklediğimizde, eğer kapasiteyi aşmış isek hafızada dizinin sonunda 1 yer daha ayrılır ve eklenecek indexten sonraki her eleman sırayla sonraki indexe kaydırılır. En son istediğimiz indexe eklenir.

Ancak eğer çok büyük bir dizimiz varsa tüm elemanları tek tek kaydırmak çok maliyetli bir işlemdir. Ve eğer kodumuzda bu işlemi sürekli yapacaksak kodumuz çok yavaşlar.

Linkedlistlerin yapısı arraylerden çok farklıdır. Elemanlar yan yana değildir. Hafızada rastgele adreslerde bulunurlar. Lİnked list’in ismi ilk elemanı gösteren bir referanstır. Buna head de denir. Linked List’lerde elemanlar Node’lar halindedir. Her bir hafıza bloğunda prev data ve next denen 3 kısım bulunur. prev’in içinde önceki, next’in içinde sonraki elemanın referansı vardır. Data ise içeriğimizi tutar.

Linked listleri zincir gibi de düşünebiliriz. Araya yeni bir halka ekleyeceğimiz zaman zinciri bir yerden koparır ve kopan yere yeni halkayı takarız.

zincirin son elemanı hiçbir yeri göstermez. Bu referansa NULL denir. Eğer zincirin sonuna yeni bir eleman eklemek istersek yeni eleman için hafızada yer alındıktan sonra NULL yerine yeni elemanın adresi eklenir. Yeni eklenen eleman da artık NULL göstermeye başlar.

Elemanların yan yana olmaması normal erişimde performansı azaltır. Araya elaman ekleme işlemi arraylistlere göre çok daha rahattır.

Mesela 3. ve 4. indexin arasına bir eleman ekleyelim.
eleman için hafızada bir yer ayrılır.
3. indexin sonunda 4. indexin yerini gösteren kısım silinir ve yeni eklenen elemanı göstermesi sağlanır.
Yeni eklenen eleman da eskiden 4. indexte bulunan adresi göstermeye başlar.
Böylece sadece 3 işlem yaparak Araya eleman eklemiş oluruz.

Eğer aradan eleman silmek istersek de benzer bir mantık kullanılır.

6. elemanı silmek istediğimizde 5. elemanın 7. elemanı göstermesini sağlamamız yeterlidir. Artık 6. eleman zincirden çıkmış olur. Sonra da eskiden 6. eleman olan hafıza bloğunu yok eder. Böylece çöp kalmamış olur.

Basit bir linked list sınıfı yazalım:

Elbette daha bir çok özellik ekleyebiliriz.

Array list mi Linked list mi kullanmamız gerektiği konusuna gelirsek:

  • Eğer eleman sayımız az ise araya eleman ekleneceği zaman yapılacak kaydırma işlemlerinin maliyeti çok yüksek olmayacaktır. Elemanlar da hafızada yan yana olacağı için oldukça performanslı çalışır.
  • Ancak eleman sayısı fazla ise, mesela 10000 eleman varsa araya her eleman ekleneceği zaman binlerce işlem yapılması gerekir. Linked listte ise sadece 3 işlem yapılarak araya eleman eklenebilir.

Sonuç olarak eleman sayımız az ise veya araya sürekli eleman eklemeyeceksek Arraylist kullanmak mantıklıdır.

Eğer araya sürekli eleman eklememiz gereken uzun bir listemiz varsa Linkedlist kullanmamız gerekir. Çünkü linked listte bilinen index’e eleman ekleme işlemi eleman sayısından bağımsızdır.

Eğer eklenecek indexi gösteren bir iteratör yoksa arama işlemi yapılacağı için bu durum linkedlist’in ekleme hızını azaltacaktır.

Sona eleman ekleme işlemi ikisinde de hemen hemen aynı hızdadır. Eğer sadece sona eleman eklenecekse, eğer ArrayList’in kapasitesi de yeterliyse çalışma hızları birbirine yakın olacaktır.

Aynı şekilde, linkedlist’te bilinmeyen konuma eklemek ile, kapasitesi dolmamış Array’e eleman eklemen hemen hemen benzer hızda olacaktır.

 

Linkedlistin bir diğer dezavantajı, içinde referans taşıdığı için hafızada daha fazla yer kaplamasıdır.
Eğer listenin tiği, boyutu çok büyük olan, mesela 100 bayt yer kaplayan bir sınıf nesnesi ise bu ekstra yer bizi çok etkilemez Ancak eğer int, char gibi basit bir veri tipine ait bir listemiz varsa, bir de referans için yer harcamak hafıza kullanımını ciddi şekilde etkiler.

Hangi veri tipini seçeceğimizi düşünürken hem hafıza hem de performans kazancını gözetmemiz gerekir.

Arka planda yapılan işlemler farklı olsa da, kod yazarken ki kullanımları nerdeyse aynıdır.

Java dilinde çok gelişmiş bir Linked List sınıfı hali hazırda mevcuttur. Bir çok fonksiyon içerir ve bunları çok rahat bir şekilde kullanabiliriz.

Özet:

ArrayList
• Veriler ardışık tutulur.
Bu yüzden arama hızı yüksektir.• Sona eleman ekleme
Kapasite dolmamışsa: O(1) zaman
Kapasite dolmuşsa: O(n) zaman

• Ekleme-silme
Kaydırma yüzünden O(n)

Linked list
• Veriler rastgele konumlarda tutulur.
Bu yüzden arama hızı düşüktür.• Başa eleman ekleme: O(1) time
• Verilen index’e eleman ekleme: O(n)
Çünkü gezme işlemi yapılır.

• Eleman silme
Gezme varsa: O(n)
Gezme yoksa: O(1)

 

Linked list oluşturma

Java’nın Collection Framework’ü içinde bizim için hazırlanmış bir linked list sınıfı mevcuttur.

LinkedList<String> şehirler =new LinkedList<String>();
String tipinde bir linkedlist oluşturduk ve İlk elemanı tutması için şehirler adında bir referans ekledik.
Şuanda boş olduğu için referans NULL gösteriyor.
şehirler.add(“İstanbul”); diyerek ilk elemanı ekleyebiliriz.

listeyi yazdırmak için foreach döngüsü kullanırız.

şehirler.add(5,”Kütahya”); diyerek araya ekleyebiliriz

şehirler.remove(4); diyerek 4. indexi silebiliriz.

List Iterator Vs Iterator

List Iterator ile Iterator farklı şeylerdir. List Iterator, List interface’inden türeyen sınıflarda bulunur.Ve next-previous işlemlerini yapar.

Iterator ise tüm Collection sınıflarında kullanılabilir.. Ancak previous işlemi yapılamaz.

Linkedlistlerde herhangi bir elemana erişmek için ilk elemandan başlayarak tüm listeyi gezmemiz gerekir.

Bu gezme işlemini gerçekleştirmek için List iteratörler kullanırız.
İteratörler, Linkedlistteki bir elemanı işaret eden referanslardır.

ListIterator<String> it1 = şehirler.listIterator(); diyerek iteratörümüzü oluşturabiliriz.
Şuanda it1 boş bir yerde. Bulunduğu yerde sadece ilk elemanın referansı var.

it1.next(); fonksiyonu, it1’in bulunduğu yerdeki referansın gösterdiği adresi gösterir. Yani bu durumda it1.next(); İstanbulu gösteriyor demektir.

System.out.println(it1.next()); dersek İstanbul bastırır ve imleç istanbul bloğuna kayar. İstanbul bloğunun içinde sonraki eleman olan manisanın referansı var. Yani it1.next() manisayı gösteriyor. Tekrar System.out.println(it1.next()); dersek Manisa yazdırır ve sonraki elemana geçer.

it1.previousIndex(); iteratörün mevcut indexini gösterir.

it1.previous(); imleci bir önceki yerine kaydırır.
System.out.println(it1.previous()); diyerek önceki yere kaydırıp onun next’ini (yani ilk olduğu yeri) yazdırabiliriz.

Burada dikkat etmemiz gereken, it.next() ve it.previous(), linkedlistteki next ve prev’den farklıdır.

previousIndex önceki indeksi gösteriyor. NextIndex ise şuankini. previous() İteratörü önceki elemana kaydırıp onda işlem yapıyor. next() ise önce mevcut konumda işlem yapıyor, ardından sonraki elemana kayıyor.

it1.add dersek, it1’in olduğu yerdeki referansı siler, buraya yeni hafıza bloğunun referansını ekler. Ve yeni hafıza bloğunun içine de referansı silinen hafıza bloğunun referansını ekler.

Başlangıçta it1’in olduğu yerdeki referans istanbulu gösteriyordu. add fonksiyonu yüzünden İstanbulu gösteren referans silindi. it1’in olduğu yerdeki referans Sivas göstermeye başladı. Sivas bloğundaki referans da İstanbulu gösterir.
Böylece Sivası En başa eklemiş olduk.

Linkedlistin son elemanı NULL gösterir. Son eleman olup olmadığını kontrol etmek için list.hasNext(); kullanılır.
if(!list.hasNext()) eğer liste boş ise veya son elemanda isek if’e girer.

list.previous() öncesinde eleman var mı diye bakar. Eğer ilk eleman ise false döner.

Unutulmamalıdır ki, previous kullanarak geri giderken sout ile yazdırırsak, imleç öncekine gider ancak sout öncekini değil de öncekinin gösterdiği yeri bastırır.

.compareTo(); karşılaştırma için kullanılır.

Diğer önemli fonksiyonlar

void addFirst(Object o) : Başa ekler
void addLast(Object o) : Sona
void clear() : Tüm Node’lar silinir
Object clone() : Klonlar
boolean contains(Object o) : Nesneyi arar
Object get(int index) :Belirtilen indisteki elemanı döndürür.
Object getFirst() : Listenin ilk üyesin, verir.
Object getLast() : Listenin son üyesini verir.
int indexOf(Object o) : Listede arar ve indexini verir. Yoksa -1 döner
int lastIndexOf(Object o) :Aramayı sonran başa yapar
Object remove(int index) : Belirtilen indexteki elemanı siler
boolean remove(Object o) : Verileni ilkgördüğü konumundan siler.
Object removeFirst() : Listenin ilk elemanını siler ve döndürür.
Object removeLast() : Listenin son elemanını siler; metodun değeri silinen öğedir.
Object set(int index, Object element) : Verilen nesneyi istenen indisli eleman ile değiştirir.
int size() : Listedeki elemanı sayısını verir.
Object[] toArray() : Listedeki elemanları, aynı sırada bir arraye dönüştürür.

    Bir cevap yazın

    E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir