Struktur Data & Algoritma Teratas di Java Yang Perlu Anda Ketahui

Jika saya harus memilih satu topik terpenting dalam pengembangan perangkat lunak, itu adalah struktur data dan algoritme. Anda dapat menganggapnya sebagai alat dasar yang tersedia untuk setiap pemrogram komputer. Saat memprogram, kami menggunakan struktur data untuk menyimpan dan mengatur data, dan algoritma untuk memanipulasi data dalam struktur tersebut. Artikel ini berisi tinjauan mendetail dari semua struktur data dan algoritme umum di untuk memungkinkan pembaca menjadi diperlengkapi dengan baik.

Di bawah ini adalah topik yang dibahas dalam artikel ini:

• Struktur Data di Java
  • Struktur Data Linear
  • Struktur Data Hierarki
• Algoritma di Jawa
  • Mengurutkan Algoritma
  • Algoritma Pencarian

Struktur Data di Java

Struktur data adalah cara menyimpan dan mengatur data dalam komputer agar dapat digunakan secara efisien. Ini menyediakan sarana untuk mengelola data dalam jumlah besar secara efisien. Dan struktur data yang efisien adalah kunci untuk merancang algoritma yang efisien.

Diartikel 'Struktur Data dan Algoritma di Java' ini, kita akan membahas struktur data dasar seperti:

• Struktur Data Linear
  • Daftar Tertaut
  • Tumpukan
  • Antrian

• Struktur Data Hierarki
  • Pohon Biner
  • Tumpukan
  • Tabel Hash

Mari kita lihat masing-masing.

Struktur Data Linier di Java

Struktur data linier dalam adalah mereka yang elemen-elemennya berurutan dan diurutkan sedemikian rupa sehingga: hanya ada satu elemen pertama dan hanya memiliki satu elemen berikutnya , hanya ada satu elemen terakhir dan hanya memiliki satu elemen sebelumnya , sedangkan semua elemen lainnya memiliki a lanjut dan a sebelumnya elemen.

Array

Sebuah Himpunan adalah struktur data liniermewakili sekelompok elemen serupa, diakses oleh indeks. Ukuran larik harus disediakan sebelum menyimpan data. Di bawah ini adalah properti dari sebuah array:

• Setiap elemen dalam array memiliki tipe data yang sama dan memiliki ukuran yang sama
• Elemen array disimpan di lokasi memori yang berdekatan dengan elemen pertama dimulai dari lokasi memori terkecil
• Elemen-elemen array dapat diakses secara acak
• Struktur data array tidak sepenuhnya dinamis

Sebagai contoh , kami mungkin ingin video game melacak sepuluh skor teratas untuk game itu. Daripada menggunakan sepuluh berbeda variabel untuk tugas ini, kita dapat menggunakan satu nama untuk seluruh kelompok dan menggunakan nomor indeks untuk merujuk pada skor tinggi dalam kelompok itu.

Daftar Tertaut

UNTUK adalah struktur data linier dengan kumpulan beberapa node, di mana each elemen menyimpan datanya sendiri dan penunjuk ke lokasi elemen berikutnya. Tautan terakhir dalam daftar tertaut menunjuk ke nol, yang menunjukkan akhir rantai. Elemen dalam daftar tertaut disebut a simpul . Node pertama disebut kepala .Node terakhir dipanggilitu ekor .

pertanyaan wawancara pemuat kelas java

Jenis Daftar Tertaut

Daftar Tertaut Tunggal (Uni-Directional)

Daftar Tertaut Ganda (Dua Arah)

Daftar Tertaut Melingkar

Berikut contoh sederhananya: Bayangkan daftar yang ditautkan seperti rantai penjepit kertas yang saling terkait. Anda dapat dengan mudah menambahkan penjepit kertas lain ke atas atau bawah. Bahkan dengan cepat memasukkan satu di tengah. Yang harus Anda lakukan hanyalah melepaskan rantai di tengah, menambahkan penjepit kertas baru, lalu menghubungkan kembali setengah lainnya. Daftar tertaut serupa.

Tumpukan

