Listeden silme
- C kursu
- Orta seviye
- Ders 73/116
- 5 dk
Bağlı listeden eleman silmeyi öğrenirsin.
Listeden silme
Silme, bir düğümü listeden koparıp belleğini iade etmektir. İki durum vardır: silinen düğüm başsa ya da ortada/sondasa.
Baş silinirken: Node *tmp = head; head = head->next; free(tmp);. Yeni baş, eski başın next'i olur. Ortada silinirken: bir prev imleci silinecek düğümün öncesinde durur; prev->next = cur->next; ile cur atlanır, sonra free(cur);. Önceki düğümün next'ini güncellemek, listedeki bağın kopmamasını sağlar. Silme işlemi O(n) olabilir çünkü value'yu bulmak için gezme gerekir.
list_remove işlevi
Tam bir silme işlevi iki dalı birleştirir. Önce head == NULL kontrolü yapılır; boş listede silinecek şey yoktur. Sonra başın değeri eşleşirse baş silinir.
Aksi halde prev ve cur çifti ile gezilir. cur->data == value bulunduğunda prev->next = cur->next; ile cur atlanır, free(cur); ile bellek iade edilir ve head döndürülür. Değer bulunamazsa liste değişmeden döndürülür. İşlev her zaman yeni başı döndürür; çağıran head = list_remove(head, 20); biçiminde geri almalıdır. Bu desen, başın değişme olasılığı nedeniyle gereklidir.
Uygulama 20'yi sil
Node *list_remove(Node *head, int value) yaz. head == NULL ise return NULL. head->data == value ise tmp = head; head = head->next; free(tmp); return head;. Değilse prev = head; cur = head->next; ile gez; cur->data == value bulunca prev->next = cur->next; free(cur); return head;. main'de 30, 20, 10 ekle; head = list_remove(head, 20);; list_print(head);; tüm düğümleri free et.
Başlangıç kodu
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *list_push_front(Node *head, int value) {
Node *n = malloc(sizeof(Node));
n->data = value;
n->next = head;
return n;
}
void list_print(Node *head) {
Node *cur = head;
while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; }
printf("\n");
}
// list_remove: value'yu bul ve sil; yeni başı döndür
// main: 30, 20, 10 ekle; 20'yi sil; list_print; tüm düğümleri free et
int main(void) {
// buraya yaz
return 0;
}Örnek çözüm
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *list_push_front(Node *head, int value) {
Node *n = malloc(sizeof(Node));
n->data = value;
n->next = head;
return n;
}
void list_print(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
Node *list_remove(Node *head, int value) {
if (head == NULL) return NULL;
if (head->data == value) {
Node *tmp = head;
head = head->next;
free(tmp);
return head;
}
Node *prev = head;
Node *cur = head->next;
while (cur != NULL) {
if (cur->data == value) {
prev->next = cur->next;
free(cur);
return head;
}
prev = cur;
cur = cur->next;
}
return head;
}
int main(void) {
Node *head = NULL;
head = list_push_front(head, 30);
head = list_push_front(head, 20);
head = list_push_front(head, 10);
head = list_remove(head, 20);
list_print(head);
while (head) { Node *t = head; head = head->next; free(t); }
return 0;
}Beklenen çıktı
10 30
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Ortadaki bir düğümü silerken ne güncellenir?
- cur->data
- prev->next Doğru cevap
- cur->next
- head->data
Açıklama: prev->next = cur->next ile cur atlanır.
2 Başı sil
Node *tmp = head; head = head->____; free(tmp);Node *tmp = head; head = head->next; free(tmp);Açıklama: head->next yeni baş olur.
3 Silme durumları
| Kavram | Anlamı |
|---|---|
boş liste |
return NULL |
baş eşleşir |
head = head->next |
orta eşleşir |
prev->next = cur->next |
bulunamaz |
return head |