Topdatastructuren en algoritmen in Java die u moet kennen

Als ik het allerbelangrijkste onderwerp in softwareontwikkeling zou moeten kiezen, dan zijn dat datastructuren en algoritmen. U kunt het beschouwen als het fundamentele hulpmiddel dat beschikbaar is voor elke computerprogrammeur. Tijdens het programmeren gebruiken we data structuren om gegevens op te slaan en te organiseren, en algoritmen om de gegevens in die structuren te manipuleren. Dit artikel bevat een gedetailleerd overzicht van alle gangbare datastructuren en algoritmen in zodat lezers goed uitgerust worden.

Hieronder staan ​​de onderwerpen die in dit artikel worden besproken:

• Datastructuren in Java
  • Lineaire gegevensstructuren
  • Hiërarchische gegevensstructuren
• Algoritmen in Java
  • Sorteeralgoritmen
  • Algoritmen zoeken

Datastructuren in Java

Een datastructuur is een manier om gegevens op een computer op te slaan en te ordenen, zodat deze efficiënt kunnen worden gebruikt. Het biedt een manier om grote hoeveelheden gegevens efficiënt te beheren. En efficiënte datastructuren zijn de sleutel tot het ontwerpen van efficiënte algoritmen.

Inin dit ‘Datastructuren en algoritmen in Java’-artikel gaan we in op basisdatastructuren zoals:

• Lineaire gegevensstructuren
  • Gekoppelde lijst
  • Stapels
  • Wachtrijen

• Hiërarchische gegevensstructuren
  • Binaire bomen
  • Enorm veel
  • Hash-tabellen

Laten we ze allemaal eens bekijken.

Lineaire gegevensstructuren in Java

Lineaire datastructuren in zijn degenen waarvan de elementen opeenvolgend zijn en zodanig geordend dat: er maar één is eerste element en heeft er maar één volgende element , er is maar een laatste element en heeft er maar één vorig element , terwijl alle andere elementen een De volgende en een vorige element.

Arrays

Een array is een lineaire datastructuurvertegenwoordigt een groep vergelijkbare elementen, toegankelijk via index. De grootte van een array moet worden opgegeven voordat gegevens worden opgeslagen. Hieronder staan ​​de eigenschappen van een array:

• Elk element in een array is van hetzelfde gegevenstype en heeft dezelfde grootte
• Elementen van de array worden opgeslagen op aangrenzende geheugenlocaties waarbij het eerste element begint bij de kleinste geheugenlocatie
• Elementen van de array zijn willekeurig toegankelijk
• De gegevensstructuur van de array is niet volledig dynamisch

Bijvoorbeeld , willen we misschien dat een videogame de top tien scores voor die game bijhoudt. In plaats van tien verschillende variabelen voor deze taak zouden we een enkele naam kunnen gebruiken voor de hele groep en indexnummers kunnen gebruiken om te verwijzen naar de hoge scores in die groep.

Gekoppelde lijst

NAAR is een lineaire gegevensstructuur met de verzameling van meerdere knooppunten, waarbij each element slaat zijn eigen data op en een pointer naar de locatie van het volgende element. De laatste schakel in een gekoppelde lijst verwijst naar null, wat het einde van de ketting aangeeft. Een element in een gekoppelde lijst wordt een genoemd knooppunt . Het eerste knooppunt heet de hoofd .Het laatste knooppunt wordt genoemdde staart .

Typen gekoppelde lijst

Enkelvoudig gekoppelde lijst (unidirectioneel)

Dubbel gekoppelde lijst (bidirectioneel)

Circulaire gekoppelde lijst

Hier is een eenvoudig voorbeeld: Stel je een gekoppelde lijst voor als een ketting van paperclips die aan elkaar zijn gekoppeld. U kunt eenvoudig een andere paperclip aan de boven- of onderkant toevoegen. Het is zelfs snel om er een in het midden in te voegen. Het enige dat u hoeft te doen, is de ketting in het midden los te koppelen, de nieuwe paperclip toe te voegen en vervolgens de andere helft weer vast te maken. Een gekoppelde lijst is vergelijkbaar.

Stapels

