Toppdatastrukturer och algoritmer i Java som du behöver veta

Om jag var tvungen att välja det enskilt viktigaste ämnet inom mjukvaruutveckling skulle det vara datastrukturer och algoritmer. Du kan tänka på det som det grundläggande verktyget som är tillgängligt för alla datorprogrammerare. Under programmeringen använder vi data struktur att lagra och organisera data, och algoritmer för att manipulera data i dessa strukturer. Den här artikeln innehåller en detaljerad genomgång av alla vanliga datastrukturer och algoritmer i så att läsarna kan bli väl rustade.

Nedan listas de ämnen som diskuteras i den här artikeln:

• Datastrukturer i Java
  • Linjära datastrukturer
  • Hierarkiska datastrukturer
• Algoritmer i Java
  • Sorteringsalgoritmer
  • Söker algoritmer

Datastrukturer i Java

En datastruktur är ett sätt att lagra och organisera data i en dator så att den kan användas effektivt. Det ger ett sätt att hantera stora mängder data effektivt. Och effektiva datastrukturer är nyckeln till att utforma effektiva algoritmer.

Cassandra kolumnfamilj vs bord

Idenna artikel 'Datastrukturer och algoritmer i Java' kommer vi att täcka grundläggande datastrukturer som:

• Linjära datastrukturer
  • Länkad lista
  • Travar
  • Köer

• Hierarkiska datastrukturer
  • Binära träd
  • Högar
  • Hash-tabeller

Låt oss kolla in var och en av dem.

Linjära datastrukturer i Java

Linjära datastrukturer i är de vars element är sekventiella och ordnade på ett sätt så att: det finns bara en första elementet och har bara en nästa element , det finns bara en sista elementet och har bara en föregående element , medan alla andra element har en Nästa och a tidigare element.

Arrayer

Ett array är en linjär datastrukturrepresenterar en grupp av liknande element, nås genom index. Storleken på en matris måste anges innan data lagras. Nedan listas egenskaper för en matris:

• Varje element i en matris har samma datatyp och har samma storlek
• Element i matrisen lagras vid angränsande minnesplatser där det första elementet börjar på den minsta minnesplatsen
• Element i matrisen kan slumpmässigt nås
• Arraydatastrukturen är inte helt dynamisk

Till exempel , vi kanske vill ha ett videospel för att hålla reda på de tio bästa poängen för det spelet. Snarare än att använda tio olika variabler för den här uppgiften kan vi använda ett enda namn för hela gruppen och använda indexnummer för att referera till de höga poängen i den gruppen.

Länkad lista

TILL är en linjär datastruktur med samlingen av flera noder, där each-elementet lagrar sina egna data och en pekare till platsen för nästa element. Den sista länken i en länkad lista pekar på null, vilket anger slutet på kedjan. Ett element i en länkad lista kallas a nod . Den första noden kallas huvud .Den sista noden kallasde svans .

Typer av länkad lista

Enskilt länkad lista (enkelriktad)

Dubbel länkad lista (dubbelriktad)

Cirkulär länkad lista

Här är ett enkelt exempel: Föreställ dig en länkad lista som en kedja av gem som är länkade ihop. Du kan enkelt lägga till ett annat gem i toppen eller botten. Det är till och med snabbt att sätta in en i mitten. Allt du behöver göra är att bara koppla bort kedjan i mitten, lägga till den nya gemen och sedan ansluta den andra halvan. En länkad lista är liknande.

Travar

Stack, en abstrakt datastruktur, är en samling av objekt som sätts in och tas bort enligt last-in-first-out (LIFO) princip. Objekt kan infogas i en stapel när som helst, men endast det senast infogade (det vill säga 'sista') objektet kan tas bort när som helst.Nedan listas egenskaper för en stack:

• Det är en ordnad lista därinsättning och radering kan endast utföras i ena änden som kallas topp
• Rekursiv datastruktur med en pekare till dess toppelement
• Följer last-in-first-out (LIFO) princip
• Stöder två mest grundläggande metoder
  • tryck (e): Sätt in element e, till toppen av stacken
  • pop (): Ta bort och sätt tillbaka toppelementet på stacken

