Предыдущая статья: “Структуры данных: двусвязный (двунаправленный) список

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

Кольцевой связный список из односвязного

В односвязном списке указатель next последнего узла указывает на первый узел:

Кольцевой связный список из двусвязного 

В двусвязном списке указатель next последнего узла указывает на первый узел, а указатель previous первого  —  на последний. Так получается кольцевой связный список в обоих направлениях:

Здесь надо учитывать следующие важные моменты:

  • next последней ссылки указывает на первую ссылку списка в обоих случаях  —  в односвязном списке и в двусвязном.
  • previous первой ссылки указывает на последнюю ссылку в двусвязном списке.

Базовые операции

Это основные операции, проводимые над списками:

  • Вставка элемента в начало списка.
  • Удаление элемента из начала списка.
  • Отображение списка.

Вставка

В этом коде показана операция вставки в кольцевом связном списке на основе односвязного :

Пример

insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
head := node
next of node = head
else
temp := head
while next of temp is not head, do
temp := next of temp
done
next of node := head
next of temp := node
head := node
end if
End

Удаление

В этом коде показана операция удаления в кольцевом связном списке на основе односвязного:

deleteFirst():
Begin
if head is null, then
it is Underflow and return
else if next of head = head, then
head := null
deallocate head
else
ptr := head
while next of ptr is not head, do
ptr := next of ptr
next of ptr = next of head
deallocate head
head := next of ptr
end if
End

Отображение списка

В этом коде показана операция отображения списка в кольцевом связном списке:

display():
Begin
if head is null, then
Nothing to print and return
else
ptr := head
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End

Вот реализация на языке программирования C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;

struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;

//если список пуст
if(head == NULL) {
return 0;
}

current = head->next;

while(current != head) {
length++;
current = current->next;
}

return length;
}

//вставить указатель в начало
void insertFirst(int key, int data) {

//создать указатель
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if (isEmpty()) {
head = link;
head->next = head;
} else {
//указать на старый первый элемент
link->next = head;

//указать начало на новый первый узел
head = link;
}
}

//удалить первый элемент
struct node * deleteFirst() {

//сохранить ссылку на первый указатель
struct node *tempLink = head;

if(head->next == head) {
head = NULL;
return tempLink;
}

//установить указатель, следующий за первым указателем, первым
head = head->next;

//возвратить удаленный указатель
return tempLink;
}

//отобразить список
void printList() {

struct node *ptr = head;
printf("\n[ ");

//начать с начала
if(head != NULL) {

while(ptr->next != ptr) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}

printf(" ]");
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//вывести список
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");
printList();
}

Читайте также:

Читайте нас в TelegramVK и Яндекс.Дзен

Предыдущая статьяКак стать специалистом по обработке данных: 5 советов
Следующая статьяРазличия между псевдонимами типов и интерфейсами в TypeScript 4.6