Stapel, een abstracte datastructuur, is een verzameling van voorwerpen die worden geplaatst en verwijderd volgens de last-in-first-out (LIFO) beginsel. Objecten kunnen op elk moment in een stapel worden ingevoegd, maar alleen het meest recent ingevoegde (dat wil zeggen, 'laatste') object kan op elk moment worden verwijderd.Hieronder staan ​​de eigenschappen van een stapel:

• Het is een geordende lijst waarininvoegen en verwijderen kan alleen worden uitgevoerd aan één uiteinde dat de top
• Recursieve gegevensstructuur met een verwijzing naar het bovenste element
• Volgt de last-in-first-out (LIFO) beginsel
• Ondersteunt twee meest fundamentele methoden
  • push (e): Plaats element e, naar de bovenkant van de stapel
  • pop (): Verwijder het bovenste element op de stapel en plaats het terug

Praktische voorbeelden van de stapel zijn onder meer het omkeren van een woord,om de juistheid van te controleren haakjesvolgorde,het implementeren van back-functionaliteit in browsers en nog veel meer.

Wachtrijen

zijn ook een ander type abstracte gegevensstructuur. In tegenstelling tot een stapel is de wachtrij een verzameling objecten die worden ingevoegd en verwijderd volgens de first-in-first-out (FIFO) beginsel. Dat wil zeggen dat elementen op elk moment kunnen worden ingevoegd, maar alleen het element dat het langst in de wachtrij heeft gestaan, kan op elk moment worden verwijderd.Hieronder staan ​​de eigenschappen van een wachtrij:

• Vaak aangeduid als de als eerste erin, als eerste eruit lijst
• Ondersteunt twee meest fundamentele methoden
  • enqueue (e): element e invoegen, op de achter van de wachtrij
  • dequeue (): Verwijder het element uit het voorkant van de wachtrij

Wachtrijen worden gebruikt in deasynchrone gegevensoverdracht tussen twee processen, CPU-planning, schijfplanning en andere situaties waarin bronnen worden gedeeld door meerdere gebruikers en geserveerd op basis van wie het eerst komt, het eerst op de server. De volgende stap in dit ‘Datastructuren en algoritmen in Java’-artikel, hebben we hiërarchische datastructuren.

Hiërarchische gegevensstructuren in Java

Binaire boom

Binary Tree is eenhiërarchische boom datastructuren waarin elk knooppunt heeft maximaal twee kinderen , waarnaar wordt verwezen als de links kind en de juiste kind . Elke binaire boom heeft de volgende groepen knooppunten:

• Root Node: het is het bovenste knooppunt en wordt vaak het hoofdknooppunt genoemdomdat alle andere knooppunten vanaf de root kunnen worden bereikt
• Linker subboom, die ook een binaire boom is
• Rechter subboom, die ook een binaire boom is

Hieronder staan ​​de eigenschappen van een binaire boom:

• Een binaire boom kan op twee manieren worden doorlopen:
  • Diepte eerste verplaatsing : In-order (Left-Root-Right), Preorder (Root-Left-Right) en Postorder (Left-Right-Root)
  • Breedte eerste traversal : Level Order Traversal
• Tijdscomplexiteit van Tree Traversal: O (n)
• Het maximale aantal knooppunten op niveau ‘l’ = 2^l-1.

Toepassingen van binaire bomen zijn onder meer:

• Wordt gebruikt in veel zoekapplicaties waarbij voortdurend gegevens worden ingevoerd / verlaten
• Als een workflow voor het samenstellen van digitale afbeeldingen voor visuele effecten
• Gebruikt in bijna elke router met hoge bandbreedte voor het opslaan van routertabellen
• Ook gebruikt in draadloze netwerken en geheugentoewijzing
• Gebruikt in compressie-algoritmen en nog veel meer

Binaire hoop

Binary Heap is een completebinaire boom, die beantwoordt aan de eigenschap heap. Simpel gezegdis een variatie op een binaire boom met de volgende eigenschappen:

• Heap is een complete binaire boom: Van een boom wordt gezegd dat hij compleet is als alle niveaus, behalve mogelijk de diepste, compleet zijn. Tzijn eigendom van Binary Heap maakt het geschikt om te worden opgeslagen in een .
• Volgt heap-eigenschap: Een binaire hoop is ofwel een Min-hoop of een Max-Heap .
  • Min binaire hoop: F.of elk knooppunt in een heap, de waarde van het knooppunt is kleiner dan of gelijk aan waarden van de kinderen
  • Max. Binaire hoop: F.of elk knooppunt in een heap, de waarde van het knooppunt is groter dan of gelijk aan waarden van de kinderen

Populaire toepassingen van binaire heap zijn onder meerhet implementeren van efficiënte prioriteitswachtrijen, het efficiënt vinden van de k kleinste (of grootste) elementen in een array en nog veel meer.

Hash-tabellen

Stel je voor dat je een voorwerp en u wilt er een sleutel aan toewijzen om het zoeken heel gemakkelijk te maken. Om dat sleutel / waarde-paar op te slaan, kunt u een eenvoudige array gebruiken, zoals een datastructuur, waar sleutels (gehele getallen) direct kunnen worden gebruikt als een index om datawaarden op te slaan. In gevallen waarin de sleutels echter te groot zijn en niet rechtstreeks als index kunnen worden gebruikt, wordt een techniek genaamd hashing gebruikt.

Bij hashing worden de grote sleutels omgezet in kleine sleutels met behulp van hash-functies . De waarden worden vervolgens opgeslagen in een datastructuur genaamdnaar hashtabel. Een hashtabel is een datastructuur die een woordenboek ADT implementeert, een structuur die unieke sleutels aan waarden kan toewijzen.

Over het algemeen heeft een hashtabel twee hoofdcomponenten:

1. Emmer-array: Een bucket-array voor een hashtabel is een array A van grootte N, waarbij elke cel van A wordt gezien als een 'bucket', dat wil zeggen een verzameling sleutel-waardeparen. Het gehele getal N definieert de capaciteit van de array.
2. Hash-functie: Het is elke functie die elke sleutel k in onze kaart toewijst aan een geheel getal in het bereik [0, N & minus 1], waarbij N de capaciteit is van de bucket-array voor deze tabel.

Wanneer we objecten in een hashtabel plaatsen, is het mogelijk dat verschillende objecten dezelfde hashcode hebben. Dit heet een botsing . Om met botsingen om te gaan, zijn er technieken zoals chaining en open adressering.

Dit zijn dus enkele eenvoudige en meest gebruikte gegevensstructuren in Java. Nu u zich van elk hiervan bewust bent, kunt u ze gaan implementeren in uw . Hiermee hebben we het eerste deel van ’dit‘ Datastructuren en algoritmen in Java ’artikel afgerond. In het volgende deel gaan we meer leren overbasisalgoritmen en hoe ze te gebruiken in praktische toepassingen zoals sorteren en zoeken, verdeel en heers, hebzuchtige algoritmen, dynamisch programmeren.

Algoritmen in Java

Algoritmen werden van oudsher gebruikt als een hulpmiddel voor het oplossen van complexe wiskundige berekeningen, en zijn nauw verbonden met informatica, en in het bijzonder met datastructuren. Een algoritme is een reeks instructies die een manier beschrijft om een ​​specifiek probleem in een eindige tijd op te lossen. Ze worden op twee manieren weergegeven:

• Stroomdiagrammen - Het is eenvisuele weergave van de controlestroom van een algoritme
• Pseudocode - Hetis een tekstuele weergave van een algoritme dat de uiteindelijke broncode benadert

Opmerking: De prestaties van het algoritme worden gemeten op basis van tijdcomplexiteit en ruimtecomplexiteit. Meestal is de complexiteit van elk algoritme afhankelijk van het probleem en van het algoritme zelf.

Laten we de twee belangrijkste categorieën algoritmen in Java eens bekijken, namelijk:

• Sorteeralgoritmen in Java
• Algoritmen zoeken in Java

Sorteeralgoritmen in Java

Sorteeralgoritmen zijn algoritmen die elementen van een lijst in een bepaalde volgorde plaatsen. De meest gebruikte volgordes zijn numerieke volgorde en lexicografische volgorde. In dit ‘Datastructuren en algoritmen’ artikel laten we een paar sorteeralgoritmen onderzoeken.