Praktiska exempel på stacken inkluderar när du vänder ett ord,för att kontrollera riktigheten av parentessekvens,implementera tillbaka funktionalitet i webbläsare och många fler.

Köer

är också en annan typ av abstrakt datastruktur. Till skillnad från en stack är kön en samling objekt som sätts in och tas bort enligt först-in-först-ut (FIFO) princip. Det vill säga att element kan infogas när som helst, men bara det element som har stått längst i kön kan tas bort när som helst.Nedan listas egenskaper för en kö:

• Ofta kallad först in först ut lista
• Stöder två mest grundläggande metoder
  • enqueue (e): Sätt in element e, vid bak- av kön
  • dequeue (): Ta bort och returnera elementet från främre av kön

Köer används iasynkron överföring av data mellan två processer, CPU-schemaläggning, Diskplanering och andra situationer där resurser delas mellan flera användare och serveras på först till kvarn-serverbasis. Därefter i denna artikel 'Datastrukturer och algoritmer i Java' har vi hierarkiska datastrukturer.

Hierarkiska datastrukturer i Java

Binärt träd

Binary Tree är enhierarkiska träddatastrukturer där varje nod har högst två barn , som kallas vänster barn och den rätt barn . Varje binärt träd har följande grupper av noder:

• Root Node: Det är den översta noden och ofta kallad huvudnodeneftersom alla andra noder kan nås från roten
• Left Sub-Tree, som också är ett binärt träd
• Right Sub-Tree, som också är ett binärt träd

Nedan listas egenskaperna för ett binärt träd:

• Ett binärt träd kan passeras på två sätt:
  • Djup första genomgång : I ordning (Left-Root-Right), Pre-order (Root-Left-Right) och Postorder (Left-Right-Root)
  • Bredd First Traversal : Traversal på nivåorder
• Tidskomplexitet för trädkorsning: O (n)
• Det maximala antalet noder på nivå 'l' = 2^l-1.

Tillämpningar av binära träd inkluderar:

• Används i många sökapplikationer där data ständigt kommer in / lämnar
• Som ett arbetsflöde för att komponera digitala bilder för visuella effekter
• Används i nästan varje router med hög bandbredd för lagring av routerbord
• Används också för trådlöst nätverk och minnestilldelning
• Används i komprimeringsalgoritmer och många fler

Binär hög

Binary Heap är en komplettbinärt träd, som svarar på högegenskapen. Enkelt uttrycktär en variant av ett binärt träd med följande egenskaper:

• Heap är ett komplett binärt träd: Ett träd sägs vara komplett om alla dess nivåer, utom möjligen de djupaste, är kompletta. Thans egendom Binary Heap gör det lämpligt att lagras i en .
• Följer höghus: En binär hög är antingen a Min-hög eller a Max-Heap .
  • Min binär hög: Feller varje nod i en hög är nodens värde mindre än eller lika med barnens värden
  • Max binär hög: Feller varje nod i en hög är nodens värde större än eller lika med barnens värden

Populära applikationer av binär hög inkluderarimplementera effektiva prioritetsköer, hitta effektivt de k minsta (eller största) elementen i en matris och många fler.

överbelastning vs överordnad c ++

Hash-tabeller

Tänk dig att du har en objekt och du vill tilldela en nyckel till den för att göra sökningen mycket lätt. För att lagra det nyckel / värdeparet kan du använda en enkel matris som en datastruktur där nycklar (heltal) kan användas direkt som ett index för att lagra datavärden. I de fall där tangenterna är för stora och inte kan användas direkt som index används en teknik som kallas hashing.

I hashing konverteras de stora nycklarna till små nycklar med hjälp av hashfunktioner . Värdena lagras sedan i en datastruktur som kallastill hashbord. En hashtabell är en datastruktur som implementerar en ordlista-ADT, en struktur som kan mappa unika nycklar till värden.

I allmänhet har en hashtabell två huvudkomponenter:

1. Bucket Array: En hinkmatris för en hashtabell är en matris A i storlek N, där varje cell i A betraktas som en 'hink', det vill säga en samling nyckel-värdepar. Heltalet N definierar matrisens kapacitet.
2. Hash-funktion: Det är vilken funktion som helst som kartlägger varje tangent k i vår karta till ett heltal i intervallet [0, N & minus 1], där N är kapaciteten för skopmatrisen för denna tabell.

