VERİ YAPILARI : BAĞLI LİSTELER

Öncelikle standart dinamik bellek fonksiyonları ile konuya girmek istedim.

Standart Dinamik Bellek Fonksiyonları

malloc fonksiyonu içerisine yazılan byte kadar bellek alanını tahsis eder. Eğer ki bu alanı tahsis etmiş ise tahsis ettiği alanın başlangıç adresini verir. Eğer ki bu alanı tahsis edilmediyse 0 yani NULL değer döner.
Fonksiyon prototipi void *malloc(unsigned size) şeklindedir.

calloc, malloc’tan farklı olarak 2 parametrelidir ve tahsis ettiği alanı sıfırlar. Bu fonksiyonun ilk parametresinde belirtilen sayı ile 2. parametresindeki sayı çarpılır ve o boyutta bir alan tahsis edilir. Örneğin 10 adet char türünden veri tutacak alan tahsis etmek istiyorsanız. p = calloc(10, sizeof(char)); şeklinde bir kod yazmanız gerekmektedir. Fonksiyon prototipi void *calloc(unsigned count, unsigned size); şeklindedir.

realloc ise daha önceden tahsis edilen bellek alanını büyütmek yada küçültmek için kullanılır. Fonksiyon prototipinden de anlaşılacağı gibi ilk parametre olarak mevcut bloğun başlangıç adresi, 2. parametre olarak ise yeni boyut girilir. Fonksiyon prototipi void *realloc(void *block, unsigned newsize);

free fonksiyonunun prototipi ile tahsis edilen alanı boşaltabiliriz. Fonksiyon prototipi void free(void *block) şeklindedir.


Bağlı Listeler

Bağlı listeler de diziler gibi doğrusal türden veri depolamak için kullanılabilirken her ikisinin de birbirine göre avantajları ve dezavantajları bulunmaktadır.

Bağlı listeler dinamiktir. Dolayısıyla eleman silme işlemi yaptığımızda ram’de gerçekten de yer açmış oluruz.
Dizilerdeki gibi sabit boyutlu değillerdir. Eleman sayısını önceden belirtme zorunluluğunu ortadan kaldırır.
Bağlı listelerde rastgele erişim(random access) söz konusu değildir. Bu durumda erişmek istediğimiz öğelere ilk düğümden başlayarak sırayla erişmemiz gerekir.
Listenin her öğesi için bir işaretçi(pointer) kullanıldığından fazladan bellek alanı gerektirir.

Bağlı listelerde düğümleri ifade eden bir yapı tanımlanır ve bu yapının içerisine sonraki düğümü işaret eden bir işaretçi kullanmamız gerekir.

struct Node {
    int data; // buraya çeşitli veriler gelebilir.
    struct Node* next;
};

geeksforgeeks te bulmuş olduğum aşağıdaki kod ve yorumları bağlı listeleri güzel bir şekilde açıklıyor


// A simple C program to introduce 
// a linked list 
#include <stdio.h> 
#include <stdlib.h> 
  
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
// Program to create a simple linked 
// list with 3 nodes 
int main() 
{ 
    struct Node* head = NULL; 
    struct Node* second = NULL; 
    struct Node* third = NULL; 
  
    // allocate 3 nodes in the heap 
    head = (struct Node*)malloc(sizeof(struct Node)); 
    second = (struct Node*)malloc(sizeof(struct Node)); 
    third = (struct Node*)malloc(sizeof(struct Node)); 
  
    /* Three blocks have been allocated dynamically.  
     We have pointers to these three blocks as head, 
     second and third      
       head           second           third 
        |                |               | 
        |                |               | 
    +---+-----+     +----+----+     +----+----+ 
    | #  | #  |     | #  | #  |     |  # |  # | 
    +---+-----+     +----+----+     +----+----+ 
     
   # represents any random value. 
   Data is random because we haven’t assigned  
   anything yet  */
  
    head->data = 1; // assign data in first node 
    head->next = second; // Link first node with 
    // the second node 
  
    /* data has been assigned to the data part of the first 
     block (block pointed by the head). And next 
     pointer of first block points to second.   
     So they both are linked. 
  
       head          second         third 
        |              |              | 
        |              |              | 
    +---+---+     +----+----+     +-----+----+ 
    | 1  | o----->| #  | #  |     |  #  | #  | 
    +---+---+     +----+----+     +-----+----+     
  */
  
    // assign data to second node 
    second->data = 2; 
  
    // Link second node with the third node 
    second->next = third; 
  
    /* data has been assigned to the data part of the second 
     block (block pointed by second). And next 
     pointer of the second block points to the third  
     block. So all three blocks are linked. 
    
       head         second         third 
        |             |             | 
        |             |             | 
    +---+---+     +---+---+     +----+----+ 
    | 1  | o----->| 2 | o-----> |  # |  # | 
    +---+---+     +---+---+     +----+----+      */
  
    third->data = 3; // assign data to third node 
    third->next = NULL; 
  
    /* data has been assigned to data part of third 
    block (block pointed by third). And next pointer 
    of the third block is made NULL to indicate 
    that the linked list is terminated here. 
  
     We have the linked list ready.   
  
           head     
             | 
             |  
        +---+---+     +---+---+       +----+------+ 
        | 1  | o----->|  2  | o-----> |  3 | NULL | 
        +---+---+     +---+---+       +----+------+        
     
      
    Note that only head is sufficient to represent  
    the whole list.  We can traverse the complete  
    list by following next pointers.    */
  
    return 0; 
} 

Devam edecek…

Bu konuda ki yazıma ileride devam edeceğim fakat bu alanda çalışma yapmak isteyen kişiler için linkedinde karşılaşmış olduğum birşeyi sizlerle paylaşmak istiyorum.

Bağlı listeler konusunu kafanızda canlandırmakta zorluk çekiyorsanız veya çekmeseniz bile bu veri yapılarını görselleştirmek için https://github.com/hediet/vscode-debug-visualizer linkteki eklentiyi kullanabilirsiniz. Henüz kullanma fırsatım olmadı ama kullandığım zaman bununla ilgili de bir yazı yazmayı planlıyorum.