Bellen sorteren in Java

Bubble Sort, vaak aangeduid als zinkende sortering, is het eenvoudigste sorteeralgoritme. Het stapt herhaaldelijk door de lijst om te worden gesorteerd, vergelijkt elk paar aangrenzende elementen en verwisselt ze als ze in de verkeerde volgorde staan.Bubble sort dankt zijn naam omdat het de elementen naar de bovenkant van de array filtert, zoals bellen die op water drijven.

Hier ispseudocode die het Bubble Sort-algoritme vertegenwoordigt (oplopende sorteercontext).

a [] is een array van grootte N begin BubbleSort (a []) declareer geheel getal i, j voor i = 0 tot N - 1 voor j = 0 tot N - i - 1 als a [j]> a [j + 1 ] ruil dan a [j], a [j + 1] end if end om voor een einde BubbleSort

Deze code rangschikt een eendimensionale reeks van N gegevensitems in oplopende volgorde. Een buitenste lus zorgt ervoor dat N-1 over de array gaat. Elke doorgang gebruikt een binnenste lus om data-items uit te wisselen, zodat het volgende kleinste data-item naar het begin van de array 'bubbelt'. Maar het probleem is dat het algoritme één hele doorgang nodig heeft zonder enige ruil om te weten dat de lijst is gesorteerd.

Slechtste en gemiddelde casustijdcomplexiteit: O (n * n). Het ergste geval doet zich voor wanneer een array omgekeerd wordt gesorteerd.

Best Case Time Complexiteit: Aan). Het beste geval doet zich voor wanneer een array al is gesorteerd.

Selectie Sorteren in Java

Selectie sorteren is een combinatie van zowel zoeken als sorteren. Het algoritme sorteert een array door herhaaldelijk het minimumelement te vinden (rekening houdend met oplopende volgorde) van het ongesorteerde deel en dit op een juiste positie in de array te plaatsen.

Hier is de pseudocode die het selectiesorteeralgoritme vertegenwoordigt (oplopende sorteercontext).

a [] is een array van grootte N begin SelectionSort (a []) voor i = 0 tot n - 1 / * stel het huidige element in als minimum * / min = i / * zoek het minimumelement * / voor j = i + 1 naar n als lijst [j]
Zoals u uit de code kunt opmaken, is het aantal keren dat de sortering door de array gaat één minder dan het aantal items in de array. De binnenste lus vindt de volgende kleinste waarde en de buitenste lus plaatst die waarde op de juiste locatie. Selectie sorteren maakt nooit meer dan O (n) swaps en kan handig zijn als het schrijven naar het geheugen een kostbare bewerking is.
 Tijdscomplexiteit: Aan2) aangezien er twee geneste lussen zijn.
 Extra ruimte: Of (1).
 Invoegsortering in Java 
