Двусвязный список. Реализация на C

Ранее я писал о том, что такое односвязный линейный список (ОЛС). Однако на практике часто вместо односвязных списков используются так называемые двусвязные линейные списки (ДЛС), о чем и пойдет речь в данной статье. Зачастую использовать ДЛС намного удобнее, правда не всегда. Для таких списков требуется больше памяти, чем для односвязных (в чем мы вскоре убедимся). Так что, если в памяти Вы не ограничены, можете спокойно использовать ДЛС для своих нужд.

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

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

Так как каждый элемент списка содержит, помимо поля с данными, два указателя, то отсюда вытекает то, что для ДЛС требуется больше памяти.

Использование двух указателей дает несколько преимуществ. Самым главным из которых является то, что перемещаться по списку можно в двух направлениях, благодаря чему упрощаются некоторые операции (по сравнению с ОЛС) и добавляются новые.

Операции над ДЛС

  1. Инициализация
  2. Включение до рабочего указателя
  3. Включение после рабочего указателя
  4. Исключение до рабочего указателя
  5. Исключение после рабочего указателя
  6. Сдвиг рабочего указателя назад (к предыдущему элементу)
  7. Сдвиг рабочего указателя вперед (к следующему элементу)
  8. Установка рабочего указателя в начало списка
  9. Установка рабочего указателя в конец списка
  10. Проверка пустоты списка
  11. Удаление списка

Реализация двусвязного списка

Как и с односвязным списком, в статической памяти будет располагаться дескриптор. Этот дескриптор будет в точности таким же, как и у ОЛС. Единственное отличие — два указателя.

/*Базовый тип списка*/
typedef int listTwoBaseType;
/*Структура элемента списка*/
struct elementTwo {
listTwoBaseType data;		// Данные
elementTwo *predLink;		// Указатель на предыдущий элемент
elementTwo *nextLink;		// Указатель на следующий элемент
};
/*Дескриптор списка*/
typedef struct {
elementTwo *Start;			// Указатель на левый фиктивный элемент
elementTwo *End;			// Указатель на правый фиктивный элемент
elementTwo *ptr;			// Рабочий указатель
} ListTwo;

Инициализация списка

Суть инициализации состоит в том, чтобы создать фиктивные элементы, то есть выделить для них память. Интерес вызывает то, что эти указатели должны указывать друг на друга.

/*Инициализация списка*/
void initListTwo(ListTwo *L) {
// Выделение памяти для левого фиктивного элемента
L->Start = (elementTwo *) malloc(sizeof(elementTwo));
/*Если памяти не достаточно*/
if (!L->Start) {
listTwoError = listTwoNoMem;
return;
}
/*Иначе*/
// Выделение памяти для правого фиктивного элемента
L->End = (elementTwo *) malloc(sizeof(elementTwo));
/*Если памяти не достаточно*/
if (!L->End) {
listTwoError = listTwoNoMem;
free((void *) L->Start);			// Удаление левого фиктивного элемента
L->Start = NULL;
return;
}
/*Иначе*/
// Элемент, следующий за левым фиктивным -- правый фиктивный эл-т
L->Start->nextLink = L->End;
// Элемента, предшествующего левому фиктивному эл-ту нет
L->Start->predLink = NULL;
// Элемента, следующего за правым фиктивным эл-том нет
L->End->nextLink = NULL;
// Элемент, предшествующий правому фиктивному -- левый фиктивный эл-т
L->End->predLink = L->Start;
// Рабочий указатель и левый фиктивный эл-т указывают на одно и то же
L->ptr = L->Start;
/*Все в порядке*/
listTwoError = listTwoOk;
}

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

Готовый список

Файл "List_Two.h"

