Körkörös összekapcsolt lista Java megvalósítása

1. Bemutatkozás

Ebben az oktatóanyagban egy kör alakú linkelt lista megvalósítását vizsgáljuk meg a Java-ban.

2. Kör alakú összekapcsolt lista

A kör alakú összekapcsolt lista egy olyan összekapcsolt lista változata, amelyben az utolsó csomópont az első csomópontra mutat, teljes csomópont kört kitöltve. Más szavakkal, a linkelt lista ezen változatán nincs a nulla elem a végén.

Ezzel az egyszerű változtatással néhány előnyhöz juthatunk:

  • Bármely csomópont a kör alakú linkelt listában lehet kiindulópont
  • Következésképpen az egész lista bármely csomópontból indulhat
  • Mivel a kör alakú összekapcsolt lista utolsó csomópontjánál az első csomópont mutatója van, könnyű végrehajtani a leállítás és a leállítás műveleteket

Összességében, ez nagyon hasznos a sor adatstruktúrájának megvalósításában.

Teljesítményileg megegyezik a többi kapcsolt lista megvalósítással, egy dolgot leszámítva: Az utolsó csomóponttól a fejcsomópontig való haladás állandó időben végezhető. Hagyományos összekapcsolt listákkal ez lineáris művelet.

3. Megvalósítás Java-ban

Kezdjük egy segédprogram létrehozásával Csomópont osztály, amely tárolni fog int értékeket és egy mutatót a következő csomópontra:

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

Most hozzuk létre az első és az utolsó csomópontot a kör alakú linkelt listában, amelyet általában fej és farok:

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

A következő alfejezetekben megnézzük a leggyakoribb műveleteket, amelyeket körkörös hivatkozott listán végezhetünk.

3.1. Elemek beszúrása

Az első művelet, amelyre kiterjedünk, új csomópontok beillesztése. Új elem beillesztése során két esetet kell kezelnünk:

  • A fej csomópont null, vagyis nincsenek már hozzáadott elemek. Ebben az esetben elkészítjük az új csomópontot, amelyet mindkettőként hozzáadunk fej és farok mivel csak egy csomópont van
  • A fej csomópont nem null, vagyis egy vagy több elem már szerepel a listán. Ebben az esetben a meglévő farok mutatnia kell az új csomópontra, és az újonnan hozzáadott csomópont lesz a farok

A fenti két esetben a nextNode mert farok rámutat fej

Hozzunk létre egy addNode módszer, amely a érték beillesztendő paraméterként:

public void addNode (int érték) {Csomópont newNode = új Csomópont (érték); if (head == null) {head = newNode; } else {tail.nextNode = newNode; } tail = newNode; tail.nextNode = fej; }

Most felvehetünk néhány számot a körkörös linkelt listánkba:

privát CircularLinkedList createCircularLinkedList () {CircularLinkedList cll = új 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. Elem megtalálása

A következő művelet, amelyet megnézünk, annak megállapítása, hogy van-e egy elem a listán.

Ezért, kijavítunk egy csomópontot a listában (általában a fej) mint a currentNode és a teljes listán keresztülhaladjon a nextNode ennek a csomópontnak, amíg meg nem találjuk a szükséges elemet.

Adjunk hozzá egy új módszert tartalmazzaNode hogy veszi a searchValue paraméterként:

nyilvános logikai érték tartalmazzaNode (int searchValue) {Csomópont currentNode = fej; if (fej == null) {return false; } else {do ​​{if (currentNode.value == searchValue) {return true; } currentNode = currentNode.nextNode; } while (currentNode! = fej); return false; }}

Most tegyünk hozzá pár tesztet annak ellenőrzésére, hogy a fent létrehozott lista tartalmazza-e a hozzáadott elemeket, és nincsenek újak:

@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. Elem törlése

Ezután megvizsgáljuk a törlési műveletet. A beszúráshoz hasonlóan van néhány olyan eset (kivéve azt az esetet, amikor maga a lista üres), amelyeket meg kell vizsgálnunk.

  • A törlendő elem a fej maga. Ebben az esetben frissítenünk kell a fej mint az aktuális fej következő csomópontja, és a következő csomópontja farok mint az új fej
  • A törlendő elem a fej. Ebben az esetben csak frissítenünk kell az előző csomópont következő csomópontját, mint a törlendő csomópont következő csomópontját

Most hozzáadunk egy új módszert csomópont törlése hogy veszi a valueToDelete paraméterként:

public void deleteNode (int valueToDelete) {Csomópont currentNode = fej; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = fej; } else {do ​​{Csomópont következőNode = currentNode.nextNode; if (következőNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; szünet; } currentNode = currentNode.nextNode; } while (currentNode! = fej); }}}

Adjunk hozzá egy egyszerű tesztet annak ellenőrzésére, hogy a törlés minden esetben a várt módon működik-e:

@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. A listán való bejárás

Megnézzük körkörös hivatkozott listánk bejárását ebben az utolsó szakaszban. Hasonlóan a keresési és törlési műveletekhez, a bejáráshoz kijavítjuk a currentNode mint fej és a teljes listán keresztülhaladjon a nextNode ennek a csomópontnak.

Adjunk hozzá egy új módszert traverseList kinyomtatja a listához hozzáadott elemeket:

public void traverseList () {Csomópont currentNode = fej; if (fej! = null) {do {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } while (currentNode! = fej); }} 

Mint láthatjuk, a fenti példában a bejárás során egyszerűen kinyomtatjuk az egyes csomópontok értékét, amíg vissza nem térünk a fejcsomópontig.

4. Következtetés

Ebben az oktatóanyagban láthattuk, hogyan lehet körkörös hivatkozott listát implementálni a Java-ban, és feltártuk a leggyakoribb műveleteket.

Először megtudtuk, hogy pontosan mit tartalmaz egy kör alakú összekapcsolt lista, amely tartalmazza a leggyakoribb jellemzőket és különbségeket egy hagyományos összekapcsolt listával szemben. Ezután láttuk, hogyan lehet elemeket beilleszteni, keresni, törölni és bejárni körkörös hivatkozott listánk megvalósításába.

Szokás szerint az ebben a cikkben használt összes példa elérhető a GitHubon.