Ancak, pointer'ları anlamak linked list nasıl çalıştığını anlamak için çok önemlidir. Pointer konusu ile ilgili kafanızda soru işaretleri varsa pointer ile ilgili yazımızı inceleyebilirsiniz.
Linked list'ler, dizideki herhangi bir noktadan gerektiği büyüyüp küçülebilen bir dizi işlevi görür.
Linked list'lerin dizilere göre bazı avantajları vardır:
1- Dizilerde eleman ekleme, silme gibi işlemler linked list'lere göre performans açısından daha maliyetlidir. Linked list'lerde ise bu işlem sadece basit bir pointer işlemi ile yapılır ve kaydırma işlemlerine ihtiyaç kalmaz. Bu sayede performanstan kazanç sağlanır.
2- Linked list'ler dinamik veri yapılarıdır. Dizi tanımlaması yapılırken en başta veri boyutunu belirtmemiz gerekirken, linked list'lerde ise bu boyutu eleman ekleme ile artırabilir, eleman silme işlemleri ile boyutu küçültebiliriz.
Linked list'lerin dezavantajları:
1- Rastgele erişim yoktur. Dizideki n'inci öğeye, o öğeye kadar tüm öğeler üzerinde yineleme yapılmadan ulaşmak imkansızdır. Bu, listenin en başından başlamamız ve istenen öğeye ulaşana kadar listede kaç kez ilerlediğinizi saymanız gerektiği anlamına gelir.
2- Linked list'ler sadece veriyi değil, veri ile birlikte bir sonraki düğüme işaret eden pointer'ları da tuttuğu için dizilere göre hafızada daha fazla yer kaplar
Linked List (Bağlı Listeler) Nedir?
Bağlı liste, her node (düğüm) bir değer ve bir işaretçi içeren, dinamik olarak ayrılmış düğümler kümesidir. Pointer her zaman listenin bir sonraki üyesini işaret eder. Pointer NULL ise, listedeki son düğümdür.
Kısaca şöyle diyebiliriz; bağlı liste içerisinde bellek üzerinde tanımlanan elemanlar pointer yardımı ile birbirini takıp eden vagonlar gibi çalışır. Kendinden sonraki gelecek olan düğümün adresini tutar. Bu sayede, her düğüm kendinden sonraki gelecek olan düğümün yerini bilir. Bu özellikleri sayesinde, bellekte sıralanış şekli açısından esneklik sağlar.
Linked List Türleri
Simple Linked List: Bu tür linked list'de, listeyi yalnızca bir yönde hareket edebilir veya hareket ettirebilirsiniz.
Doubly Linked List: Bu tür linked list'de, listeyi her iki yönde de hareket ettirebilir veya çaprazlanabilir(ileri ve geri).
Circular Linked List: Bu tür linked list'de, bağlantılı listenin son düğümü, bir sonraki işaretçisinde bağlantılı listenin ilk/baş düğümünün bağlantısını içerir ve ilk/baş düğüm, bağlı listenin son düğümünün bağlantısını kendi içinde içerir.
Linked List'lerin Temsili
Linked list, linked list'in ilk düğümüne bir işaretçi ile temsil edilir. İlk düğüm, linked list'in başı olarak adlandırılır. Linked list boşsa, başlığın değeri NULL'u gösterir.
Listedeki her düğüm en az iki bölümden oluşur:
- Bir veri öğesi(tamsayı, diziler veya herhangi bir veri türü).
- Bir sonraki düğüme işaretçi(veya referans)(bu düğümü diğerine bağlar) veya başka bir düğüm adresi.
C'de yapıları(structures) kullanarak bir düğümü temsil edebiliriz. Aşağıda tamsayı verileriyle bağlantılı bir liste düğümü örneği verilmiştir.
// bir linked list düğümü
struct Node{
int data;
struct Node* next;
};
3 düğümlü basit bit linked list'in oluşturulması:
#include <stdio.h>
#include <stdlib.h>
// bir linked list düğümü
struct Node{
int data;
struct Node* next;
};
int main() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// yığında 3 düğüm ayırmak
head = (struct Node*) malloc(sizeof (struct Node));
second = (struct Node*) malloc(sizeof (struct Node));
third =(struct Node*) malloc(sizeof (struct Node));
/* dinamik olarak 3 blok tahsis edilmiştir
* Bu üç bloğa head, second ve third olarak işaretçilerimiz var
*
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
Herhangi bir rastgele değeri temsil eder.
Veriler rastgele çünkü henüz bir şey atamadık.
*/
head->data = 1; // ilk düğüme değer atandı
head->next =second; // ilk düğümü, ikinci düğüme bağladık
/* veriler, ilk bloğun data kısmına atanmıştır.
* ve bloğun sonraki işaretçisi ikinciyi gösterir.
* yani ikisi de bağlı
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
second->data = 2; // ikinci düğüme değer atandı
second->next = third; // ikinci düğümü, üçüncü düğüme bağladık
/* veriler, ikinci bloğun data kısmına atanmıştır.
* ve ikinci bloğun bir işaretçisi üçüncü bloğa işaret eder.
* yani üç blok da birbirine bağlı.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+
*/
third->data =3; // üçüncü düğüme değer atandı
third->next = NULL;
/* veriler, üçüncü bloğun data kısmına atanmıştır.
* ve üçüncü bloğun bir sonraki işaretçisi,
* linked list'in burada bittiğini belirtmek için NULL yapılır.
*
* Linked list'imiz hazır
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
Tüm listeye temsil ulaşmak için yalnızca head'in yeterli olduğunu unutmayın.
*/
return 0;
}
Şimdi oluşturduğumuz listeyi dolaşalım ve her düğümün verilerini ekrana yazdıralım. Geçişler için ve düğüm verilerini yazdıran genel amaçlı bir printList() fonksiyonu yazalım.
#include <stdio.h>
#include <stdlib.h>
// bir linked list düğümü
struct Node{
int data;
struct Node* next;
};
// bu fonksiyon, verilen düğümden başlayarak linked list'in içeriğini yazdırır
void printList(struct Node* n){
while(n != NULL){
printf(" %d",n->data);
n = n->next;
}
}
int main() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// yığında 3 düğüm ayırmak
head = (struct Node*) malloc(sizeof (struct Node));
second = (struct Node*) malloc(sizeof (struct Node));
third =(struct Node*) malloc(sizeof (struct Node));
head->data = 1; // ilk düğüme değer atandı
head->next =second; // ilk düğümü, ikinci düğüme bağladık
second->data = 2; // ikinci düğüme değer atandı
second->next = third; // ikinci düğümü, üçüncü düğüme bağladık
third->data =3; // üçüncü düğüme değer atandı
third->next = NULL;
// fonksiyonu çağıralım
printList(head);
return 0;
}
Çıktı:
1 2 3
C programlama ile ilgili olan diğer konulara aşağıdaki linkten ulaşabilirsiniz:
Kaynaklar:
https://www.learn-c.org/en/Linked_lists
programiz.com/dsa/linked-list
https://www.edureka.co/blog/linked-list-n-c/
https://www.geeksforgeeks.org/linked-list-set-1-introduction/
https://www.studytonight.com/data-structures/linked-list-vs-array
