Intrusive List: Kendi Container'ınıza Bağlı Yapılar Ekleme
Intrusive list, bir veri yapısının içine liste düğümünü doğrudan gömme tekniğidir. Klasik bağlı liste her eleman için ayrı bir düğüm nesnesi oluştururken, intrusive list'te düğüm verinin kendisinin parçasıdır. Bu sayede bellek parçalanması azalır ve cache vurma oranı artar.
Sorun şöyle: standart bir bağlı listede, her öğe için heap'ten ayrı bellek tahsis edersiniz. Verinin kendisi bir yerde, düğümün next/prev işaretçileri başka yerde bulunur. Bu pointer indirlemesi ve bellek sıçramaları performansı düşürür. Intrusive list'te ise düğümün tüm bilgisi (next, prev) doğrudan veri yapısının içinde yer alır.
Burada pratik bir örnek: bir oyun karakteri listesini yönetiyorsunuz. Her karakterin sağlığı, konumu ve liste düğümü bilgisi aynı bellek bloğunda.
1#include <stdio.h>2#include <stdlib.h>34typedef struct {5int id;6int health;7struct node *next;8struct node *prev;9} Character;1011typedef struct {12Character *head;13Character *tail;14} CharacterList;1516CharacterList* create_list() {17CharacterList *list = malloc(sizeof(CharacterList));18list->head = NULL;19list->tail = NULL;20return list;21}2223void add_character(CharacterList *list, int id, int health) {24Character *ch = malloc(sizeof(Character));25ch->id = id;26ch->health = health;27ch->next = NULL;28ch->prev = list->tail;2930if (list->tail) {31list->tail->next = ch;32} else {33list->head = ch;34}35list->tail = ch;36}3738void print_list(CharacterList *list) {39for (Character *ch = list->head; ch; ch = ch->next) {40printf("Karakter %d - Saglik: %d\n", ch->id, ch->health);41}42}4344void remove_character(CharacterList *list, Character *ch) {45if (ch->prev) ch->prev->next = ch->next;46else list->head = ch->next;4748if (ch->next) ch->next->prev = ch->prev;49else list->tail = ch->prev;5051free(ch);52}5354int main() {55CharacterList *list = create_list();56add_character(list, 1, 100);57add_character(list, 2, 80);58add_character(list, 3, 120);5960print_list(list);6162return 0;63}Beklenen çıktı:
1Karakter 1 - Saglik: 1002Karakter 2 - Saglik: 803Karakter 3 - Saglik: 120Burada Character yapısı kendi düğüm bilgisini (next, prev) taşır. Listeye eklediğinizde, ayrı bir düğüm nesnesi oluşturmanız gerekmez. Bellek daha kompakt ve erişim daha hızlı olur.
Sık yapılan hata: düğüm işaretçilerini yönetirken NULL kontrolü atlamak. Özellikle remove işleminde head ve tail durumlarını iyi kontrol etmelisiniz. Aksi takdirde dangling pointer'larla karşılaşırsınız.
0 yorum