När vi lägger objekt i en hashtable är det möjligt att olika objekt kan ha samma hashkod. Detta kallas a kollision . För att hantera kollision finns tekniker som kedjning och öppen adressering.

Så det här är några grundläggande och oftast använda datastrukturer i Java. Nu när du är medveten om var och en av dessa kan du börja implementera dem i din . Med detta har vi slutfört den första delen av 'denna' Datastrukturer och algoritmer i Java 'artikel. I nästa del ska vi lära oss mer omgrundläggande algoritmer och hur man använder dem i praktiska tillämpningar som sortering och sökning, dela och erövra, giriga algoritmer, dynamisk programmering.

Algoritmer i Java

Historiskt används som ett verktyg för att lösa komplexa matematiska beräkningar, algoritmer är djupt kopplade till datavetenskap, och med datastrukturer i synnerhet. En algoritm är en sekvens av instruktioner som beskriver ett sätt att lösa ett specifikt problem under en begränsad tidsperiod. De representeras på två sätt:

• Flödesscheman - Det är envisuell representation av en algoritms kontrollflöde
• Pseudokod - Denär en textrepresentation av en algoritm som approximerar den slutliga källkoden

Notera: Algoritmens prestanda mäts utifrån tidskomplexitet och rymdkomplexitet. För det mesta är komplexiteten hos vilken algoritm som helst beroende av problemet och av algoritmen i sig.

Låt oss utforska de två huvudkategorierna av algoritmer i Java, vilka är:

• Sortera algoritmer i Java
• Söker algoritmer i Java

Sortera algoritmer i Java

Sorteringsalgoritmer är algoritmer som placerar element i en lista i en viss ordning. De mest använda beställningarna är numerisk ordning och lexikografisk ordning. I den här artikeln ”Datastrukturer och algoritmer” kan vi utforska några sorteringsalgoritmer.

Bubblesortering i Java

Bubblesortering, ofta kallad sjunkande sortering, är den enklaste sorteringsalgoritmen. Det går upprepade gånger genom listan som ska sorteras, jämför varje par intilliggande element och byter dem om de är i fel ordning.Bubblesorter får sitt namn eftersom det filtrerar bort elementen till toppen av matrisen, som bubblor som flyter på vatten.

Här ärpseudokod som representerar algoritmen för bubblasortering (stigande sorteringskontext).

a [] är en matris av storlek N börjar BubbleSort (a []) förklarar heltal i, j för i = 0 till N - 1 för j = 0 till N - i - 1 om a [j]> a [j + 1 ] byt sedan ut ett [j], ett [j + 1] slut om slut för att returnera ett slut BubbleSort

Den här koden beställer en endimensionell matris av N-dataposter i stigande ordning. En yttre slinga gör att N-1 passerar över matrisen. Varje pass använder en inre slinga för att utbyta dataobjekt så att nästa minsta dataobjekt 'bubblar' mot början av matrisen. Men problemet är att algoritmen behöver ett helt pass utan någon byte för att veta att listan är sorterad.

Värsta och genomsnittliga komplexitet i falltid: O (n * n). Det värsta fallet inträffar när en array omvänd sorteras.

Bästa falltidskomplexitet: På). Bästa fall inträffar när en matris redan är sorterad.

Urval Sortera i Java

Urvalsortering är en kombination av både sökning och sortering. Algoritmen sorterar en matris genom att upprepade gånger hitta minimielementet (med tanke på stigande ordning) från den osorterade delen och placera den på rätt plats i matrisen.

Här är pseudokod som representerar valssorteringsalgoritm (stigande sorteringskontext).

a [] är en matris av storlek N börjar SelectionSort (a []) för i = 0 till n - 1 / * ställa in aktuellt element som minimum * / min = i / * hitta minsta element * / för j = i + 1 till n om listan [j]
Som du kan förstå från koden är antalet gånger sorten passerar genom matrisen ett mindre än antalet objekt i matrisen. Den inre slingan hittar nästa minsta värde och den yttre slingan placerar det värdet på rätt plats. Urvalssortering gör aldrig mer än O (n) -byten och kan vara användbart när minnesskrivningen är en kostsam operation.
 Tidskomplexitet: På2) eftersom det finns två kapslade öglor.
 Hjälprum: Eller (1).
 Insättningssortering i Java 