Invoegsortering is een eenvoudig sorteeralgoritme dat door de lijst herhaalt door één invoerelement tegelijk te verbruiken en de uiteindelijke gesorteerde array samenstelt. Het is heel eenvoudig en effectiever bij kleinere gegevenssets. Het is een stabiele en in-place sorteertechniek.
python __init__ klasse
Hier is de pseudocode die het invoegsorteeralgoritme vertegenwoordigt (oplopende sorteercontext).
a [] is een array van grootte N begin InsertionSort (a []) voor i = 1 tot N key = a [i] j = i - 1 while (j> = 0 en a [j]> key0 a [j + 1] = x [j] j = j - 1 einde terwijl a [j + 1] = sleutel einde voor einde InsertionSort
Zoals je kunt opmaken uit de code, het algoritme voor invoegingverwijdert een element uit de invoergegevens, zoekt de locatie waar het hoort in de gesorteerde lijst en voegt het daar in. Het herhaalt zich totdat er geen invoerelementen ongesorteerd blijven.
 Beste geval: Het beste geval is wanneer de invoer een array is die al is gesorteerd. In dit geval heeft invoegsortering een lineaire looptijd (d.w.z. & Theta (n)).
 Het slechtste geval:  De eenvoudigste invoer in het slechtste geval is een array die in omgekeerde volgorde is gesorteerd.
 QuickSort in Java 
Quicksort-algoritme is een snel, recursief, niet-stabiel sorteeralgoritme dat werkt volgens het verdeel en heersprincipe. Het kiest een element als draaipunt en verdeelt de gegeven array rond dat gekozen draaipunt.
 Stappen om Snel sorteren te implementeren:  
 
Kies een geschikt 'draaipunt'.
Verdeel de lijsten in twee lijstenop basis van dit scharnierelement. Elk element dat kleiner is dan het pivot-element wordt in de linkerlijst geplaatst en elk element dat groter is, wordt in de rechterlijst geplaatst. Als een element gelijk is aan het pivot-element, kan het in elke lijst worden opgenomen. Dit wordt de partitiebewerking genoemd.
Sorteer elk van de kleinere lijsten recursief. 
Hier is de pseudocode die het Quicksort-algoritme vertegenwoordigt.
QuickSort (A als array, laag als int, hoog als int) {if (low
In de bovenstaande pseudocode, partitie () functie voert partitie bewerking uit en Snel sorteren() functie roept herhaaldelijk de partitiefunctie aan voor elke kleinere gegenereerde lijst. De complexiteit van quicksort in het gemiddelde geval is & Theta (n log (n)) en in het ergste geval is & Theta (n2).
 Samenvoegen Sorteren in Java 
Mergesort is een snel, recursief, stabiel sorteeralgoritme dat ook werkt volgens het verdeel en heersprincipe. Net als bij quicksort, verdeelt merge sort de lijst met elementen in twee lijsten. Deze lijsten worden onafhankelijk gesorteerd en vervolgens gecombineerd. Bij het samenvoegen van de lijsten worden de elementen op de juiste plaats in de lijst ingevoegd (of samengevoegd).
Hier is de pseudocode die het samenvoegsorteeralgoritme vertegenwoordigt.
procedure MergeSort (a as array) if (n == 1) retourneert een var l1 als array = a [0] ... a [n / 2] var l2 als array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) einde procedure procedure samenvoegen (a als array, b als array) var c als array terwijl (a en b elementen hebben) if ( a [0]> b [0]) voeg b [0] toe aan het einde van c verwijder b [0] van b anders voeg a [0] toe aan het einde van c verwijder a [0] van een einde if end while while (a heeft elementen) voeg a [0] toe aan het einde van c verwijder a [0] van een einde terwijl (b heeft elementen) voeg b [0] toe aan het einde van c verwijder b [0] van b einde terwijl terug c einde procedure
 samenvoegen () functie verdeelt de lijst in twee, calls samenvoegen () op deze lijsten afzonderlijk en combineert ze vervolgens door ze als parameters naar de merge () -functie te sturen.Het algoritme heeft een complexiteit van O (n log (n)) en heeft een breed scala aan toepassingen.
 Heap Sorteren in Java 
Heapsort is een op vergelijkingen gebaseerd sorteeralgoritmeBinaire Heap-gegevensstructuur. Je kunt het zien als een verbeterde versie f selectie sorteren, waarhet verdeelt zijn invoer in een gesorteerd en een ongesorteerd gebied, en het verkleint iteratief het ongesorteerde gebied door het grootste element te extraheren en dat naar het gesorteerde gebied te verplaatsen.
 Stappen om Quicksort te implementeren (in oplopende volgorde): 
Bouw een maximale heap met de sorteerarray
Op dit puntt, wordt het grootste item opgeslagen in de root van de heap. Vervang het door het laatste item van de hoop en verminder de grootte van de hoop met 1. Heapify tenslotte de wortel van de boom
Herhaal de bovenstaande stappen totdat de grootte van de heap groter is dan 1
Hier is de pseudocode die het Heap Sort-algoritme vertegenwoordigt.
Heapsort (a as array) voor (i = n / 2 - 1) tot i> = 0 heapify (a, n, i) voor i = n-1 tot 0 swap (a [0], a [i]) heapify (a, i, 0) einde voor einde voor heapify (a as array, n as int, i as int) grootste = i // Initialiseer grootste als wortel int l eft = 2 * i + 1 // links = 2 * i + 1 int rechts = 2 * i + 2 // rechts = 2 * i + 2 if (links a [grootste]) grootste = links if (rechts a [grootste]) grootste = rechts if (grootste! = I) swap ( a [i], A [grootste]) Heapify (a, n, grootste) end heapify
Afgezien van deze zijn er andere sorteeralgoritmen die niet zo bekend zijn, zoals Introsort, Counting Sort, enz. Laten we verder gaan met de volgende reeks algoritmen in dit artikel ‘Datastructuren en algoritmen’, laten we de zoekalgoritmen onderzoeken.
 Algoritmen zoeken in Java 
Zoeken is een van de meest voorkomende en vaak uitgevoerde acties in reguliere zakelijke applicaties. Zoekalgoritmen zijn algoritmen voor het vinden van een item met gespecificeerde eigenschappen in een verzameling items. Laten we eens kijken naar twee van de meest gebruikte zoekalgoritmen.
 Lineair zoekalgoritme in Java 
Lineair zoeken of sequentieel zoeken is het eenvoudigste zoekalgoritme. Het omvat het sequentieel zoeken naar een element in de gegeven datastructuur totdat het element is gevonden of het einde van de structuur is bereikt. Als het element wordt gevonden, wordt de locatie van het item geretourneerd, anders retourneert het algoritme NULL.
Hier is de pseudocode die Lineair zoeken in Java vertegenwoordigt:
procedure linear_search (a [], waarde) voor i = 0 tot n-1 als a [i] = waarde druk dan 'Gevonden' af return i end als print 'Niet gevonden' einde voor einde linear_search
Het is eenbrute-force-algoritme.Hoewel het zeker de eenvoudigste is, is het zeker niet de meest voorkomende, vanwege zijn inefficiëntie. Tijdscomplexiteit van lineair zoeken is AAN) .
 Binair zoekalgoritme in Java 
Binair zoeken, ook wel logaritmisch zoeken genoemd, is een zoekalgoritme dat de positie van een doelwaarde binnen een reeds gesorteerde array vindt. Het verdeelt de invoercollectie in gelijke helften en het item wordt vergeleken met het middelste element van de lijst. Als het element wordt gevonden, eindigt de zoekopdracht daar. Anders gaan we door met het zoeken naar het element door de juiste partitie van de array te verdelen en te selecteren, op basis van of het doelelement kleiner of groter is dan het middelste element.
Hier is de pseudocode die staat voor binair zoeken in Java:
Procedure binary_search een gesorteerde array n grootte van array x waarde die moet worden doorzocht lowerBound = 1 upperBound = n terwijl x niet gevonden if upperBound
Het zoeken wordt beëindigd wanneer de upperBound (onze pointer) voorbij lowerBound (laatste element) gaat, wat inhoudt dat we de hele array hebben doorzocht en het element niet aanwezig is.Het zijn de meest gebruikte zoekalgoritmen, voornamelijk vanwege de snelle zoektijd. De tijdcomplexiteit van de binaire zoekopdracht is AAN) wat een duidelijke verbetering is ten opzichte van de AAN) tijdcomplexiteit van Lineair zoeken.
Dit brengt ons bij het einde van dit ‘Datastructuren en algoritmen in Java’ artikel. Ik heb een van de meest fundamentele en belangrijke onderwerpen van Java behandeld.Ik hoop dat je duidelijk bent met alles wat in dit artikel met je is gedeeld.
  Zorg ervoor dat je zoveel mogelijk oefent en terugkeert naar je ervaring.   
 Bekijk de    door Edureka, een vertrouwd online leerbedrijf met een netwerk van meer dan 250.000 tevreden leerlingen verspreid over de hele wereld. We zijn hier om je te helpen bij elke stap op je reis, om naast deze Java-interviewvragen ook een curriculum te bedenken dat is ontworpen voor studenten en professionals die een Java-ontwikkelaar willen worden. 
 Heeft u een vraag voor ons? Vermeld het in het opmerkingengedeelte van deze ‘Datastructuren en algoritmen in Java’  artikel en we nemen zo snel mogelijk contact met u op.