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

Татуировки

Последнее обновление: 25.10.2016

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

Например, если у нас список состоит из одного головного элемента head, то мы можем замкнуть такой список следующим образом:

Head.next = head;

Для реализации возьмем класс элемента, который используется в односвязном списке:

Public class Node { public Node(T data) { Data = data; } public T Data { get; set; } public Node Next { get; set; } }

Теперь определим класс кольцевого списка:

Using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp { public class CircularLinkedList : IEnumerable // кольцевой связный список { Node head; // головной/первый элемент Node tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void Add(T data) { Node node = new Node(data); // если список пуст if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++; } public bool Remove(T data) { Node current = head; Node previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { // убираем узел current, теперь previous ссылается не на current, а на current.Next previous.Next = current.Next; // Если узел последний, // изменяем переменную tail if (current == tail) tail = previous; } else // если удаляется первый элемент { // если в списке всего один элемент if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false; } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { Node current = head; if (current == null) return false; do { if (current.Data.Equals(data)) return true; current = current.Next; } while (current != head); return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { Node current = head; do { if (current != null) { yield return current.Data; current = current.Next; } } while (current != head); } } }

Добавление фактически сводится к переустановке указателя на последний элемент tail, а новый элемент помещается между tail и head:

Public void Add(T data) { Node node = new Node(data); // если список пуст if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++; }

При удалении переустанавливаем указатель на следующий элемент у предыдущего элемента по отношению к удаляемому:

Public bool Remove(T data) { Node current = head; Node previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { // убираем узел current, теперь previous ссылается не на current, а на current.Next previous.Next = current.Next; // Если узел последний, // изменяем переменную tail if (current == tail) tail = previous; } else // если удаляется первый элемент { // если в списке всего один элемент if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false; }

Применение кольцевого списка:

CircularLinkedList circularList = new CircularLinkedList(); circularList.Add("Tom"); circularList.Add("Bob"); circularList.Add("Alice"); circularList.Add("Jack"); foreach (var item in circularList) { Console.WriteLine(item); } circularList.Remove("Bob"); Console.WriteLine("\n После удаления: \n"); foreach (var item in circularList) { Console.WriteLine(item); }

Консольный вывод:

Tom Bob Alice Jack После удаления: Tom Alice Jack

Аннотация: В лекции рассматриваются определения, способы объявления, инициализация и особенности использования при решении задач циклических списков, деков, красно-черных деревьев, приводятся примеры решения задач на обработку кольцевых списков, деков, красно-черных деревьев.

Цель лекции : изучить алгоритмы и приемы работы с динамическими структурами данных , научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

Структурированные типы данных , такие, как массивы, множества , записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы , указатели и динамические переменные , можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных . Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S , одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип . В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя "корня" (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной , указатель на которую содержится в переменной d . Этот подход позволяет создать динамическую структуру с любой топологией.

Циклические (кольцевые) списки

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

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными .

Похож на линейный однонаправленный список , но его последний элемент содержит указатель , связывающий его с первым элементом ( рис. 32.1).

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

Рис. 32.1.

Основные операции , осуществляемые с циклическим однонаправленным списком:

создание списка;
печать (просмотр) списка;
вставка элемента в список;
удаление элемента из списка;
поиск элемента в списке;
проверка пустоты списка;
удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop){ if (n > 0) { (*Head) = new Circle_Single_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); } else { (*Head) = Loop; } } //печать циклического однонаправленного списка void Print_Circle_Single_List(Circle_Single_List* Head) { Circle_Single_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr-> << "\n"; } /*вставка элемента после заданного номера в циклический однонаправленный список*/ Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head, int Number, int DataItem){ Circle_Single_List *Current = Head; //встали на первый элемент Circle_Single_List *NewItem = new(Circle_Single_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического однонаправленного списка*/ Circle_Single_List* Delete_Item_Circle_Single_List (Circle_Single_List* Head, int Number){ if (Head != NULL){ Circle_Single_List *Current = Head; if (Head-> < Number; i++) Current = Current->Next; Circle_Single_List *ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; //непосредственное удаление элемента ptr->Next = Current->Next; if (Head = Current) Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом однонаправленном списке bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem){ Circle_Single_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического однонаправленного списка bool Empty_Circle_Single_List(Circle_Single_List* Head){ return (Head != NULL ? false: true); } //удаление циклического однонаправленного списка void Delete_Circle_Single_List(Circle_Single_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Single_List(Head, 1); Delete_Circle_Single_List(Head); } } Листинг 1.

Похож на линейный двунаправленный список , но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент ( рис. 32.2).

Рис. 32.2.

Основные операции , осуществляемые с циклическим двунаправленным списком:

создание списка;
печать (просмотр) списка;
вставка элемента в список;
удаление элемента из списка;
поиск элемента в списке
проверка пустоты списка;
удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head,Circle_Double_List* Loop){ Circle_Double_List* ptr;//вспомогательный указатель if (n > 0) { (*Head) = new Circle_Double_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop); if ((*Head)->Next != NULL) (*Head)->Next->Prior = (*Head); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; } else { (*Head) = Loop; return NULL; } } //печать циклического двунаправленного списка void Print_Circle_Double_List(Circle_Double_List* Head) { Circle_Double_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr->Next; } while (ptr!=Head); cout << "\n"; } /*вставка элемента после заданного номера в циклический двунаправленный список*/ Circle_Double_List* Insert_Item_Circle_Double_List (Circle_Double_List* Head, int Number, int DataItem){ Circle_Double_List *Current = Head; //встали на первый элемент Circle_Double_List *NewItem = new(Circle_Double_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; NewItem->Prior = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; NewItem->Prior = Current; NewItem->Next->Prior = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического двунаправленного списка*/ Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number){ if (Head != NULL){ Circle_Double_List *Current = Head; if (Head->Next != Head){ for (int i = 1; i < Number; i++) Current = Current->Next; Circle_Double_List *ptr = Current->Next; Current->Prior->Next = Current->Next; Current->Next->Prior = Current->Prior; if (Head = Current) //удаляем первый Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом двунаправленном списке bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem){ Circle_Double_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического двунаправленного списка bool Empty_Circle_Double_List(Circle_Double_List* Head){ return (Head != NULL ? false: true); } //удаление циклического двунаправленного списка void Delete_Circle_Double_List(Circle_Double_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Double_List(Head, 1); Delete_Circle_Double_List(Head); } } Листинг 2.

Текст лекции.

Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных. Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя «корня» (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной, указатель на которую содержится в переменной d. Этот подход позволяет создать динамическую структуру с любой топологией.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как «первый» путем установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.

Рис. 1. Циклический однонаправленный список

Основные операции, осуществляемые с циклическим однонаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· поиск элемента в списке;

· проверка пустоты списка;

· удаление списка.

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Loop){

(*Head) = new Circle_Single_List();

cout << "Введите значение ";

cin >> (*Head)->Data;

(*Head)->

Make_Circle_Single_List(n-1,&((*Head)->Next),Loop);

//печать циклического однонаправленного списка

void Print_Circle_Single_List(Circle_Single_List* Head) {

Circle_Single_List* ptr=Head;

//вспомогательный указатель

cout << ptr->Data << "\t";

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

/*вставка элемента после заданного номера в циклический однонаправленный список*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem){

//встали на первый элемент

Circle_Single_List *NewItem = new(Circle_Single_List);

//создали новый элемент

NewItem->Data = DataItem;

NewItem->Next = NewItem;

else {//список не пуст

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

/*удаление элемента с заданным номером из циклического однонаправленного списка*/

Circle_Single_List* Delete_Item_Circle_Single_List

(Circle_Single_List* Head, int Number){

if (Head != NULL){

Circle_Single_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

while (ptr->Next != Current)

ptr = ptr->Next;

//непосредственное удаление элемента

ptr->Next = Current->Next;

if (Head = Current) Head = Current->Next;

delete(Current);

//поиск элемента в циклическом однонаправленном списке

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

while (ptr != Head);

//проверка пустоты циклического однонаправленного списка

bool Empty_Circle_Single_List(Circle_Single_List* Head){

//удаление циклического однонаправленного списка

void Delete_Circle_Single_List(Circle_Single_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Single_List(Head, 1);

Delete_Circle_Single_List(Head);

Циклический двунаправленный список похож на линейный двунаправленный список, но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент (рис. 2).

Рис.2. Циклический двунаправленный список

Основные операции, осуществляемые с циклическим двунаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· удаление элемента из списка;

· поиск элемента в списке

· проверка пустоты списка;

· удаление списка.

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка

Circle_Double_List* Make_Circle_Double_List(int n,

Circle_Double_List** Head,Circle_Double_List* Loop){

Circle_Double_List* ptr;//вспомогательный указатель

(*Head) = new Circle_Double_List();

//выделяем память под новый элемент

if (Loop == NULL) Loop = (*Head);

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значение информационного поля

(*Head)->Next=NULL;//обнуление адресного поля

ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);

if ((*Head)->Next != NULL)

(*Head)->Next->Prior = (*Head);

if ((*Head)->Prior == NULL)

(*Head)->Prior = ptr;

if (ptr == NULL)

else return ptr;

//печать циклического двунаправленного списка

void Print_Circle_Double_List(Circle_Double_List* Head) {

Circle_Double_List* ptr=Head;

//вспомогательный указатель

cout << ptr->Data << "\t";

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

/*вставка элемента после заданного номера в циклический двунаправленный список*/

Circle_Double_List* Insert_Item_Circle_Double_List

(Circle_Double_List* Head, int Number, int DataItem){

//встали на первый элемент

Circle_Double_List *NewItem = new(Circle_Double_List);

//создали новый элемент

NewItem->Data = DataItem;

if (Head == NULL) {//список пуст

NewItem->Next = NewItem;

NewItem->Prior = NewItem;

else {//список не пуст

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

NewItem->Prior = Current;

NewItem->Next->Prior = NewItem;

/*удаление элемента с заданным номером из циклического двунаправленного списка*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (Head != NULL){

Circle_Double_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

Circle_Double_List *ptr = Current->Next;

Current->Prior->Next = Current->Next;

Current->Next->Prior = Current->Prior;

if (Head = Current) //удаляем первый

Head = Current->Next;

delete(Current);

//поиск элемента в циклическом двунаправленном списке

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data)

else ptr = ptr->Next;

while (ptr != Head);

//проверка пустоты циклического двунаправленного списка

bool Empty_Circle_Double_List(Circle_Double_List* Head){

return (Head != NULL ? false: true);

//удаление циклического двунаправленного списка

void Delete_Circle_Double_List(Circle_Double_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);

Для доступа к требуемому элементу линейного списка необходимо просматривать список с его начала независимо от положения исходной точки просмотра. Это замедляет операции доступа к элементам в списке. Замыкание элементов списка в кольцо позволяет устранить этот недостаток. Такой список называется циклическим. Просмотр циклического списка можно начинать с любого элемента, а не только с его начала, причем началом списка может служить любой из его элементов. Логическая структура циклического списка:

Операции над циклическим списком

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

Для циклического списка также вводится новая операция – сцепление двух циклических списков – Сoncat (с 1,с 2).

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

Реализация циклического списка с помощью динамических переменных:

Такой список называется односвязным циклическим списком . Из любого элемента списка можно достичь любого другого элемента. Отметим, что циклический список не имеет первого и последнего элементов. Внешний указательHeadудобно использовать в качестве указателя на текущий элемент списка. При решении конкретных задач условно можно считать, что он адресуетпоследний элемент списка, что автоматически делает следующий за ним элемент первым.

Класс tCircleListможет быть описан следующим образом:

tValue= Real;// тип значения элемента списка - вещественный

pItem= ^tItem; // тип указателя на элемент списка

tItem= record // тип элемента списка

Value: tValue; // содержательная часть элемента списка

Next: pItem; // указатель на следующий элемент списка

end ; // record tItem

tCircleList=class // класс - циклический список

protected

fHead: pItem;// поле - указатель на текущий элемент списка

fSize:Word;// поле - число элементов списка

public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство – указатель на начало списка (доступ по чтению и записи)

property Head: Word read fHead write fHead;

v после элемента с адресом Addr

procedure InsertAfter(Addr: pItem; v: tValue);

// Включение элемента со значением v перед элементом с адресом Addr

procedure InsertBefore(Addr: pItem; v: tValue);

// Исключение элемента, следующего за элементом с адресом Addr

function DeleteAfter(Addr: pItem): tValue;

// Исключение элемента с указателем Addr

function Delete(Addr:pItem):tValue;

// Включение элемента со значением v в начало списка

procedure InsertHead(v:tValue);

// Включение элемента со значением v в конец списка

procedure InsertRear(v:tValue);

// Исключение элемента из начала списка

function DeleteHead:tValue;

// Исключение элемента из конца списка

function DeleteRear:tValue;

procedure Concat(var CList2: tCircleList); // сцепление со списком CList2

// Поиск в списке элемента со значением v и возвращение его адреса

function Search(v: tValue): pItem;

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override ; // деструктор - удаление списка

end ; // class tCircleList

Класс tCircleListне объявлен наследником классаtListпоскольку реализация практически всех его методов отличается от реализации одноимённых методов для нециклического списка. Отличия, в основном, заключаются в следующем:

– для операций InsertAfterиInsertBeforeпо-другому осуществляются включение элемента в пустой список и включение в начало и конец циклического списка;

– применение операции DeleteAfterдля циклического списка, состоящего из одного элемента, не должно приводить к исключению самого этого элемента;

– методы DeleteAfterиDeleteдолжны восстанавливать указатель на последний элемент циклического списка, если он исключается при выполнении этих операций;

– в методах SearchиClearпризнаком завершения просмотра циклического списка является достижение вспомогательным указателем того элемента, с которого начался просмотр.

И только конструктор Createи деструкторDestroyреализуются так же как и одноимённые методы классаtList.

Очевидно, что операции включения и исключения справа и слева от текущего элемента (InsertHead,InsertRear,DeleteHead,DeleteRear) выполняют те же действия, что и одноимённые операции для нециклического списка. Отличие заключается в том, что новые операции изменяют значение указателя на последний элемент циклического списка, если список расширился влево или вправо либо сузился слева или справа.

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

Циклические (кольцевые) списки

Операции над циклическим списком

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