Шаг 3 - Двусвязный список

Как создать обычный список мы уже разобрали, но как вы уже поняли "навигация" по такому списку не очень мобильна, и для того, чтобы работать с предыдущим элементом вам придется просмотреть весь список от начала.

Двусвязный список мало чем не отличается от односвязного, но у него появляется еще одна компонента, в которой хранится адрес предыдущего элемента.

Пример класса двусвязного списка:

class CTwoDirList
{
public:
	CTwoDirList(CTwoDirList *pr);
	int number;
	~CTwoDirList();
	CTwoDirList* Next;
	CTwoDirList* Prev;
};

Пример списка:

3_1.gif (1174 b)

Здесь представлена структура списка из трех элементов.

Полям 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, а не кодом в десятки строк, который следит за сохранностью связей в списке.


Предыдущий Шаг | Следующий Шаг | Оглавление
Автор Кузин Андрей.