/****************************************/
/*			Двусвязный список			*/
/****************************************/
#ifndef _LIST_TWO_H_
#define _LIST_TWO_H_
/*Описание исключительных ситуаций*/
const int listTwoOk = 0;				// Все впорядке
const int listTwoEmpty = 1;				// Список пуст
const int listTwoNoMem = 2;				// Недостаточно памяти
const int listTwoEnd = 3;				// Указатель в конце
const int listTwoBegin = 4;				// Указатель в начале
/**********************************/
/*Переменная ошибок*/
extern int listTwoError;
/*Базовый тип списка*/
typedef int listTwoBaseType;
/*Структура элемента списка*/
struct elementTwo {
listTwoBaseType data;		// Данные
elementTwo *predLink;		// Указатель на предыдущий элемент
elementTwo *nextLink;		// Указатель на следующий элемент
};
/*Дескриптор списка*/
typedef struct {
elementTwo *Start;			// Указатель на левый фиктивный элемент
elementTwo *End;			// Указатель на правый фиктивный элемент
elementTwo *ptr;			// Рабочий указатель
} ListTwo;
/*Функции работы со списком*/
void initListTwo(ListTwo *L);					// Инициализация списка
void predPut(ListTwo *L, listTwoBaseType E);	// Включение до рабочего указателя
void postPut(ListTwo *L, listTwoBaseType E);	// Включение после рабочего указателя
void predGet(ListTwo *L, listTwoBaseType *E);	// Исключение до рабочего указателя
void postGet(ListTwo *L, listTwoBaseType *E);	// Исключение после рабочего указателя
void movePtrListTwoLeft(ListTwo *L);			// Сдвиг рабочего указателя назад
void movePtrListTwoRight(ListTwo *L);			// Сдвиг рабочего указателя вперед
void beginPtrListTwo(ListTwo *L);				// Установить рабочий указатель в начало
void endPtrListTwo(ListTwo *L);					// Установить рабочий указатель в конец
void doneListTwo(ListTwo *L);					// Удаление списка
int isEmptyListTwo(ListTwo *L);					// Предикат: пуст ли список
/***************************/
#endif

Файл "List_Two.с"

