001
07.01.2008, 00:46 Uhr
0xdeadbeef
Gott
(Operator)
|
Bei einer einfach verketteten Liste musst du neben dem Element, das du löschen willst, noch das Element davor wissen, weil dessen next-Zeiger geändert werden muss. Außerdem musst du den Speicher wieder freigeben, und ein paar Spezialfälle beachten, für das Löschen am Ende bzw. Anfang, bzw. in einer fast leeren Liste, also:
| C++: |
if(tail == head) {
free(tail); // Hier wird ausgenutzt, dass free(NULL); nichts macht, im Fall einer leeren Liste.
tail = head = NULL;
} else if(current == head) {
head = current->next;
free(current);
} else if(current == tail) {
tail = current_prev;
current_prev->next = NULL; // wobei current_prev das vorherige Element ist
free(current);
} else {
current_prev->next = current->next;
free(current);
}
|
Außerdem musst du bei der Initialisierung noch den next-Zeiger des erstellten Elements auf NULL setzen. Vereinfachen lässt sich das mit einer doppelt verketteten Dummy-Liste, bei der head und tail unbenutzte Elemente sind, dann sieht das aus wie folgt:
| C++: |
struct list_node {
struct list_node *prev, *next;
};
struct list {
struct list_node *head, *tail;
size_t size;
};
void list_init(struct list *ls) {
ls->head = malloc(sizeof(struct list_node));
ls->tail = malloc(sizeof(struct list_node));
ls->head->prev = ls->head;
ls->head->next = ls->tail;
ls->tail->prev = ls->head;
ls->tail->next = ls->tail;
ls->size = 0;
}
void list_push(struct list *ls) {
struct list_node *new_node = malloc(sizeof(struct list_node));
new_node->next = ls->tail;
new_node->prev = ls->tail->prev;
ls->tail->prev->next = new_node;
ls->tail->prev = new_node;
++ls->size;
}
void list_remove(struct list *ls, struct list_node *node) {
assert(node != ls->head && node != ls->tail); // Die Dummies werden erst am Ende gelöscht
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
--ls->size;
}
struct list_node *list_get(struct list *ls, size_t index) {
size_t i;
struct list_node *result;
if(index > ls->size) {
return NULL;
}
result = head->next;
for(i = 0; i < index; ++i) {
result = result->next;
}
return result;
}
/* Die Liste zerstören */
void list_destroy(struct list *ls) {
/* Alle Elemente löschen */
while(ls->size > 0) {
list_remove(ls->head->next);
}
/* Dummies freigeben */
free(ls->head);
free(ls->tail);
}
|
Der Hintergrund ist, dass die Dummies dir so ziemlich alle Sonderfälle ersparen, weil für jedes Element sichergestellt ist, dass es ein nächstes und vorheriges gibt, so dass node->prev->next und node->next->prev immer da sind, und außerdem, dass head und tail nie geändert werden.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 07.01.2008 um 00:52 Uhr von 0xdeadbeef editiert. |