Tumpukan, struktur data abstrak, adalah kumpulan benda yang dimasukkan dan dihapus sesuai dengan last-in-first-out (LIFO) prinsip. Objek dapat disisipkan ke dalam tumpukan kapan saja, tetapi hanya objek yang paling terakhir dimasukkan (yaitu, 'terakhir') yang dapat dihapus kapan saja.Di bawah ini adalah properti dari tumpukan:

• Ini adalah daftar urutan di manapenyisipan dan penghapusan dapat dilakukan hanya pada satu ujung yang disebut puncak
• Struktur data rekursif dengan penunjuk ke elemen teratasnya
• Mengikuti last-in-first-out (LIFO) prinsip
• Mendukung dua metode paling mendasar
  • dorong (e): Masukkan elemen e, ke bagian atas tumpukan
  • pop (): Hapus dan kembalikan elemen teratas pada tumpukan

Contoh praktis tumpukan termasuk saat membalik kata,untuk memeriksa kebenaran tanda kurungurutan,menerapkan fungsionalitas kembali di browser dan banyak lagi.

Antrian

juga jenis lain dari struktur data abstrak. Tidak seperti tumpukan, antrian adalah kumpulan objek yang disisipkan dan dihapus sesuai dengan first-in-first-out (FIFO) prinsip. Artinya, elemen dapat disisipkan kapan saja, tetapi hanya elemen yang telah berada dalam antrean paling lama yang dapat dihapus kapan saja.Di bawah ini adalah properti antrian:

• Sering disebut sebagai file pertama masuk pertama keluar daftar
• Mendukung dua metode paling mendasar
  • enqueue (e): Masukkan elemen e, di belakang dari antrian
  • dequeue (): Hapus dan kembalikan elemen dari depan dari antrian

Antrian digunakan ditransfer data yang tidak sinkron antara dua proses, penjadwalan CPU, Penjadwalan Disk, dan situasi lain di mana sumber daya dibagi di antara banyak pengguna dan disajikan berdasarkan server yang datang pertama. Selanjutnya dalam artikel 'Struktur Data dan Algoritma di Java' ini, kami memiliki struktur data hierarki.

Struktur Data Hierarki di Java

Pohon Biner

Pohon Biner adalah astruktur data hierarki pohon di mana setiap node memiliki paling banyak dua anak , yang disebut sebagai anak kiri dan anak yang tepat . Setiap pohon biner memiliki grup node berikut:

• Root Node: Ini adalah node paling atas dan sering disebut sebagai node utamakarena semua node lain dapat dijangkau dari root
• Sub-Pohon Kiri, yang juga merupakan pohon biner
• Sub-Pohon Kanan, yang juga merupakan pohon biner

Di bawah ini adalah properti dari pohon biner:

• Pohon biner dapat dilintasi dengan dua cara:
  • Traversal Pertama Kedalaman : In-order (Left-Root-Right), Preorder (Root-Left-Right) dan Postorder (Left-Right-Root)
  • Breadth First Traversal : Level Order Traversal
• Kompleksitas Waktu dari Tree Traversal: O (n)
• Jumlah maksimum node pada level 'l' = 2^l-1.

Aplikasi pohon biner meliputi:

• Digunakan di banyak aplikasi pencarian di mana data terus-menerus masuk / keluar
• Sebagai alur kerja untuk mengkomposisikan gambar digital untuk efek visual
• Digunakan di hampir setiap router bandwidth tinggi untuk menyimpan tabel router
• Juga digunakan dalam jaringan nirkabel dan alokasi memori
• Digunakan dalam algoritma kompresi dan banyak lagi

Heap Biner

Biner Heap sudah lengkappohon biner, yang menjawab properti heap. Secara sederhana ituadalah variasi dari pohon biner dengan properti berikut:

• Heap adalah pohon biner lengkap: Sebuah pohon dikatakan lengkap jika semua tingkatannya, kecuali mungkin yang paling dalam, sudah lengkap. Tproperti Binary Heap miliknya membuatnya cocok untuk disimpan di file .
• Mengikuti properti heap: Biner Heap bisa berupa a Min-Heap atau a Max-Heap .
  • Min Biner Heap: Fatau setiap node di heap, nilai node adalah lebih rendah dari atau sama dengan nilai-nilai anak-anak
  • Max Biner Heap: Fatau setiap node di heap, nilai node tersebut adalah lebih dari atau sama dengan nilai-nilai anak-anak

