Структура данных — круговой связанный список

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

Единственный связанный список как круговой

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

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

В двусвязном списке следующий указатель последнего узла указывает на первый узел, а предыдущий указатель первого узла указывает на последний узел, делающий круговую в обоих направлениях.

Согласно приведенной выше иллюстрации, ниже приведены важные моменты, которые необходимо учитывать.

• Следующая ссылка последней ссылки указывает на первую ссылку списка в обоих случаях как одиночного, так и двусвязного списка.

• Первая ссылка указывает на последний список в случае двусвязного списка.

Следующая ссылка последней ссылки указывает на первую ссылку списка в обоих случаях как одиночного, так и двусвязного списка.

Первая ссылка указывает на последний список в случае двусвязного списка.

Основные операции

Ниже приведены важные операции, поддерживаемые циклическим списком.

• insert — вставляет элемент в начало списка.

• удалить — удаляет элемент из начала списка.

• display — отображает список

insert — вставляет элемент в начало списка.

удалить — удаляет элемент из начала списка.

display — отображает список

Операция вставки

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

пример

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;
	
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
		
      //point first to new first node
      head = link;
   }   
}

Операция удаления

Следующий код демонстрирует операцию удаления в круговом связанном списке на основе одного связанного списка.

//delete first item
struct node * deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
	
   if(head->next == head) {  
      head = NULL;
      return tempLink;
   }     

   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

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

Следующий код демонстрирует операцию отображения списка в виде круглого связанного списка.

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
	
   printf(" ]");
}

Чтобы узнать о его реализации на языке программирования C, пожалуйста, нажмите здесь .