Bağlı Liste(Linked List) Yapısı

Programlama dillerinde birden çok veriyi tutmak için genellikle dizileri kullanırız. Ancak dizileri kullanmak için verimizin boyutunu bilmemiz gerekir. Eğer bilmiyorsak ya da belirlediğimiz değerin üzerine çıkmak istiyorsak sıkıntı yaşarız. Yaşayacağımız bir diğer sıkıntı ise elimizdeki veri setinin arasına bir değer girmek istersek ortaya çıkar. Örneğin 500 elemanlı bir dizinin 300. elemanına dışarıdan başka bir değer girersek 300. elemandan sonraki değerleri birer kaydırmamız gerekir. İşte tüm bunları aşmak için bağlı liste(linked list) kullanabiliriz.

Bağlantılı liste kullanmanın avantaj ve dezavantajları;

• Dinamik boyuta sahip oluruz
• Araya eleman eklerken fazla maliyet oluşturmaz

• Rastgele erişim yoktur
• Pointer için fazladan alan kullanırız.

Linked list temel işlemlerimiz

• Ekle
• Sil
• Ara
• Bul
• Yok et

• Her bir elemanımıza düğüm(node) denir.
• Bağlanmış düğümler serisine bağlantılı liste denir.
• Her düğümde veri ve işaretçi bulunur.
• Baş; ilk düğüme olan işaretçidir.
• Son düğüm NULL işaret eder.

Şimdi implemente edelim

Öncelikle 2 ana sınıfımız olacak. Bunlar Node ve List

class Node {
public:
	double	data;		// data
	Node*	next;		// pointer
};

class List {
public:
	List(void) { head = NULL; }	// constructor
	~List(void);				// destructor

	bool IsEmpty() { return head == NULL; } //boş kontrolü
	Node* InsertNode(int index, double x);	//node ekle
	int FindNode(double x);	 //node bul
	int DeleteNode(double x); //node sil
	void DisplayList(void); //liste görüntüle
private:
	Node* head; //baş kısmı
};

Şimdi de InsertNode fonksiyonumuzu yazalım. Kabaca algoritması;

• index’inci elemanı bul
• Yeni düğüm için hafızada yer ayır
• Yeni düğüm kendisinden sonrasını gösterecek
• Yeni düğümden önceki düğüm yeni düğümü gösterecek

Yukarıdaki işlemleri yaparken 2 farklı durumla karşılaşırız.

• İlk düğüm olarak ekleme
• Ortaya ve sona ekleme

Node* List::InsertNode(int index, double x) {
	
	if (index < 0) return NULL;	
	
	int currIndex	=	1;
	Node* currNode	=	head;
	while (currNode && index > currIndex) {
		currNode	=	currNode->next;
		currIndex++;
	}
	if (index > 0 && currNode == NULL) return NULL;
	
	Node* newNode	=	new	Node;
	newNode->data	=	x;	
	if (index == 0) {
		newNode->next	=	head;
		head		=	newNode;
	}
	else{
		newNode->next	=	currNode->next;
		currNode->next	=	newNode;
	}
	return newNode;
}

FindNode fonskiyonumuz

• Listede x verisini ara
• Böyle bir düğüm varsa pozisyonunu dön yoksa 0 dön

int List::FindNode(double x) {
	Node* currNode	=	head;
	int currIndex	=	1;
	while (currNode && currNode->data != x) {
		currNode	=	currNode->next;
		currIndex++;
	}
	if (currNode) return currIndex;
	return 0;
}

DeleteNode fonksiyonu

• Silinecek düğümü bul
• Bulunan düğümü hafızadan sil
• Düğümden önceki pointer düğümden sonraki pointeri göstersin.

Ekleme işleminde olduğu gibi 2 özel durumumuz var.

• İlk düğümü silme
• Ortadaki veya sonraki düğümü silme

int List::DeleteNode(double x) {
	Node* prevNode	=	NULL;
	Node* currNode	=	head;
	int currIndex	=	1;
	while (currNode && currNode->data != x) {
		prevNode	=	currNode;
		currNode	=	currNode->next;
		currIndex++;
	}
	if (currNode) {
		if (prevNode) {
			prevNode->next	=	currNode->next;
			delete currNode;
		}
		else {
			head		=	currNode->next;
			delete currNode;
		}
		return currIndex;
	}
	return 0;
}

Listedeki elemanları ve eleman sayısını yazdırma

void List::DisplayList()
{
   int num		=	0;
   Node* currNode	=	head;
   while (currNode != NULL)
   {
   	printf("%lf\n",currNode->data);

	currNode	=	currNode->next;
	num++;
   }
   printf("\nNumber of nodes in the list: %d",num);
}

Listeyi silme

List::~List(void) {
   Node* currNode = head, *nextNode = NULL;
   while (currNode != NULL)
   {
	nextNode	=	currNode->next;
	// destroy the current node
	delete currNode;	
	currNode	=	nextNode;
   }
}

Örnek işlemler

int main(int argc, char** argv) {
	
	List list;
	list.InsertNode(0,5.4); //başarılı
	list.InsertNode(1,6.5); //başarılı
	list.InsertNode(-2,5.5);//başarsız
	list.InsertNode(2,10.0);//başarılı
	list.DisplayList();
	list.DeleteNode(5.4);
	list.DisplayList();
	return 0;
}

Projeyi buradan indirebilirsiniz