Aplikasi populer dari tumpukan biner termasukmenerapkan antrian prioritas yang efisien, secara efisien menemukan k elemen terkecil (atau terbesar) dalam sebuah larik dan banyak lagi.

Tabel Hash

Bayangkan Anda memiliki file obyek dan Anda ingin menetapkan kunci untuk mempermudah pencarian. Untuk menyimpan pasangan kunci / nilai tersebut, Anda dapat menggunakan larik sederhana seperti struktur data di mana kunci (bilangan bulat) dapat digunakan secara langsung sebagai indeks untuk menyimpan nilai data. Namun, dalam kasus di mana kunci terlalu besar dan tidak dapat digunakan secara langsung sebagai indeks, teknik yang disebut hashing digunakan.

Dalam hashing, kunci besar diubah menjadi kunci kecil dengan menggunakan fungsi hash . Nilai tersebut kemudian disimpan dalam struktur data yang disebutuntuk tabel hash. Tabel hash adalah struktur data yang mengimplementasikan ADT kamus, struktur yang dapat memetakan kunci unik ke nilai.

Secara umum, tabel hash memiliki dua komponen utama:

1. Array Bucket: Larik keranjang untuk tabel hash adalah larik A dengan ukuran N, di mana setiap sel A dianggap sebagai 'wadah', yaitu kumpulan pasangan nilai kunci. Bilangan bulat N mendefinisikan kapasitas array.
2. Fungsi Hash: Ini adalah fungsi apa pun yang memetakan setiap kunci k di peta kita ke bilangan bulat dalam rentang [0, N & minus 1], di mana N adalah kapasitas larik keranjang untuk tabel ini.

Saat kita memasukkan objek ke dalam hashtable, ada kemungkinan objek yang berbeda mungkin memiliki kode hash yang sama. Ini disebut a tabrakan . Untuk mengatasi tabrakan, ada teknik seperti rantai dan pengalamatan terbuka.

Jadi, ini adalah beberapa struktur data dasar dan paling sering digunakan di Java. Sekarang setelah Anda mengetahui masing-masing ini, Anda dapat mulai menerapkannya di file . Dengan ini, kami telah menyelesaikan bagian pertama dari artikel 'Struktur Data dan Algoritma di Java' ini. Di bagian selanjutnya, kita akan belajar tentangalgoritma dasar dan bagaimana menggunakannya dalam aplikasi praktis seperti menyortir dan mencari, membagi dan menaklukkan, algoritma rakus, pemrograman dinamis.

Algoritma di Jawa

Secara historis digunakan sebagai alat untuk memecahkan komputasi matematika yang kompleks, algoritme sangat terkait dengan ilmu komputer, dan dengan struktur data pada khususnya. Algoritme adalah urutan instruksi yang menggambarkan cara memecahkan masalah tertentu dalam periode waktu yang terbatas. Mereka diwakili dalam dua cara:

• Diagram alir - Ini adalah sebuahrepresentasi visual dari aliran kontrol algoritma
• Pseudocode - Saya tadalah representasi tekstual dari algoritme yang mendekati kode sumber akhir

catatan: Performa algoritma diukur berdasarkan kompleksitas waktu dan kompleksitas ruang. Sebagian besar, kerumitan algoritme apa pun bergantung pada masalah dan algoritme itu sendiri.

Mari kita pelajari dua kategori utama dari algoritma di Java, yaitu:

• Mengurutkan Algoritma di Java
• Mencari Algoritma di Java

Mengurutkan Algoritma di Java

Algoritme pengurutan adalah algoritme yang menempatkan elemen-elemen daftar dalam urutan tertentu. Urutan yang paling umum digunakan adalah urutan numerik dan urutan leksikografis. Dalam artikel ‘Struktur Data dan Algoritme’ ini, mari kita pelajari beberapa algoritme pengurutan.

Bubble Sort di Java

