Implementazione Java dell'elenco collegato circolare

1. Introduzione

In questo tutorial, esamineremo l'implementazione di un elenco collegato circolare in Java.

2. Elenco collegato circolare

Un elenco collegato circolare è una variazione di un elenco collegato in cui l'ultimo nodo punta al primo nodo, completando un cerchio completo di nodi . In altre parole, questa variazione della lista collegata non ha un elemento nullo alla fine.

Con questa semplice modifica, otteniamo alcuni vantaggi:

  • Qualsiasi nodo nell'elenco collegato circolare può essere un punto di partenza
  • Di conseguenza, l'intera lista può essere percorsa a partire da qualsiasi nodo
  • Poiché l'ultimo nodo dell'elenco collegato circolare ha il puntatore al primo nodo, è facile eseguire operazioni di accodamento e rimozione dalla coda

Tutto sommato, questo è molto utile nell'implementazione della struttura dei dati della coda.

Dal punto di vista delle prestazioni, è uguale ad altre implementazioni di liste collegate tranne per una cosa: il passaggio dall'ultimo nodo al nodo principale può essere fatto in tempo costante . Con gli elenchi concatenati convenzionali, questa è un'operazione lineare.

3. Implementazione in Java

Iniziamo creando una classe Node ausiliaria che memorizzerà valori int e un puntatore al nodo successivo :

class Node { int value; Node nextNode; public Node(int value) { this.value = value; } }

Ora creiamo il primo e l'ultimo nodo nell'elenco collegato circolare, solitamente chiamato testa e coda:

public class CircularLinkedList { private Node head = null; private Node tail = null; // .... }

Nelle prossime sottosezioni daremo uno sguardo alle operazioni più comuni che possiamo eseguire su un elenco collegato circolare.

3.1. Inserimento di elementi

La prima operazione che andremo a coprire è l'inserimento di nuovi nodi. Durante l'inserimento di un nuovo elemento dovremo gestire due casi:

  • Il nodo head è nullo , ovvero non ci sono elementi già aggiunti. In questo caso, creeremo il nuovo nodo che aggiungiamo sia come testa che come coda della lista poiché c'è un solo nodo
  • Il nodo head non è nullo , ovvero ci sono uno o più elementi già aggiunti alla lista. In questo caso, la coda esistente dovrebbe puntare al nuovo nodo e il nodo appena aggiunto diventerà la coda

In entrambi i casi sopra, il nextNode per tail punterà a head

Creiamo un metodo addNode che prenda il valore da inserire come parametro:

public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; tail.nextNode = head; }

Ora possiamo aggiungere alcuni numeri al nostro elenco di collegamenti circolari:

private CircularLinkedList createCircularLinkedList() { CircularLinkedList cll = new CircularLinkedList(); cll.addNode(13); cll.addNode(7); cll.addNode(24); cll.addNode(1); cll.addNode(8); cll.addNode(37); cll.addNode(46); return cll; }

3.2. Trovare un elemento

La prossima operazione che esamineremo è la ricerca per determinare se un elemento è presente nell'elenco.

Per questo, aggiusteremo un nodo nell'elenco (di solito la testa ) come currentNode e attraverseremo l'intero elenco utilizzando il nextNode di questo nodo , fino a trovare l'elemento richiesto.

Aggiungiamo un nuovo metodo containsNode che accetta searchValue come parametro:

public boolean containsNode(int searchValue) { Node currentNode = head; if (head == null) { return false; } else { do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.nextNode; } while (currentNode != head); return false; } }

Ora, aggiungiamo un paio di test per verificare che l'elenco creato sopra contenga gli elementi che abbiamo aggiunto e non nuovi:

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(8)); assertTrue(cll.containsNode(37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() { CircularLinkedList cll = createCircularLinkedList(); assertFalse(cll.containsNode(11)); }

3.3. Eliminazione di un elemento

Successivamente, esamineremo l'operazione di eliminazione. Simile all'inserimento abbiamo un paio di casi (escluso il caso in cui l'elenco stesso è vuoto) che dobbiamo esaminare.

  • Elemento da eliminare è la testa stessa . In questo caso, è necessario aggiornare la testa come il successivo nodo della testa corrente , e il successivo nodo della coda come nuovo capo
  • L'elemento da eliminare è qualsiasi elemento diverso dalla testa . In questo caso, dobbiamo solo aggiornare il nodo successivo del nodo precedente come nodo successivo del nodo che deve essere eliminato

Aggiungeremo ora un nuovo metodo deleteNode che accetta valueToDelete come parametro:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Aggiungiamo ora un semplice test per verificare che l'eliminazione funzioni come previsto per tutti i casi:

@Test public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(13)); cll.deleteNode(13); assertFalse(cll.containsNode(13)); assertTrue(cll.containsNode(1)); cll.deleteNode(1); assertFalse(cll.containsNode(1)); assertTrue(cll.containsNode(46)); cll.deleteNode(46); assertFalse(cll.containsNode(46)); }

3.4. Attraversando la lista

Daremo uno sguardo all'attraversamento della nostra lista circolare collegata in questa sezione finale . Simile alle operazioni di ricerca ed eliminazione, per l'attraversamento fissiamo il currentNode come head e attraversiamo l'intero elenco utilizzando il nextNode di questo nodo.

Aggiungiamo un nuovo metodo traverseList che stampa gli elementi aggiunti alla lista:

public void traverseList() { Node currentNode = head; if (head != null) { do { LOGGER.info(currentNode.value + " "); currentNode = currentNode.nextNode; } while (currentNode != head); } } 

Come possiamo vedere, nell'esempio sopra, durante l'attraversamento, stampiamo semplicemente il valore di ciascuno dei nodi, finché non torniamo al nodo head.

4. Conclusione

In questo tutorial, abbiamo visto come implementare un elenco collegato circolare in Java ed esplorato alcune delle operazioni più comuni.

Innanzitutto, abbiamo appreso che cos'è esattamente un elenco collegato circolare che include alcune delle caratteristiche e delle differenze più comuni con un elenco collegato convenzionale. Quindi, abbiamo visto come inserire, cercare, eliminare e attraversare gli elementi nella nostra implementazione dell'elenco collegato circolare.

Come al solito, tutti gli esempi utilizzati in questo articolo sono disponibili su GitHub.