010
15.01.2008, 23:54 Uhr
0xdeadbeef
Gott
(Operator)
|
...und nach doppelt verketteten Listen dann doppelt verkettete Dummy-Listen.  Das sieht dann so aus:
| Code: |
------- head --------- ----- ----- ---------
| |----->| |--->| |--->| |--->| |--\
| | /--| dummy |<---| |<---| |<---| dummy | |
| | \->| | | | | | | |<-/
------- --------- ----- ----- ---------
| ^
| tail |
\--------------------------------------------/
|
Die Dummy-Elemente werden im Konstruktor erstellt, im Destruktor zerstört, und dazwischen nie wieder angefasst. Der Hintergrund ist, dass du keine Sonderfälle für Elemente am Anfang und am Ende beachten musst, weil immer garantiert ist, dass es ein nächstes und ein vorheriges Element gibt - auch wenn das eventuell ein Dummy ist. Vergleiche das Löschen eines Elements ohne Dummies:
| C++: |
if(head == tail) {
delete head;
head = tail = 0;
} else if(elem == head) {
head = elem->next;
head->prev = 0;
delete elem;
} else if(elem == tail) {
tail = elem->prev;
tail->next = NULL;
delete elem;
} else {
elem->next->prev = elem->prev;
elem->prev->next = elem->next;
delete elem;
}
|
und mit Dummies:
| C++: |
if(elem != head && elem != tail) {
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
delete elem;
}
|
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 15.01.2008 um 23:55 Uhr von 0xdeadbeef editiert. |