Bubble Sort, sering disebut sebagai sinking sort, adalah algoritme pengurutan yang paling sederhana. Ini berulang kali melangkah melalui daftar untuk diurutkan, membandingkan setiap pasangan elemen yang berdekatan dan menukar mereka jika berada dalam urutan yang salah.Bubble sort mendapatkan namanya karena menyaring elemen ke atas larik, seperti gelembung yang mengapung di atas air.

Ini diapseudocode mewakili Algoritma Bubble Sort (konteks urutan naik).

a [] adalah larik berukuran N mulai BubbleSort (a []) menyatakan bilangan bulat i, j untuk i = 0 hingga N - 1 untuk j = 0 hingga N - i - 1 jika a [j]> a [j + 1 ] lalu tukar a [j], a [j + 1] end jika end untuk mengembalikan BubbleSort akhir

Kode ini mengurutkan array satu dimensi dari N item data ke dalam urutan menaik. Lingkaran luar membuat N-1 melewati array. Setiap lulus menggunakan loop dalam untuk bertukar item data sedemikian rupa sehingga item data terkecil berikutnya 'menggelembung' ke awal larik. Tetapi masalahnya adalah algoritme memerlukan satu jalur penuh tanpa pertukaran apa pun untuk mengetahui bahwa daftar tersebut diurutkan.

Kompleksitas Waktu Kasus Terburuk dan Rata-rata: O (n * n). Kasus terburuk terjadi ketika array diurutkan terbalik.

Kompleksitas Waktu Kasus Terbaik: Di). Kasus terbaik terjadi ketika array sudah diurutkan.

Sortir Pilihan di Jawa

Penyortiran pilihan adalah kombinasi dari pencarian dan penyortiran. Algoritme mengurutkan sebuah array dengan berulang kali menemukan elemen minimum (dengan mempertimbangkan urutan naik) dari bagian yang tidak disortir dan meletakkannya pada posisi yang tepat dalam array.

transformasi yang terhubung dan tidak terhubung di informatica

Berikut ini pseudocode yang mewakili Algoritme Pengurutan Pilihan (konteks urutan naik).

a [] adalah larik berukuran N mulai SelectionSort (a []) untuk i = 0 hingga n - 1 / * tetapkan elemen saat ini sebagai minimum * / min = i / * temukan elemen minimum * / untuk j = i + 1 ke n jika daftar [j]
Seperti yang dapat Anda pahami dari kode, frekuensi pengurutan melewati larik kurang dari satu kali jumlah item dalam larik. Perulangan dalam menemukan nilai terkecil berikutnya dan perulangan luar menempatkan nilai itu ke lokasi yang tepat. Jenis pilihan tidak pernah menghasilkan lebih dari O (n) swap dan dapat berguna ketika penulisan memori adalah operasi yang mahal.
 Kompleksitas Waktu: Di2) karena ada dua loop bersarang.
 Ruang Bantu: Atau (1).
 Sortasi Penyisipan di Jawa 
