Estrutura de dados - lista vinculada circular

Lista vinculada circular é uma variação da lista vinculada na qual o primeiro elemento aponta para o último elemento e o último elemento aponta para o primeiro elemento. Tanto a Lista vinculada individualmente quanto a Lista vinculada duplamente podem ser transformadas em uma lista vinculada circular.

Lista vinculada individualmente como circular

Na lista unida individualmente, o próximo ponteiro do último nó aponta para o primeiro nó.

Lista duplamente vinculada como circular

Na lista duplamente ligada, o próximo ponteiro do último nó aponta para o primeiro nó e o ponteiro anterior do primeiro nó aponta para o último nó que faz a circular em ambas as direções.

Conforme a ilustração acima, a seguir estão os pontos importantes a serem considerados.

  • O próximo link do último aponta para o primeiro link da lista em ambos os casos de lista unida ou duplamente vinculada.

  • O anterior do primeiro link aponta para o último da lista no caso de lista duplamente vinculada.

Operações básicas

A seguir estão as operações importantes apoiadas por uma lista circular.

  • insert - Insere um elemento no início da lista.

  • delete - Exclui um elemento do início da lista.

  • display - Exibe a lista.

Operação de Inserção

O código a seguir demonstra a operação de inserção em uma lista vinculada circular com base em uma lista vinculada única.

Exemplo

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

Operação de Exclusão

O código a seguir demonstra a operação de exclusão em uma lista vinculada circular com base em uma lista vinculada única.

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

Operação da lista de exibição

O código a seguir demonstra a operação da lista de exibição em uma lista ligada circular.

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

Para saber sobre sua implementação na linguagem de programação C, clique aqui .