NEDİR BU VERİ YAPILARI(DATA STRUCTURES)?
Bilgisayar bilimi alanında herkesin; Aley(şahsım) bunu mutlaka iyi öğren, aman atlama , bol bol kod yaz(there is no free lunch 😜), mantığı öğren ezberleme sakın dediği sahadayız…
FIFO, LIFO, algorithm,RAM neymiş bu dequeueue….
Açıkcası basit anlatımla ve olabildiğince özet şekilde anlatmaya çalışacağım.
Tabi başlamadan önce bazı gerekli ön bilgiler lazım ben dersi C dilinde aldığım için C dilinin syntaxine hakim olmamız lazım…
Görüşümce güçlü Struct ve Pointer bilgisi de ekstra gerekli.
Veriyi her zaman dizide düzenli şekilde tutamıyoruz.(Ah keşke tutabilsek).Zamanla kendi verilerimizi tutabileceğimiz yapılar ortaya çıkmış bunlara da abstract data types(soyut veri tipleri) denmiş.
ADT(ABSTRACT DATA TYPES) SOYUT VERİ YAPILARI
- Yazılmcı/programcı tarafından oluşturulmuş veri tipleridir.(Just Imagine That 💩)
PEKİ NEDEN İHTİYAÇ VAR BU VERİ YAPILARINA?
Lafın özü karmaşık yapıları açıklayabilmek. 💃
Peki veri veri diyoruz ya nerde bu veriler (RAM’de).
ADT ÖRNEKLERİ
- Diziler
- Listeler
- Stack
- Queue
O zaman ilk veri yapımıza gelelimmm. Bilgisayar biliminden soğumaya hazır olun!!! 😝
BAĞLI LİSTE(LINKED LIST)
- Veri saklamanın yollarından biridir.
- Kendisi vazgeçilemez bir Abstract Data Type.
- Her veri kendisinden sonra gelen veriyi işaret etmek zorundadır.(İyi pointer bilgisi lazım demiştik değil mi?)
Data + Next = Node
Yani her data ve next bir düğüm(şu meşhur NODE) demektir.
İlk düğüme HEAD adını verirken son düğüme TAIL adını veriyoruz.
Ve mutlaka son düğümün pointerı(yukarıdaki şekilde son next oluyor)NULL’u işaret ediyor ve böylece son düğümün o olduğunu kolayca(!) anlayabiliyoruz.
BAĞLI LİSTE ÇEŞİTLERİ
Üzgünüm ama gerçekten çeşit çeşitler….
1-)Tek yönlü bağlı liste(Singly Linked List)
2-)Çift yönlü bağlı liste(Doubly linked List)
3-)Dairesel bağlı liste(Circular Linked List)
Gördüğünüz üzere yanarlı dönerli, şekilli şukullu bol bol liste var…
BAĞLI LİSTELERLE NELER YAPABİLİYORUZ ?
Neler yapamıyoruz ki :)
- Traverse (her türlü halı, kilim, travel 😝)
- Eleman ekleme
- Eleman silme
- Eleman yazdırma
- Sort işlemleri
Neden Bağlı Listeyi Tercih Ediyoruz?
- Dinamik yapılıdır.(Sonradan eleman ekle çıkar kafana göre takıl .(dizide zor çok zor öyle böyle değil zor..))
- Eleman ekleme, silme işlemleri kolaydır.
Neden Bağlı Listeyi Tercih Etmiyoruz ?
- Random erişemeyiz.
- Hafızayı fazladan kullanabilir.
“If you lost head, you lost the list..” (Çevirisi geçmiş olsun 😞)
Bağlı Liste Oluşturma
1-)Düğümü hazırda tut.
2-)Düğümde iki farklı veri tutulacağı için STRUCT yapısı ile düğümü oluştururuz. (bir int tipinde değişken bir de pointer tipinde değişken. Ne demiştik yukarıda NODE=data+next )
3-)Düğümlerin için RAM’inde yer ayır.(mutlaka ayır)
nasıl mı ayırıyoruz?
malloc fonksiyonu ile dinamik bellek yönetimine yardımcı olur
malloc= memory allocation
Örneğin;
head = (struct node*)malloc(sizeof(struct node);Düğüm Oluşturma
Linked List Oluşturma
Linked List Traverse
(Her türlü halı, kilim, travel 😜)
- Veri yapısında aranılan noktayı(düğümü) bulmamızı hedefler.
Adım Adım Traverse
- İlk düğümü geçici düğüme eşitle.
- İşaret edilen düğümü bul.
- Geçici düğümü işaret edilen düğüme eşitle.
Tek Yönlü(Singly)Linked List Sona Eleman Ekleme
- Traverse işlemi ile son düğüm bulunur.Düğümün pointer değişkeni NULL olmalıdır.(Böylelikle son düğüm olduğunu kanıtlarız.)
- Bulunan düğüm geri döndürülür.Bulunan düğümün pointer değişkenine eklenecek olan düğüm atanır.
Kısaca
- Son düğüm bul.
- Son düğümün pointer değişkenine yeni düğümü ata.
- Yeni düğümün pointer değişkenine null değerini ata.
KODU
Tek Yönlü (Singly) Linked List Başa Eleman Ekleme
Yeni eklenecek eleman için düğüm oluşturulur eklemeden önce ise head elemanı ikinci eleman olur.Yeni düğümün linki head elemanına atanır.yeni düğüm head elemanı olarak güncellenir.
KODU
Tek Yönlü (Singly) Linked List Araya Eleman Ekleme
(Biliyorum çok karışık ama halledicez iki dk)
- Hangi elemanın önüne veya arkasına ekleyeceğimiz mutlaka belirtilmelidir.
- Şarta bağlı olarak traverse işlemini yaparız.
KODU
Tek Yönlü (Singly) Linked List Sondan Eleman Silme
(Çok eğlencesiz kısımlar şaka bile yapılmıyor gerçekten ama delete işlemi bi nebze daha çekilir gibi diye düşünüyorum.☹️)
- Sondan bir önceki düğümü bul.
- Bu düğümün link değeri free komutuyla hafızadan silinir.
- Düğümün next değerine NULL atanır.
KODU
Tek Yönlü (Singly) Linked List Baştan Eleman Silme
- Baştan eleman silinince ikinci eleman ilk eleman olur.
- İkinci elemanı bir değişkene aktarıyoruz.
- Head değerini free yapıyoruz.
- Elimizdeki değişkeni head elemanı olarak güncelliyoruz.
KODU
Tek Yönlü (Singly) Linked List Aradan Eleman Silme
- Aradan eleman silme için kullanıcıdan sayı bilgisi alınmalıdır
- Traverse işlemiyle sayının bulunduğu düğüm bulunmalıdır.
- Mantık olarak, sayının önceki bulunduğu düğüm sayının bulunduğu düğümden sonrasına atanmalıdır.
ÖZETLE;
1-)Silenecek düğümden önceki düğüm bulunur.
2-)Önceki düğüm prev değişkeninde saklanır
3-)Sonraki düğümü saklamak için prev.düğüm->next->next
4-)Yaparak atama işlemi gerçekleştiririz.
5-)C.prev’den sonraki düğümü free yapılır.
6-)prev->next=next yapılarak düğüm silinir.
KODU
Tek Yönlü (Singly) Linked List Elemanları Ters Çevirme(REVERSE)
En yaygın mülakat sorularından biriymiş öğrenmeden olmaz dedik…👩🏻💻
Neymiş bu reverse inceleyelim bakalım:
Öncelikle adı üstünde ters çevirme olduğu için ilk elemanımız son , son elemanımız ise ilk eleman olacaktır.
Ayrıca pointerların yönünü de ters çevirmek gerekecektir.
Bu soruyu iki şekilde çözebiliyoruz;birincisi ITERATIVE ikincisi RECURSIVE.
Iterative olanıyla başlayalım o zaman 💁🏻♀️
1-)Bir tane geçici düğüm oluşturulur.Bir tane de önceki elemanı tutmak için düğüm oluşturulup NULL değeri atanır.
2-)Head düğümünden itibaren traverse döngüsüne girilir.
3-)Traverse sürecinde geçici düğüm sürekli bir sonraki düğümdür.
4-)Mevcut durumdaki düğümden sonraki düğüme önceki düğüm atanır.
5-)Önceki düğüme de mevcut düğüm atanırç
6-)Traverse işlemi için mevcut düğümden sonrakine geçilir.
KODU
Çift Yönlü(Doubly)Linked List
Teki bitti çifti başladı….
Aslında olay genel mantığı kavramakla bitmiş oluyor… Boşuna dememiş atalarımız “Soruyu anlamak çözmenin yarısıdır”(Belki de lise hocalarımızın uydurması 🤪 atalar kısmından emin olamadım şuan.
- Başlangıç ve son düğümler NULL’ı işaret etmeli.
Çift Yönlü(Doubly)Linked List Sona Eleman Ekleme
Çift Yönlü (Doubly) Linked List Başa Eleman Ekleme
Çift Yönlü (Doubly) Linked List Araya Eleman Ekleme
Çift Yönlü(Doubly)Linked List Baştan Eleman Silme
Çift Yönlü(Doubly)Linked List Sondan Eleman Silme
Çift Yönlü(Doubly)Linked List Aradan Eleman Silme
Dairesel(Circular) Linked List
