Struttura dei dati - Elenco collegato circolare

L'elenco collegato circolare è una variazione dell'elenco collegato in cui il primo elemento punta all'ultimo elemento e l'ultimo elemento punta al primo elemento. Sia l'elenco collegato singolarmente che l'elenco collegato in modo doppio possono essere trasformati in un elenco collegato circolare.

Elenco collegato singolarmente come circolare

In un elenco collegato singolarmente, il puntatore successivo dell'ultimo nodo punta al primo nodo.

Elenco doppiamente collegato come circolare

Nella lista doppiamente concatenata, il puntatore successivo dell'ultimo nodo punta al primo nodo e il puntatore precedente del primo nodo punta all'ultimo nodo facendo la circolare in entrambe le direzioni.

Come per l'illustrazione sopra, di seguito sono riportati i punti importanti da considerare.

  • L'ultimo collegamento punta al primo collegamento dell'elenco in entrambi i casi di elenco a collegamento singolo o doppio.

  • Il precedente del primo collegamento punta all'ultimo della lista in caso di lista doppiamente collegata.

Operazioni di base

Di seguito sono riportate le operazioni importanti supportate da un elenco circolare.

  • insert - Inserisce un elemento all'inizio della lista.

  • delete - Elimina un elemento dall'inizio della lista.

  • display - Visualizza l'elenco.

Operazione di inserimento

Il codice seguente mostra l'operazione di inserimento in un elenco collegato circolare basato su un singolo elenco collegato.

Esempio

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

Operazione di cancellazione

Il codice seguente illustra l'operazione di eliminazione in un elenco collegato circolare basato su un singolo elenco collegato.

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

Funzionamento dell'elenco di visualizzazione

Il codice seguente dimostra l'operazione dell'elenco di visualizzazione in un elenco collegato circolare.

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

Per conoscere la sua implementazione nel linguaggio di programmazione C, fare clic qui .