LinkedList Sınıfı
LinkedList, ArrayList'e alternatif bir List uygulamasıdır; ama iç yapısı tamamen farklıdır. Dizi yerine çift yönlü bağlı liste (doubly linked list) kullanır: her eleman bir "düğümdür" ve kendinden önceki ve sonraki dü…
LinkedList Sınıfı
LinkedList, ArrayList'e alternatif bir List uygulamasıdır; ama iç yapısı tamamen farklıdır.
Dizi yerine çift yönlü bağlı liste (doubly linked list) kullanır: her eleman bir "düğümdür" ve
kendinden önceki ve sonraki düğümleri işaret eder. Bu yapı, baş/son ekleme-silmede hız kazandırır;
ama indeksli erişimde kaybettirir. Ayrıca LinkedList aynı zamanda bir Deque (çift uçlu kuyruk)
olduğundan kuyruk ve yığın olarak da kullanılabilir.
İç yapı: bağlı düğümler
null <- [baş] <-> [orta] <-> [son] -> null
Her düğüm değeri + önceki/sonraki işaretçileri tutar. Sonuçları:
- Baş/son ekleme-silme: O(1) — sadece işaretçiler güncellenir.
- İndeksli erişim
get(i): O(n) — istenen düğüme ulaşmak için baştan/sondan gezilir. - Bellek: Her eleman için ekstra iki işaretçi (ArrayList'ten daha fazla bellek).
Hem List hem Deque
LinkedList, iki arayüzü birden uygular:
// List gibi list.add("x"); list.get(0); list.addFirst("a"); list.addLast("z"); // Deque (kuyruk) gibi — FIFO q.offer(1); q.poll(); q.peek(); // Deque (yığın) gibi — LIFO s.push(1); s.pop();
Örnek 1 (./Ornek1.java) LinkedList'i List, kuyruk (FIFO) ve yığın (LIFO) olarak kullanır.
ArrayList vs LinkedList: hangisi ne zaman?
Bu, klasik bir karşılaştırmadır. Örnek 2 (./Ornek2.java) iki senaryoyu ölçer:
| İşlem | ArrayList | LinkedList |
|---|---|---|
İndeksli erişim get(i) | O(1) hızlı | O(n) yavaş |
| Sona ekleme | amortize O(1) | O(1) |
| Başa ekleme-silme | O(n) (kaydırma) | O(1) |
| Bellek | Az (kompakt dizi) | Çok (düğüm + işaretçiler) |
| Önbellek dostu (cache locality) | Evet | Hayır |
Pratik kural: Çoğu durumda ArrayList daha iyidir — modern donanımda dizinin önbellek dostluğu, LinkedList'in teorik avantajlarını çoğu zaman gölgede bırakır. LinkedList'i yalnızca gerçekten baş/son ekleme-silme ağırlıklı ve indeksli erişim yapmayan senaryolarda düşün.
Önemli: Kuyruk veya yığın gerekiyorsa,
LinkedListyerine geneldeArrayDequedaha hızlıdır (daha az bellek, daha iyi önbellek davranışı). Bunu Queue/Deque konusunda görüyoruz.
Özet
LinkedList'in çift yönlü bağlı liste yapısını; hem List hem Deque olarak kullanımını (Örnek 1);
ArrayList ile performans karşılaştırmasını — baş ekleme LinkedList'te, rastgele erişim ArrayList'te
hızlı (Örnek 2) — öğrendik. "Varsayılan olarak ArrayList; kuyruk/yığın için ArrayDeque" pratik
kuralını benimse. Sırada, anahtar-değer eşlemesinin temeli: HashMap.
▶ Kod Örnekleri(2)
Ornek1
çalıştırılabilir1// Ornek1: LinkedList — hem List hem Deque (çift uçlu kuyruk) olarak.
2// Çalıştırma: java Ornek1.java
3import java.util.LinkedList;
4
5public class Ornek1 {
6
7 public static void main(String[] args) {
8 LinkedList<String> liste = new LinkedList<>();
9
10 // List gibi: indeksli işlemler
11 liste.add("orta");
12 liste.addFirst("baş"); // başa ekle (O(1))
13 liste.addLast("son"); // sona ekle (O(1))
14 System.out.println("Liste: " + liste);
15 System.out.println("İlk: " + liste.getFirst() + ", Son: " + liste.getLast());
16
17 // Deque (kuyruk) gibi kullanım: FIFO
18 LinkedList<Integer> kuyruk = new LinkedList<>();
19 kuyruk.offer(1); kuyruk.offer(2); kuyruk.offer(3); // sona ekle
20 System.out.println("\nKuyruk (FIFO): " + kuyruk);
21 System.out.println("poll (baştan al): " + kuyruk.poll() + " -> " + kuyruk);
22 System.out.println("peek (bakma): " + kuyruk.peek());
23
24 // Stack (yığın) gibi kullanım: LIFO
25 LinkedList<Integer> yigin = new LinkedList<>();
26 yigin.push(1); yigin.push(2); yigin.push(3); // başa ekle
27 System.out.println("\nYığın (LIFO): " + yigin);
28 System.out.println("pop (baştan al): " + yigin.pop() + " -> " + yigin);
29
30 System.out.println("""
31
32 --- LinkedList ---
33 Çift yönlü bağlı liste: her düğüm önceki+sonrakini tutar.
34 Hem List (add/get/remove) hem Deque (addFirst/addLast/offer/poll/push/pop) arayüzlerini uygular.
35 Güçlü yan: baş/son ekleme-silme O(1).
36 Zayıf yan: indeksli erişim get(i) O(n) (düğümleri tek tek gezer).""");
37 }
38}Ornek2
çalıştırılabilir1// Ornek2: ArrayList vs LinkedList — hangisi ne zaman? (basit ölçümle)
2// Çalıştırma: java Ornek2.java
3import java.util.ArrayList;
4import java.util.LinkedList;
5import java.util.List;
6
7public class Ornek2 {
8
9 public static void main(String[] args) {
10 int N = 100_000;
11
12 // 1) BAŞA ekleme: LinkedList hızlı (O(1)), ArrayList yavaş (her seferinde kaydırma O(n)).
13 long t1 = sure(() -> {
14 List<Integer> l = new ArrayList<>();
15 for (int i = 0; i < N; i++) l.add(0, i); // başa ekle
16 });
17 long t2 = sure(() -> {
18 LinkedList<Integer> l = new LinkedList<>();
19 for (int i = 0; i < N; i++) l.addFirst(i); // başa ekle
20 });
21 System.out.printf("BAŞA ekleme (%d): ArrayList ~%4d ms | LinkedList ~%4d ms%n", N, t1, t2);
22
23 // 2) RASTGELE erişim: ArrayList hızlı (O(1)), LinkedList yavaş (O(n)).
24 List<Integer> arr = new ArrayList<>();
25 LinkedList<Integer> lin = new LinkedList<>();
26 for (int i = 0; i < N; i++) { arr.add(i); lin.add(i); }
27 long t3 = sure(() -> { long s = 0; for (int i = 0; i < N; i += 100) s += arr.get(i); });
28 long t4 = sure(() -> { long s = 0; for (int i = 0; i < N; i += 100) s += lin.get(i); });
29 System.out.printf("RASTGELE erişim: ArrayList ~%4d ms | LinkedList ~%4d ms%n", t3, t4);
30
31 System.out.println("""
32
33 --- ArrayList vs LinkedList ---
34 ArrayList : indeksli erişim O(1), sona ekleme amortize O(1) — ÇOĞU durumda en iyi seçim.
35 LinkedList: baş/son ekleme-silme O(1) ama indeksli erişim O(n), bellek/işaretçi maliyeti yüksek.
36 Pratik kural: VARSAYILAN olarak ArrayList kullan.
37 Kuyruk/yığın gerekiyorsa LinkedList yerine genelde ArrayDeque daha hızlıdır (sonraki konu).""");
38 }
39
40 static long sure(Runnable r) {
41 long t = System.currentTimeMillis();
42 r.run();
43 return System.currentTimeMillis() - t;
44 }
45}