Insertion Sort adalah algoritme pengurutan sederhana yang melakukan iterasi melalui daftar dengan menggunakan satu elemen masukan pada satu waktu dan membangun larik terurut terakhir. Ini sangat sederhana dan lebih efektif pada kumpulan data yang lebih kecil. Ini adalah teknik penyortiran yang stabil dan di tempat.
Berikut ini pseudocode yang mewakili Algoritme Sortir Penyisipan (konteks urutan menaik).
a [] adalah larik berukuran N mulai InsertionSort (a []) untuk i = 1 hingga N kunci = a [i] j = i - 1 sedangkan (j> = 0 dan a [j]> kunci0 a [j + 1] = x [j] j = j - 1 ujung sedangkan a [j + 1] = ujung tombol untuk penyisipan akhir
Seperti yang dapat Anda pahami dari kode, algoritma sortir penyisipanmenghapus satu elemen dari data input, menemukan lokasinya dalam daftar yang diurutkan dan menyisipkannya di sana. Ini berulang sampai tidak ada elemen masukan tetap tidak diurutkan.
 Kasus terbaik: Kasus terbaik adalah ketika input berupa larik yang sudah diurutkan. Dalam kasus ini semacam penyisipan memiliki waktu berjalan linier (yaitu, & Theta (n)).
 Kasus terburuk:  Masukan kasus terburuk yang paling sederhana adalah larik yang diurutkan dalam urutan terbalik.
 QuickSort di Java 
Algoritme Quicksort adalah algoritme pengurutan cepat, rekursif, dan tidak stabil yang bekerja berdasarkan prinsip divide and conquer. Ini mengambil elemen sebagai pivot dan mempartisi larik yang diberikan di sekitar pivot yang dipilih.
 Langkah-langkah untuk menerapkan Quick sort:  
 
Pilih 'titik pivot' yang sesuai.
Bagilah daftar menjadi dua daftarberdasarkan elemen pivot ini. Setiap elemen yang lebih kecil dari elemen pivot ditempatkan di daftar kiri dan setiap elemen yang lebih besar ditempatkan di daftar kanan. Jika sebuah elemen sama dengan elemen pivot maka elemen tersebut dapat masuk ke daftar mana pun. Ini disebut operasi partisi.
Urutkan setiap daftar yang lebih kecil secara rekursif. 
Berikut ini pseudocode yang mewakili Algoritma Quicksort.
QuickSort (A sebagai array, low as int, high as int) {if (low
Dalam pseudocode di atas, partisi () fungsi melakukan operasi partisi dan Quicksort () fungsi berulang kali memanggil fungsi partisi untuk setiap daftar kecil yang dihasilkan. Kompleksitas quicksort dalam kasus rata-rata adalah & Theta (n log (n)) dan dalam kasus terburuk adalah & Theta (n2).
 Gabungkan Sortir di Jawa 
Mergesort adalah algoritma pengurutan yang cepat, rekursif, dan stabil yang juga bekerja dengan prinsip divide and conquer. Mirip dengan quicksort, merge sort membagi daftar elemen menjadi dua daftar. Daftar ini diurutkan secara independen dan kemudian digabungkan. Selama kombinasi daftar, elemen disisipkan (atau digabungkan) di tempat yang tepat dalam daftar.
Berikut ini pseudocode yang mewakili Algoritma Pengurutan Gabung.
prosedur MergeSort (a sebagai array) if (n == 1) mengembalikan var l1 sebagai array = a [0] ... a [n / 2] var l2 sebagai array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) prosedur akhir merge (a sebagai array, b sebagai array) var c sebagai array sedangkan (a dan b memiliki elemen) if ( a [0]> b [0]) tambahkan b [0] di akhir c hapus b [0] dari b lain tambahkan [0] di akhir c hapus [0] dari akhir jika berakhir sementara (a memiliki elemen) tambahkan a [0] ke akhir c hapus a [0] dari akhir sementara (b memiliki elemen) tambahkan b [0] ke akhir c hapus b [0] dari b akhir saat kembali c prosedur akhir
 mergesort () Fungsi membagi daftar menjadi dua, panggilan mergesort () pada daftar ini secara terpisah dan kemudian menggabungkannya dengan mengirimkannya sebagai parameter ke fungsi merge ().Algoritma ini memiliki kompleksitas O (n log (n)) dan memiliki aplikasi yang luas.
 Urutan Heap di Java 
Heapsort adalah algoritma pengurutan berbasis perbandinganStruktur data Heap Biner. Anda dapat menganggapnya sebagai jenis pemilihan versi f yang ditingkatkan, di manaitu membagi masukannya menjadi wilayah yang diurutkan dan yang tidak disortir, dan secara berulang menyusutkan wilayah yang tidak disortir dengan mengekstrak elemen terbesar dan memindahkannya ke wilayah yang diurutkan.
 Langkah-langkah untuk menerapkan Quicksort (dalam urutan meningkat): 
Bangun tumpukan maksimal dengan array penyortiran
Saat init, item terbesar disimpan di root heap. Gantilah dengan item terakhir dari heap dan kurangi ukuran heap sebanyak 1. Terakhir, lakukan heap pada root pohon
Ulangi langkah-langkah di atas sampai ukuran heap lebih besar dari 1
Berikut ini pseudocode yang merepresentasikan Heap Sort Algorithm.
Heapsort (a sebagai larik) untuk (i = n / 2 - 1) hingga i> = 0 heapify (a, n, i) untuk i = n-1 hingga 0 swap (a [0], a [i]) heapify (a, i, 0) akhir untuk akhir untuk heapify (a sebagai array, n sebagai int, i sebagai int) terbesar = i // Inisialisasi terbesar sebagai root int l eft = 2 * i + 1 // left = 2 * i + 1 int kanan = 2 * i + 2 // kanan = 2 * i + 2 if (kiri a [terbesar]) terbesar = kiri jika (kanan a [terbesar]) terbesar = kanan jika (terbesar! = I) tukar ( a [i], A [terbesar]) Heapify (a, n, terbesar) ujung heapify
Selain itu, ada algoritme pengurutan lain yang tidak begitu terkenal seperti, Introsort, Counting Sort, dll. Beralih ke kumpulan algoritme berikutnya di artikel ‘Struktur Data dan Algoritme’ ini, mari kita pelajari algoritme penelusuran.
 Mencari Algoritma di Java 
Pencarian adalah salah satu tindakan yang paling umum dan sering dilakukan dalam aplikasi bisnis biasa. Algoritme penelusuran adalah algoritme untuk menemukan item dengan properti tertentu di antara sekumpulan item. Mari kita pelajari dua algoritme penelusuran yang paling umum digunakan.
 Algoritma Pencarian Linier di Java 
Pencarian linier atau pencarian sekuensial adalah algoritma pencarian yang paling sederhana. Ini melibatkan pencarian berurutan untuk elemen dalam struktur data yang diberikan hingga elemen tersebut ditemukan atau akhir struktur tercapai. Jika elemen ditemukan, maka lokasi item dikembalikan jika algoritma mengembalikan NULL.
Berikut ini pseudocode yang mewakili Penelusuran Linier di Java:
procedure linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search
Ini adalah sebuahalgoritma kekerasan.Meskipun jelas merupakan yang paling sederhana, namun yang paling pasti bukan yang paling umum, karena inefisiensi. Kompleksitas Waktu pencarian Linear adalah DI) .
 Algoritma Pencarian Biner di Java 
Pencarian biner, juga dikenal sebagai pencarian logaritmik, adalah algoritma pencarian yang menemukan posisi nilai target dalam larik yang sudah diurutkan. Ini membagi koleksi masukan menjadi dua bagian yang sama dan item tersebut dibandingkan dengan elemen tengah dari daftar. Jika elemen ditemukan, pencarian berakhir di sana. Jika tidak, kami terus mencari elemen dengan membagi dan memilih partisi yang sesuai dari array, berdasarkan apakah elemen target lebih kecil atau lebih besar dari elemen tengah.
Berikut pseudocode yang mewakili Penelusuran Biner di Java:
Prosedur binary_menelusuri larik yang diurutkan n ukuran larik x nilai yang akan dicari lowerBound = 1 upperBound = n sedangkan x tidak ditemukan jika upperBound
Pencarian berakhir ketika upperBound (pointer kita) melewati lowerBound (elemen terakhir), yang berarti kita telah mencari seluruh array dan elemen tersebut tidak ada.Ini adalah algoritma pencarian yang paling umum digunakan terutama karena waktu pencariannya yang cepat. Kompleksitas waktu dari pencarian biner adalah DI) yang merupakan peningkatan nyata pada DI) kompleksitas waktu Pencarian Linier.
Ini mengakhiri artikel 'Struktur Data dan Algoritma di Java' ini. Saya telah membahas salah satu topik paling mendasar dan penting di Jawa.Semoga Anda jelas dengan semua yang telah dibagikan dengan Anda di artikel ini.
  Pastikan Anda berlatih sebanyak mungkin dan mengembalikan pengalaman Anda.   
 Lihat    oleh Edureka, perusahaan pembelajaran online tepercaya dengan jaringan lebih dari 250.000 pelajar yang puas dan tersebar di seluruh dunia. Kami di sini untuk membantu Anda dengan setiap langkah dalam perjalanan Anda, selain pertanyaan wawancara java ini, kami hadir dengan kurikulum yang dirancang untuk siswa dan profesional yang ingin menjadi Pengembang Java. 
 Ada pertanyaan untuk kami? Harap sebutkan di bagian komentar pada 'Struktur Data dan Algoritma di Java'  artikel dan kami akan menghubungi Anda kembali sesegera mungkin.