Как создать обычный список мы уже разобрали, но как вы уже поняли "навигация" по такому списку не очень мобильна, и для того, чтобы работать с предыдущим элементом вам придется просмотреть весь список от начала.
Двусвязный список мало чем не отличается от односвязного, но у него появляется еще одна компонента, в которой хранится адрес предыдущего элемента.
Пример класса двусвязного списка:
class CTwoDirList { public: CTwoDirList(CTwoDirList *pr); int number; ~CTwoDirList(); CTwoDirList* Next; CTwoDirList* Prev; };
Пример списка:
Здесь представлена структура списка из трех элементов.
Полям Prev первого элемента и Next последнего обязательно надо присвоить значения NULL. Это убережет вас от случайного выхода за границу списка, и будет признаком его конца.
List в данном примере это указатель на первый элемент списка, хотя он может указывать на любой элемент, т.к. теперь вы можете спокойно двигаться по списку в любом направлении.
#include <stdio.h> #include <stdlib.h> class CTwoDirList { public: CTwoDirList(CTwoDirList *pr); int number; ~CTwoDirList(); CTwoDirList* Next; CTwoDirList* Prev; }; CTwoDirList::CTwoDirList(CTwoDirList *pr) { Next=NULL; Prev=pr; number=0; }; CTwoDirList::~CTwoDirList() { Prev->Next=Next; Next->Prev=Prev; }; void main() { CTwoDirList *List,*temp,*temp1,*temp2; List= new CTwoDirList(NULL); List->number=10; temp=List; for (int i=0;i < 10;i++) { temp->Next=new CTwoDirList(temp); temp=temp->Next; temp->number=i; }; temp=List; printf("\nList in -> direction:"); while (temp!=NULL) { printf(" %d ",temp->number); if (temp->Next==NULL) temp1=temp; temp=temp->Next; }; printf("\nList in <- direction:"); temp2=temp1; while (temp1!=NULL) { printf(" %d ",temp1->number); temp1=temp1->Prev; }; while (List!=NULL) { temp=List; List=List->Next; delete temp; }; };
Для вставки нового элемента в список надо выделить для него память (например оператором new) и связать с основным списком. Порядок вставки элемента необходимо обязательно четко понимать, иначе ваш список не будет выполнять своих функций, если он вообще будет работать. Вставкой нового элемента в конец списка занимается конструктор класса. Для этого ему сообщается адрес последней компоненты списка. Он присваевает адрес этой компоненты своему полю Prev, а полю Next присваивается значение NULL, которое является признаком конца списка. Если же вместо Next=NULL выполнить оператор:
Next=Prev->Next;
То вы сможете вставлять элемент в список не только в конце, но и в любом его месте. В этом случае конструктору придется сообщать адрес элемента, после которого надо вставить новый. Кстати заметьте, что это будет работать даже если вставлять элемент в конец, потому что Prev->Next в этом случае будет равен NULL и ошибки не произойдет.
Если же вы вставляете элемент первым в список, то не забудьте сохранить адрес этого элемента в переменной List, которая хранит адрес первого элемента.
Если вы запустите программу, то увидите следующее.
List in -> direction: 10 0 1 2 3 4 5 6 7 8 9 List in <- direction: 9 8 7 6 5 4 3 2 1 0 10
В первой строке список будет выводиться посредством связок Next, а во второй Prev. Т.е. Вам продемонстрируется его основная работа.
Почему удобно использовать для этих целей классы ? А потому, что классы имеют деструкторы, позволяющие перед уничтожением элемента подправить основной список. И само удаление теперь может быть в виде обычного delete, а не кодом в десятки строк, который следит за сохранностью связей в списке.