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 .