/****************************************/
/*			Двусвязный список			*/
/****************************************/
#include <stdio.h>
#include <stdlib.h>
#include "List_Two.h"
/*Переменная ошибок*/
int listTwoError;
/*Инициализация списка*/
void initListTwo(ListTwo *L) {
// Выделение памяти для левого фиктивного элемента
L->Start = (elementTwo *) malloc(sizeof(elementTwo));
/*Если памяти не достаточно*/
if (!L->Start) {
listTwoError = listTwoNoMem;
return;
}
/*Иначе*/
// Выделение памяти для правого фиктивного элемента
L->End = (elementTwo *) malloc(sizeof(elementTwo));
/*Если памяти не достаточно*/
if (!L->End) {
listTwoError = listTwoNoMem;
free((void *) L->Start);			// Удаление левого фиктивного элемента
L->Start = NULL;
return;
}
/*Иначе*/
// Элемент, следующий за левым фиктивным -- правый фиктивный эл-т
L->Start->nextLink = L->End;
// Элемента, предшествующего левому фиктивному эл-ту нет
L->Start->predLink = NULL;
// Элемента, следующего за правым фиктивным эл-том нет
L->End->nextLink = NULL;
// Элемент, предшествующий правому фиктивному -- левый фиктивный эл-т
L->End->predLink = L->Start;
// Рабочий указатель и левый фиктивный эл-т указывают на одно и то же
L->ptr = L->Start;
/*Все в порядке*/
listTwoError = listTwoOk;
}
/*Включение до рабочего указателя*/
void predPut(ListTwo *L, listTwoBaseType E) {
/*Если рабочий указатель установлен на начало*/
if (L->ptr == L->Start) {
listTwoError = listTwoBegin;
return;
}
/*Иначе*/
elementTwo *pntr = (elementTwo *) malloc(sizeof(elementTwo));		// Выделение памяти под новый элемент
/*Если памяти не достаточно*/
if (!pntr) {
listTwoError = listTwoNoMem;
return;
}
/*Иначе*/
pntr->data = E;							// Запись информации в новый элемент
pntr->predLink = L->ptr->predLink;		// Новый эл-т указывает слева на предыдущий
pntr->nextLink = L->ptr;				// Новый эл-т указывает справа на текущий
L->ptr->predLink->nextLink = pntr;		// Предыдущий эл-т указывает справа на новый
L->ptr->predLink = pntr;				// Текущий эл-т указывает слева на новый
}
/*Включение после рабочего указателя*/
void postPut(ListTwo *L, listTwoBaseType E) {
/*Если рабочий указатель установлен в конец*/
if (L->ptr == L->End) {
listTwoError = listTwoEnd;
return;
}
/*Иначе*/
// Выделение памяти под новый элемент
elementTwo *pntr = (elementTwo *) malloc(sizeof(elementTwo));
/*Если памяти не достаточно*/
if (!pntr) {
listTwoError = listTwoNoMem;
return;
}
/*Иначе*/
pntr->data = E;							// Запись информации в новый элемент
pntr->nextLink = L->ptr->nextLink;		// Новый эл-т указывает справа на следующий
pntr->predLink = L->ptr;				// Новый эл-т указывает слева на текущий
L->ptr->nextLink->predLink = pntr;		// Следующий эл-т указывает слева на новый
L->ptr->nextLink = pntr;				// Текущий эл-т указывает справа на новый
}
/*Исключение до рабочего указателя*/
void predGet(ListTwo *L, listTwoBaseType *E) {
/*Если список пуст*/
if (isEmptyListTwo(L)) {
return;
}
/*Иначе*/
/*Если рабочий указатель указывает на начало (левый фиктивный эл-т)*/
if (L->ptr == L->Start) {
listTwoError = listTwoBegin;
return;
}
/*Иначе*/
*E = L->ptr->predLink->data;			// Запись информации в переменную
elementTwo *pntr = L->ptr->predLink;	// Временный эл-т, указывающий на удаляемый
L->ptr->predLink = pntr->predLink;		// Текущий эл-т указывает на предшествующий удаляемому
pntr->predLink->nextLink = L->ptr;		// Предшествующий удаляемому эл-т указывает на текущий
free((void *) pntr);					// Удаление временного элемента
}
/*Исключение после рабочего указателя*/
void postGet(ListTwo *L, listTwoBaseType *E) {
/*Если список пуст*/
if (isEmptyListTwo(L)) {
return;
}
/*Иначе*/
/*Если рабочий указатель указывает на конец (правый фиктивный эл-т)*/
if (L->ptr == L->End) {
listTwoError = listTwoEnd;
return;
}
/*Иначе*/
*E = L->ptr->nextLink->data;			// Запись информации в переменную
elementTwo *pntr = L->ptr->nextLink;	// Временный эл-т, указывающий на удаляемый
L->ptr->nextLink= pntr->nextLink;		// Текущий эл-т указывает на следующий за удаляемым
pntr->nextLink->predLink = L->ptr;		// Следующий за удаляемым эл-т указывает на текущий
free((void *) pntr);					// Удаление временного элемента
}
/*Сдвиг рабочего указателя назад*/
void movePtrListTwoLeft(ListTwo *L) {
/*Если рабочий указатель указывает на начало*/
if (L->ptr == L->Start) {
listTwoError = listTwoBegin;
return;
}
/*Иначе смещение указателя*/
L->ptr = L->ptr->predLink;
}
/*Сдвиг рабочего указателя вперед*/
void movePtrListTwoRight(ListTwo *L) {
/*Если рабочий указатель указывает на конец списка*/
if (L->ptr == L->End) {
listTwoError = listTwoEnd;
return;
}
/*Иначе смещение указателя*/
L->ptr = L->ptr->nextLink;
}
/*Установить рабочий указатель в начало*/
void beginPtrListTwo(ListTwo *L) {
while (L->ptr != L->Start) {
movePtrListTwoLeft(L);
}
}
/*Установить рабочий указатель в конец*/
void endPtrListTwo(ListTwo *L) {
while (L->ptr != L->End) {
movePtrListTwoRight(L);
}
}
/*Удаление списка*/
void doneListTwo(ListTwo *L) {
beginPtrListTwo(L);				// Установка рабочего указателя в начало
listTwoBaseType E;				// Создание временного элемента
while (!isEmptyListTwo(L)) {	// Пока список не пуст
postGet(L, &E);				// Извлечь элемент
}
/*Удаление фиктивных элементов*/
free((void *) L->Start);
free((void *) L->End);
}
/*Предикат: пуст ли список*/
int isEmptyListTwo(ListTwo *L) {
if (L->Start->nextLink == L->End) {
listTwoError = listTwoEmpty;
return 1;
}
return 0;
}

Вот и все! Надеюсь все было доступно изложено. Если возникнут вопросы, Вы можете задать их в комментариях в конце статьи. Удачи!

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *