Двусвязный список и его программная реализация.

Ранее рассмотрен односвязный список, в котором легко найти следующий элемент, но вернуться на предыдущий – достаточно трудно. Его легко пройти, начиная от головы, но совершенно невозможно «против шерсти», в обратном порядке.

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

Рис. 8. Организация двусвязного списка

Рассмотрим схемы реализации некоторых операций для двусвязного списка.

1. Удаление элемента

Рис. 9. Удаление элемента двусвязного списка

2. Вставка элемента

Рис. 10. Вставка элемента в двусвязный список

#ifndef LISTS2_

#define LISTS2_

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <conio.h>

//////////////////////////////////////////////////////

// Элемент списка

//////////////////////////////////////////////////////

typedef struct

{

char name[20]; // Информация

void *next; // Указатель на следующий блок

void *prev; // Указатель на предыдущий блок

} LIST2, *pLIST2;

//////////////////////////////////////////////////////

// Добавить в конец списка новый элемент

pLIST2 AddToLists2(pNAME pInf);

// Добавить в список после заданного элемента

pLIST2 AddToLists2Elem(char* pName, char* pNewName);

// Добавить в список перед заданным элементом

pLIST2 AddToLists2Elem(char* pName, char* pNewName);

// Удалить из списка заданный элемент (первый, если pName==NULL)

pLIST2 DelFromLists2(char* pName);

// Вывести содержание списка

void PrintLists2(void);

//////////////////////////////////////////////////////

extern pLIST2 pHead;

#endif //LISTS2_

Кольцевые списки

Если замкнуть связь «вперед» последнего блока на первый блок списка, а связь «назад» первого блока на последний, то получим кольцевой список.