streamalism.org

1. Overzicht

In deze zelfstudie leggen we uit hoe u het middelste element van een gekoppelde lijst in Java kunt vinden.

We zullen de belangrijkste problemen in de volgende secties introduceren, en we zullen verschillende benaderingen laten zien om ze op te lossen.

2. Bijhouden van de grootte

Dit probleem kan eenvoudig worden opgelost door de grootte bijhouden wanneer we nieuwe elementen aan de lijst toevoegen. Als we de grootte kennen, weten we ook waar het middelste element is, dus de oplossing is triviaal.

Laten we een voorbeeld bekijken met de Java-implementatie van een LinkedList:

public static Optioneel findMiddleElementLinkedList (LinkedList linkedList) {if (linkedList == null || linkedList.isEmpty ()) {return Optional.empty (); } return Optioneel.of (linkedList.get ((linkedList.size () - 1) / 2)); }

Als we de interne code van het LinkedList class, kunnen we zien dat we in dit voorbeeld gewoon de lijst doorlopen totdat we het middelste element bereiken:

Knooppunt knooppunt (int index) {if (index> 1)) {Knooppunt x = eerste; voor (int i = 0; i <index; i ++) {x = x.next; } geef x terug; } anders {Knooppunt x = laatste; for (int i = size - 1; i> index; i--) {x = x.prev; } geef x terug; }}

3. Het midden vinden zonder de grootte te kennen

Het komt heel vaak voor dat we problemen tegenkomen waar we hebben alleen het hoofdknooppunt van een gekoppelde lijst, en we moeten het middelste element vinden. In dit geval weten we de grootte van de lijst niet, waardoor dit probleem moeilijker op te lossen is.

We zullen in de volgende secties verschillende benaderingen laten zien om dit probleem op te lossen, maar eerst moeten we een klasse maken die een knooppunt van de lijst vertegenwoordigt.

Laten we een Knooppunt klasse, die opslaat Draad waarden:

openbare statische klasse Node {private Node next; privé String-gegevens; // constructors / getters / setters public boolean hasNext () {return next! = null; } public void setNext (Node next) {this.next = next; } public String toString () {retourneer this.data; }}

We zullen deze hulpmethode ook gebruiken in onze testcases om een ​​enkelvoudig gekoppelde lijst te maken met alleen onze knooppunten:

privé statisch knooppunt createNodesList (int n) {Knooppunt head = nieuw knooppunt ("1"); Knoopstroom = hoofd; for (int i = 2; i <= n; i ++) {Node newNode = new Node (String.valueOf (i)); current.setNext (newNode); current = newNode; } terugkeer hoofd; }

3.1. Eerst de maat vinden

De eenvoudigste benadering om dit probleem aan te pakken, is door eerst de grootte van de lijst te vinden en daarna dezelfde benadering te volgen die we eerder gebruikten - door te herhalen tot het middelste element.

Laten we deze oplossing in actie zien:

openbare statische Optioneel findMiddleElementFromHead (Node head) {if (head == null) {return Optional.empty (); } // bereken de grootte van de lijst Node current = head; int maat = 1; while (current.hasNext ()) {current = current.next (); maat ++; } // herhaal tot het middelste element current = head; for (int i = 0; i <(size - 1) / 2; i ++) {current = current.next (); } return Optioneel.of (current.data ()); }

Zoals we kunnen zien, deze code herhaalt de lijst twee keer. Daarom presteert deze oplossing slecht en wordt deze niet aanbevolen.

3.2. Iteratief het middelste element in één doorgang vinden

We gaan nu de vorige oplossing verbeteren door het middelste element te vinden met slechts één iteratie over de lijst.

Om dat iteratief te doen, hebben we twee aanwijzingen nodig om de lijst tegelijkertijd te doorlopen. Eén aanwijzer zal in elke iteratie 2 knooppunten vooruitgaan en de andere aanwijzer zal slechts één knooppunt per iteratie vooruitgaan.

Wanneer de snellere aanwijzer het einde van de lijst bereikt, staat de langzamere aanwijzer in het midden:

openbare statische Optioneel findMiddleElementFromHead1PassIterative (Node head) {if (head == null) {return Optional.empty (); } Knooppunt slowPointer = head; Knooppunt fastPointer = hoofd; while (fastPointer.hasNext () && fastPointer.next (). hasNext ()) {fastPointer = fastPointer.next (). next (); slowPointer = slowPointer.next (); } return Optioneel.ofNullable (slowPointer.data ()); }

We kunnen deze oplossing testen met een eenvoudige unit-test met behulp van lijsten met zowel een oneven als een even aantal elementen:

@Test openbare leegte whenFindingMiddleFromHead1PassIterative_thenMiddleFound () {assertEquals ("3", MiddleElementLookup .findMiddleElementFromHead1PassIterative (createNodesList (5)). Get ()); assertEquals ("2", MiddleElementLookup .findMiddleElementFromHead1PassIterively (reateNodesList (4)). get ()); }

3.3. Recursief het middelste element in één doorgang vinden

Een andere manier om dit probleem in één keer op te lossen, is door recursie te gebruiken. We kunnen herhalen tot het einde van de lijst om de grootte te kennen en, bij de callbacks tellen we gewoon tot de helft van de grootte.

Om dit in Java te doen, gaan we een hulpklasse maken om de referenties van de lijstgrootte en het middelste element te behouden tijdens de uitvoering van alle recursieve aanroepen:

privé statische klasse MiddleAuxRecursion {Knooppunt midden; int lengte = 0; }

Laten we nu de recursieve methode implementeren:

private static void findMiddleRecursively (Node node, MiddleAuxRecursion middleAux) {if (node ​​== null) {// bereikte het einde middleAux.length = middleAux.length / 2; terugkeren; } middleAux.length ++; findMiddleRecursively (node.next (), middleAux); if (middleAux.length == 0) {// vond de middelste middleAux.middle = node; } middleAux.length--; }

En tot slot, laten we een methode maken die de recursieve aanroept:

openbare statische Optioneel findMiddleElementFromHead1PassRecursively (Node head) {if (head == null) {return Optional.empty (); } MiddleAuxRecursion middleAux = nieuwe MiddleAuxRecursion (); findMiddleRecursively (head, middleAux); return Optioneel.of (middleAux.middle.data ()); }

Nogmaals, we kunnen het op dezelfde manier testen als voorheen:

@Test openbare leegte whenFindingMiddleFromHead1PassRecursively_thenMiddleFound () {assertEquals ("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively (createNodesList (5)). Get ()); assertEquals ("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively (createNodesList (4)). get ()); }

4. Conclusie

In dit artikel hebben we het probleem van het vinden van het middelste element van een gekoppelde lijst in Java geïntroduceerd, en we hebben verschillende manieren laten zien om dit op te lossen.

We zijn begonnen met de eenvoudigste benadering waarbij we de grootte hebben bijgehouden, en daarna zijn we doorgegaan met de oplossingen om het middelste element van het hoofdknooppunt van de lijst te vinden.

Zoals altijd is de volledige broncode van de voorbeelden beschikbaar op GitHub.