Question 1

Doubly linked list nədir və singly-dən nə ilə fərqlənir?

Accepted Answer

Fərqi bir cümlə ilə de, sonra qazanc və qiyməti ayrı-ayrı sadala — müsahiblərin gözlədiyi tarazlıq budur. Fərq: hər node next-dən əlavə prev istinadı da saxlayır. Qazanc: İstinadı əlində olan node-u O(1)-də silmək (singly-də O(n), çünki əvvəlkini tapmaq lazımdır) Geriyə gəzinti — browser history, undo-redo, mətn kursoru tail ilə birlikdə hər iki ucda O(1) əlavə/silmə, yəni təbii deque davranışı Qiymət: Node başına əlavə pointer — yaddaş; kiçik dəyərlərdə metadata payload-dan çox ola bilər Hər əməliyyatda iki istinadı sinxron saxlamaq — səhv etmək asandır və səhv səssiz qalır Sonda praktik nümunə ver: "LRU cache məhz doubly tələb edir, çünki hash map-dən tapdığım node-u siyahıdan O(1)-də çıxarmalıyam — singly ilə bu mümkün deyil." Bu bir cümlə cavabı nəzəri təsvirdən praktik anlayışa çevirir.

Question 2

LRU cache-i necə implementasiya edərsən?

Accepted Answer

Bu, doubly linked list-in ən çox verilən tətbiq sualıdır. Cavabı dörd addımda qur. 1. Tələbi aydınlaşdır: həm get, həm put O(1) olmalıdır; tutum dolanda ən çoxdan istifadə olunmamış element atılır. 2. Niyə tək struktur bəs etmir: hash map O(1) axtarış verir, amma sıra saxlamır. Siyahı sıra saxlayır, amma açara görə axtarış O(n)-dir. Deməli ikisini birləşdirmək lazımdır. 3. Dizayn: HashMap<Key, Node> + doubly linked list. Siyahının başı — ən son istifadə olunan, sonu — ən köhnə. get(key): map-dən node-u tap (O(1)), siyahıdan çıxar (O(1), prev sayəsində), başa köçür, dəyəri qaytar put(key, value): mövcuddursa dəyəri yenilə və başa köçür; yenidirsə node yarat, başa əlavə et, map-ə yaz; tutum aşılıbsa tail.prev-i çıxar və map-dən də sil 4. Detallar — bunlar səni fərqləndirir: iki sentinel node (head və tail) bütün null xüsusi hallarını aradan qaldırır; map-dən silərkən node-un key-ini saxlamaq lazımdır (buna görə node həm key, həm value saxlayır); capacity = 0 halını nəzərə al. Sonda əlavə et: "Real layihədə hazır həll seçərdim — Java-da LinkedHashMap accessOrder = true ilə, Kotlin/Android-də LruCache. Amma müsahibədə əl ilə yazmaq gözlənilir." Bu, praktik yetkinlik siqnalıdır. Thread-safe variant tələb olunursa, kilid və ya konkurrent struktur lazım olduğunu qeyd et.

Question 3

Circular linked list harada istifadə olunur və hansı tələsi var?

Accepted Answer

Əvvəlcə strukturu bir cümlə ilə təsvir et: sonuncu node null əvəzinə head-ə istinad edir; doubly circular-da isə head.prev tail-ə baxır. Real istifadə sahələri — konkret nümunələr nəzəri təsvirdən qat-qat effektlidir: Round-robin planlaşdırma — əməliyyat sistemində proseslərə növbə ilə vaxt ayırmaq; current = current.next və heç vaxt sona çatmırsan Media playlist / karusel — "repeat all" rejimi təbii alınır Oyunlarda növbə sırası — masa arxasında oyunçular dövrə ilə növbə alır Circular buffer məntiqi — sabit ölçülü loq və ya sensor datası Josephus problemi kimi klassik alqoritmik məsələlər Əsas tələ: gəzinti təbii şəkildə dayanmır. while (cur != null) sonsuz dövrədir, çünki heç bir next null deyil. Dayanma şərti mütləq başlanğıca qayıtma yoxlaması olmalıdır: do { ... } while (cur !== start). Eyni səbəbdən toString, length hesablama, hətta debugger-də obyektə baxmaq belə diqqət tələb edir. İkinci tələ: silmə zamanı siyahının tək node qaldığı hal — node.next === node — ayrıca işlənməlidir, əks halda struktur pozulur. Üstünlüyünü də de: null olmadığı üçün sərhəd halları azalır və hər node-dan bütün siyahıya çıxış var — bu, kodu bəzən singly-dən sadə edir.

Question 4

Undo/redo funksionallığını necə dizayn edərsən?

Accepted Answer

İki yanaşmanı təqdim et və seçimini əsaslandır — dizayn suallarında gözlənilən budur. Yanaşma 1 — iki stack: undoStack və redoStack. Yeni əməliyyat: undoStack-a push et, redoStack-ı təmizlə. Undo: undoStack-dan pop, tətbiq et, redoStack-a push. Redo: əksi. Sadə, O(1), əksər hallarda kifayətdir. Yanaşma 2 — doubly linked list: hər node bir vəziyyət və ya əməliyyatdır; current pointer indiki nöqtəni göstərir. Undo — current = current.prev, redo — current = current.next; yeni əməliyyat current-dən sonrakı zəncri kəsir. Bu, browser history ilə eyni modeldir. Nə vaxt ikincisi daha yaxşıdır: tarixçəni istifadəçiyə siyahı kimi göstərmək lazımdırsa (Photoshop-vari history paneli), və ya ixtiyari nöqtəyə tullanmaq imkanı istənirsə. İki stack ilə bu, əlavə iş tələb edir. Praktik detallar — cavabı istehsal səviyyəsinə qaldıran hissə: Command pattern: hər əməliyyat execute() və undo() metodları olan obyekt kimi saxlanılır — bu, tam vəziyyət nüsxəsi saxlamaqdan qat-qat yaddaş-səmərəlidir Yaddaş limiti: tarixçənin ölçüsünə hədd qoy, köhnə addımları at (burada da doubly siyahı O(1) sondan silmə verir) Qruplaşdırma: ardıcıl yazılan simvolları bir undo addımına birləşdirmək — istifadəçi gözləntisi belədir Böyük vəziyyətlər üçün: tam snapshot əvəzinə delta saxlamaq Yekun: "Sadə tətbiqdə iki stack seçərdim; tarixçə görünəndirsə və ya ixtiyari nöqtəyə keçid lazımdırsa, doubly linked list-ə keçərdim."

Question 5

Doubly linked list-də node silərkən hansı səhvlərə yol verilir və onları necə qarşısını alırsan?

Accepted Answer

Bu sual diqqətliliyi və istehsal təcrübəsini yoxlayır. Cavabı səhv → nəticə → qarşısının alınması formatında ver. Səhv 1 — yalnız bir istinadı yeniləmək. prev.next-i yeniləyib next.prev-i unutsan, siyahı irəli düzgün, geri pozuq qalır. Nəticə: səssiz korrupsiya, çox sonra qəribə davranış kimi üzə çıxır. Qarşısını almaq: silməni tək bir private metoda (unlink(node)) yığmaq və hər yerdə onu çağırmaq — iki sətir heç vaxt ayrılmır. Səhv 2 — sərhəd hallarını unutmaq. Head və ya tail silinəndə node.prev və ya node.next null olur və null.next xətası verir. Qarşısını almaq: sentinel node-lar — head və tail üçün boş node qoyanda hər real node-un həmişə qonşusu olur və şərtlər tamamilə itir. Səhv 3 — metadata-nı yeniləməmək. size azalmır, head/tail köhnə node-a baxmağa davam edir. Qarşısını almaq: eyni metod içində hamısını yeniləmək, testlərdə invariantları yoxlamaq. Səhv 4 — silinmiş node-un istinadlarını təmizləməmək. node.prev və node.next hələ də siyahıya baxırsa, node-a kənardan istinad qalıbsa, bütün siyahı GC-dən qorunub yaddaşda qala bilər. Qarşısını almaq: silmədən sonra node.prev = node.next = null. Səhv 5 — gəzinti zamanı silmək. Silmədən əvvəl next-i saxlamasan, gəzinti pozulur. Yekun praktikalar: invariantları yoxlayan test yaz (irəli və geri gəzinti eyni ardıcıllığı verməlidir, size real node sayına bərabər olmalıdır); mümkünsə hazır kitabxana strukturundan istifadə et — əl ilə yazılmış linked list istehsal kodunda nadir hallarda özünü doğruldur.

Əməliyyat	Singly	Doubly	Şərh
Başa əlavə/silmə	O(1)	O(1)	Hər ikisində ucuz
Sona əlavə (tail pointer ilə)	O(1)	O(1)	—
Sondan silmə	O(n)	O(1)	`prev` olduğu üçün doubly qazanır
Verilmiş node-u silmək	O(n)	O(1)	LRU cache-in bütün əsası budur
Geriyə gəzinti	Mümkün deyil (və ya O(n) əlavə iş)	O(n)	Browser history üçün vacibdir
Yaddaş (node başına)	1 pointer	2 pointer	Doubly ~təxminən 1.5-2x metadata
Səhv etmə riski	Aşağı	Yüksək — iki istinad sinxron qalmalıdır	Silmədə `prev`-i unutmaq klassik buqdur

Doubly və Circular Linked List

📚 Mənbələr və sənədlər