Singly Linked List
Singly linked list — hər elementin (node) iki hissədən ibarət olduğu zəncirvari strukturdur: saxlanılan dəyər və növbəti node-a istinad (next). Sonuncu node-un next-i null-dır.
Massivdən əsas fərqi: node-lar yaddaşda ardıcıl deyil — hər biri heap-in istənilən yerində ola bilər və zəncir yalnız pointer-lərlə saxlanılır. Bundan hər şey doğur:
- İndeks yoxdur —
n-ci elementə çatmaq üçün başdan gəzmək lazımdır,O(n) - Əvəzində daxiletmə və silmə sürüşdürmə tələb etmir — sadəcə bir neçə pointer dəyişir
- Ölçü əvvəlcədən ayrılmır, böyütmə/köçürmə yoxdur
Siyahıya çıxış yeganə nöqtədən — head pointer-indən gedir. Head itirilsə, bütün siyahı itir (və GC onu yığır). Tez-tez əlavə olaraq tail pointer-i də saxlanılır ki, sona əlavə O(n) yox, O(1) olsun.
| Əməliyyat | Singly Linked List | Dinamik massiv | Qeyd |
|---|---|---|---|
| Başa əlavə | O(1) | O(n) | Linked list-in ən güclü tərəfi |
| Başdan silmə | O(1) | O(n) | `head = head.next` |
| Sona əlavə | O(n), tail pointer varsa O(1) | amortized O(1) | Tail saxlamaq demək olar həmişə dəyər |
| Sondan silmə | O(n) | O(1) | Sondan əvvəlki node-u tapmaq lazımdır |
| Ortadan silmə (node əlindədirsə) | O(1) — əvvəlki node məlumdursa | O(n) | Singly-də əvvəlkini tapmaq `O(n)`-dir |
| `i`-ci elementə çıxış | O(n) | O(1) | Massivin ən güclü tərəfi |
| Axtarış | O(n) | O(n) | Hər ikisi xətti |
| Yaddaş | Element başına əlavə pointer | Sıx, cache-dostu | Massiv praktikada daha sürətli gəzilir |
Əsas əməliyyatların məntiqi — hamısı pointer-lərin yenidən bağlanmasından ibarətdir və sıra vacibdir.
- Başa əlavə: yeni node yarat,
newNode.next = head, sonrahead = newNode. Sıranı tərsinə etsən, siyahının qalanını itirirsən. - Sona əlavə (tail-siz):
nextnullolana qədər gəz, sonralast.next = newNode. Siyahı boşdursa,headözü təyin olunmalıdır — bu, ən çox unudulan haldır. - Silmə: silinən node-un əvvəlkisini tap və
prev.next = target.nextet. Head silinirsə,head = head.next. - Gəzinti:
let cur = head; while (cur) { ...; cur = cur.next; }
Klassik texnika — iki pointer (fast & slow): slow bir addım, fast iki addım atır. fast sona çatanda slow ortadadır. Eyni texnika ilə dövrü (cycle) aşkarlamaq olur: siyahıda dövr varsa, fast və slow mütləq görüşür (Floyd alqoritmi) — hər ikisi O(n) time, O(1) space.
Linked list praktikada nə vaxt qazanır? Dürüst cavab: nadir hallarda — və müsahibədə bu dürüstlük yaxşı qarşılanır.
Qazandığı hallar:
- Başdan tez-tez əlavə/silmə — stack, növbə, undo zənciri
- Node artıq əlindədirsə silmə — məsələn LRU cache-də: hash map node-a birbaşa istinad verir, silmə
O(1)olur (bunun üçün doubly lazımdır) - Böyük elementlərin köçürülməsi baha başa gəlirsə — linked list heç vaxt bütöv strukturu köçürmür
- Siyahıları birləşdirmək — iki siyahını
O(1)-də bağlamaq olar
İtirdiyi hallar (yəni əksəriyyət): indekslə çıxış yoxdur; node başına əlavə pointer yaddaşı; cache lokallığı pisdir — node-lar yaddaşda səpələnib, hər addım cache miss ola bilər. Buna görə real ölçmələrdə massivi gəzmək linked list-i gəzməkdən qat-qat sürətlidir, hər ikisi O(n) olsa da.
Ona görə praktikada ArrayList/Array default seçimdir; linked list isə daha çox başqa strukturların daxili tikinti materialı kimi işlənir (hash map bucket-ləri, LRU cache, növbə implementasiyaları).
İnterview məsləhəti. "Linked list-i tərsinə çevir" bütün dünyada ən çox verilən sual ola bilər. Gözlənilən iterativ həll üç pointer saxlayır — prev, curr, next — və hər addımda curr.next = prev edir; O(n) time, O(1) space. Kod yazmadan əvvəl kağızda üç node çəkib pointer-lərin hərəkətini göstərmək çox güclü təsir bağışlayır.
Digər tez-tez verilənlər: ortanı tap (fast & slow), dövrü aşkarla (Floyd), sondan k-cı elementi tap (iki pointer arasında k məsafə), iki sıralanmış siyahını birləşdir, təkrarları sil.
Ən çox rast gəlinən səhvlər: null yoxlamalarını unutmaq (boş siyahı, tək node-lu siyahı, head-in silinməsi); pointer-ləri səhv sırada dəyişib zəncirin qalanını itirmək; while (cur.next) ilə while (cur) arasında fərqi qarışdırmaq. Sərhəd hallarını ucadan sadalamaq — boş, bir elementli, iki elementli — müsahibin gözlədiyi davranışdır.
Çox faydalı bir texnika: dummy (sentinel) head node-u istifadə etmək. Head-in xüsusi hal kimi işlənməsini aradan qaldırır və kodu nəzərəçarpacaq dərəcədə sadələşdirir.