Tek bağlı liste

27 January 14, Monday @ 00:25

Tek bağlı liste (singly linked list), kolayca göz ardı edilebilecek basit gözüken bir veri yapısıdır. Aslında onu bir çeşit yönlü çizge (directed graph) olarak düşünmek daha doğru ve programlanmasında birçok ince nokta var. Belki de bu özelliğinden dolayı programcılara iş görüşmelerinde sık sık soruluyor. Bugüne kadar karşıma çıkan sorulardan bir derleme yaptım. Eleman ekleme gibi temel işlemler ya da tek bağlı listenin özelliklerinden bağımsız genel sorular yok. Eğlenceli ve öğretici olacağını tahmin ediyorum.

Çözerken (C dili için)

struct node {
    struct node *next;
    void *data;
}

gibi minimal bir şekilde tanımlanmış bir liste varsayabilirsiniz. Problemlerde istenen O(1) kabaca liste uzunluğundan bağımsız olarak sabit miktarda, O(N) ise listenin eleman sayısıyla orantılı bellek ya da işlem sayısını belirtiyor.

1. Verilen listede sondan k'ıncı (mesela beşinci) elemanı döndürebilir misiniz? İdeal çözüm O(1) bellek, O(N) işlem. Bu ısınma sorusuydu :)
2. Verilen listede dairesel bir döngü (bir eleman sonraki eleman olarak önceki elemanlardan birini gösteriyor) olup olmadığını bulun. O(1) bellek O(N) işlem. Bu çok sık sorulan bir soru.
3. İki tane liste veriliyor. Bu listelerin birleşip birleşmediğini, eğer birleşiyorlarsa sondan kaçıncı elemandan itibaren birleştiklerini bulun. O(1) bellek O(N) işlem.
4. Çift sayıda eleman içeren bir liste veriliyor. Listeyi bir eleman ilk yarısından bir eleman da ters yönde olmak üzere ikinci yarısından sıralanacak şekilde değiştirin. Örnek olarak eğer 1->2->3->4->5->6 listesi verilmişse bunu 1->6->2->5->3->4 haline getireceksiniz. Yine O(1) bellek O(N) işlem. Bu sorunun listeyi olduğu gibi ters çevirme ya da her k elemanı ters çevirme gibi değişik halleri sıklıkla soruluyor.
5. Dairesel (son elemanın bir sonraki eleman olarak ilk elemanı gösterdiği) bir listede, herhangi bir elemana ait bir işaretçi veriliyor. İşaretçinin gösterdiği elemanı listeyi bozmadan silebilir misiniz? Bellek kullanmadan ve O(1) işlemde!
6. Bir önceki sorunun çözümü dairesel olmayan bir listede çalışır mı? Hangi koşullarda çalışmaz?
7. Peki eğer node yapısına ek bir bilgi (ama işaretçi falan değil, o zaman çift yönlü listeye döner) koyarsak bu koşulları da çözebilir miyiz? Bellekte node yapısının kapladığı yeri büyütmeden bu bilgiyi koymanın bir yolu var mı?
8. Yine aynı soruda, işlem sayısı limitini kaldırırsak, dairesel olmayan liste için soruyu çözmek mümkün mü?

Sorularda anlaşılmayan yerler olursa yorumlarınızı bekliyorum. Tek bağlı listelerle ilgili yukardaki kriterlere uyan başka sorularınız varsa onları da yazın. Eğlenceli ve zorlu sorulara ödüllerimiz olabilir :D

Post a comment