Структуры данных: кольцевой (циклический, замкнутый) связный список

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

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

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

В односвязном списке указатель 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(" [ ");
	
   //начать с начала
   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(" Deleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);
   }   
	
   printf(" List after deleting all items: ");
   printList();   
}