Источник: Nuances of Programming
Предыдущая статья: “Структуры данных: двусвязный (двунаправленный) список”
Кольцевой (циклический, замкнутый) связный список — это разновидность связного списка, при которой первый элемент указывает на последний, а последний — на первый. Кольцевой (циклический, замкнутый) связный список можно сделать как из односвязного (однонаправленного), так и из двусвязного (двунаправленного) списка.
Кольцевой связный список из односвязного
В односвязном списке указатель 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();
}
Читайте также: