| ptrnl -NULL | 1 | ■ | ptrn2=NULL | ||||||||||
| ptrnl | info | ptrn2 | —•■ ■*— | ptrnl | info | ptrn2 | —* —»■ *— -*— | ptrnl | info | ptrn2 | |||
| . . | |||||||||||||
Рис. 2.4. Графическое представление двунаправленных связанных списков
Двунаправленные списки имеют следующее удобное свойство [11]: если р — указатель на элемент, то
left(right(p))=p=right(left(p)),
где right(p) — ссылка на адрес следующего элемента; ей(р) — ссылка на адрес предыдущего элемента.
Операция, которую можно выполнить над двунаправленным списком, но нельзя над обычным — это удаление элемента с заданным адресом.
Пример удаления элемент с заданным адресом/?#•
if( ptr == NULL )
printf("Удаление запрещено."); else
{
х = info(ptr); g = left(ptr); r = right(ptr); right(g) = r; left(r) = g; freenode(ptr);
Реализация списков на языке Си
1. Узел однонаправленного списка
| struct NODE | |
| { | |
| <тип> info; | |
| struct NODE | *ptrn; |
| }; |
2. Узел двунаправленного списка
| St { | ruct NODE | ||
| struct | NODE | *ptrnl; | |
| <тип> | info; | ||
| struct | NODE | *ptrn2; | |
| }; |
3. Указатель на список
struct NODE *lst; struct NODE *p;
4. Выделение блока оперативной памяти под узел
p=(struct NODE*)malloc( sizeof(struct NODE) );
5. Обращения к полям узла Однонаправленный список
p->ptrn=...; p->infо=...;
Двунаправленный список
| р- | ->ptrnl=. | • • г |
| р- | ->info=.. | • г |
| р- | ->ptrn2=. | • • г |