Insertion Sort är en enkel sorteringsalgoritm som går igenom listan genom att konsumera ett inmatningselement åt gången och bygga den slutliga sorterade matrisen. Det är mycket enkelt och mer effektivt på mindre datamängder. Det är stabil och på plats sorteringsteknik.
Här är en pseudokod som representerar algoritmen för insättningssortering (stigande sorteringskontext).
a [] är en matris av storlek N börjar InsertionSort (a []) för i = 1 till N-tangent = a [i] j = i - 1 medan (j> = 0 och en [j]> tangent 0 a [j + 1] = x [j] j = j - 1 ände medan en [j + 1] = nyckeländ för slutet InsertionSort
Som du kan förstå från koden, infogningssorteringsalgoritmentar bort ett element från ingångsdata, hittar platsen det tillhör i den sorterade listan och infogar det där. Det upprepas tills inga ingångselement förblir osorterade.
 Bästa fall: Det bästa fallet är när input är en array som redan är sorterad. I detta fall har insättningssortering en linjär körtid (dvs. & Theta (n)).
 Värsta fall:  Den enklaste inmatningen i värsta fall är en matris sorterad i omvänd ordning.
 QuickSort i Java 
Quicksort-algoritmen är en snabb, rekursiv, icke-stabil sorteringsalgoritm som fungerar enligt delnings- och erövringsprincipen. Det väljer ett element som pivot och partitionerar den givna matrisen runt den valda pivoten.
 Steg för att implementera snabb sortering:  
 
Välj en lämplig 'pivot point'.
Dela upp listorna i två listorbaserat på detta pivotelement. Varje element som är mindre än pivotelementet placeras i den vänstra listan och varje element som är större placeras i den högra listan. Om ett element är lika med pivotelementet kan det gå i valfri lista. Detta kallas partitionsoperationen.
Sortera rekursivt var och en av de mindre listorna. 
Här är pseudokod som representerar Quicksort Algorithm.
QuickSort (A som array, låg som int, hög som int) {if (låg
I ovanstående pseudokod, dela() funktionen utför partition och Snabbsort () funktionen anropar upprepade gånger partitionsfunktionen för varje mindre lista som genereras. Komplexiteten hos quicksort i genomsnitt är & Theta (n log (n)) och i värsta fall är & Theta (n2).
 Slå samman sortering i Java 
Mergesort är en snabb, rekursiv, stabil sorteringsalgoritm som också fungerar efter delnings- och erövringsprincipen. I likhet med quicksort delar merge sort upp listan med element i två listor. Dessa listor sorteras oberoende och kombineras sedan. Under kombinationen av listorna infogas (eller slås samman) elementen på rätt plats i listan.
Här är en pseudokod som representerar Merge Sort Algorithm.
procedur MergeSort (a som array) om (n == 1) returnerar en var l1 som array = a [0] ... a [n / 2] var l2 som array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) returnera merge (l1, l2) slut procedur procedur merge (a som array, b som array) var c som array medan (a och b har element) om ( a [0]> b [0]) lägg till b [0] till slutet av c ta bort b [0] från b annars lägg till [0] till slutet av c ta bort [0] från ett slut om slut medan (a har element) lägg till en [0] i slutet av c ta bort [0] från en ände medan (b har element) lägg till b [0] till slutet av c ta bort b [0] från b-änden medan retur c avsluta proceduren
 mergesort () funktionen delar listan i två, samtal mergesort () på dessa listor separat och sedan kombinera dem genom att skicka dem som parametrar för att slå samman () -funktionen.Algoritmen har en komplexitet av O (n log (n)) och har ett brett spektrum av applikationer.
 Heapsortering i Java 
Heapsort är en jämförelsebaserad sorteringsalgoritmDatastruktur för binär hög. Du kan tänka på det som förbättrad version f urval sortera, varden delar sin ingång i en sorterad och en osorterad region, och den krymper iterativt den osorterade regionen genom att extrahera det största elementet och flytta det till det sorterade området.
 Steg för att implementera Quicksort (i ökande ordning): 
Bygg en maxhög med sorteringsmatrisen
Vid denna point, den största föremålet lagras i roten till högen. Byt ut det med det sista föremålet på högen och minska storleken på högen med 1. Slutligen, heapifiera roten till trädet
Upprepa stegen ovan tills högen är större än 1
Här är pseudokod som representerar Heap Sort Algorithm.
Heapsort (a som array) för (i = n / 2 - 1) till i> = 0 heapify (a, n, i) för i = n-1 till 0 swap (a [0], a [i]) heapify (a, i, 0) slut för slut för heapify (a som array, n som int, i som int) största = i // Initiera störst som root int l eft = 2 * i + 1 // vänster = 2 * i + 1 int höger = 2 * i + 2 // höger = 2 * i + 2 om (vänster a [största]) största = vänster om (höger a [största]) största = höger om (största! = I) swap ( a [i], A [största]) Heapify (a, n, största) slut heapify
Bortsett från dessa finns det andra sorteringsalgoritmer som inte är så kända som Introsort, Counting Sort osv. Om vi ​​går vidare till nästa uppsättning algoritmer i denna artikel 'Datastrukturer och algoritmer', låt oss utforska sökalgoritmer.
 Söker algoritmer i Java 
Sökning är en av de vanligaste och ofta utförda åtgärderna i vanliga affärsapplikationer. Sökalgoritmer är algoritmer för att hitta ett objekt med angivna egenskaper bland en samling objekt. Låt oss utforska två av de vanligaste sökalgoritmerna.
 Linjär sökalgoritm i Java 
Linjär sökning eller sekventiell sökning är den enklaste sökalgoritmen. Det innebär sekventiell sökning efter ett element i den angivna datastrukturen tills antingen elementet hittas eller slutet på strukturen har nåtts. Om elementet hittas returneras artikelns plats, annars returnerar algoritmen NULL.
Här är pseudokod som representerar linjär sökning i Java:
procedur linjärsökning (a [], värde) för i = 0 till n-1 om ett [i] = värde skriv ut 'Hittade' returnera i slut om utskrift 'hittades inte' slut för slut linjär_sökning
Det är enbrute-force algoritm.Även om det verkligen är det enklaste, är det definitivt inte det vanligaste på grund av dess ineffektivitet. Tidskomplexitet för linjär sökning är PÅ) .
 Binär sökalgoritm i Java 
Binär sökning, även känd som logaritmisk sökning, är en sökalgoritm som hittar positionen för ett målvärde i en redan sorterad matris. Den delar in insamlingen i lika stora halvor och objektet jämförs med mittelementet i listan. Om elementet hittas slutar sökningen där. Annars fortsätter vi att leta efter elementet genom att dela och välja lämplig partition av matrisen, baserat på om målelementet är mindre eller större än mittelementet.
Här är pseudokod som representerar binär sökning i Java:
Procedur binär_sök en sorterad matris n storlek på matris x värde som ska sökas lowerBound = 1 upperBound = n medan x inte hittas om upperBound
Sökningen avslutas när upperBound (vår pekare) går förbi lowerBound (sista element), vilket innebär att vi har sökt i hela arrayen och elementet inte finns.Det är de mest använda sökalgoritmerna främst på grund av dess snabba söktid. Tidskomplexiteten för den binära sökningen är PÅ) vilket är en markant förbättring av PÅ) tidskomplexitet för linjär sökning.
Fibonacci-serie c ++
Detta leder oss till slutet av denna artikel 'Datastrukturer och algoritmer i Java'. Jag har täckt ett av de mest grundläggande och viktiga ämnena i Java.Hoppas att du är tydlig med allt som har delats med dig i den här artikeln.
  Se till att du tränar så mycket som möjligt och återgår till din upplevelse.   
 Kolla in    av Edureka, ett pålitligt online-lärande företag med ett nätverk av mer än 250 000 nöjda elever spridda över hela världen. Vi är här för att hjälpa dig med varje steg på din resa, för att bli en förutom de här Java-intervjufrågorna, kommer vi med en läroplan som är utformad för studenter och yrkesverksamma som vill vara Java-utvecklare. 
 Har du en fråga till oss? Vänligen nämna det i kommentarsektionen i detta ”Datastrukturer och algoritmer i Java”  artikeln så återkommer vi till dig så snart som möjligt.