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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • дисплей - отображает список.

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

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

пример

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, пожалуйста, нажмите здесь .