Tip nggunakake koleksi

1. Daftar koleksi

Sampeyan bisa uga elinga, Jawa duwe koleksi - alat praktis kanggo nyimpen obyek saka jinis sing padha.

Ayo nyoba ngelingi antarmuka sing gegandhengan karo koleksi utama:

Dhaptar , Setel , Peta lan Antrian .

Kaya biasane, alat kasebut ora mesthi apik utawa ala - sing penting yaiku apa sampeyan nggunakake alat kasebut kanggo tujuan sing dituju. Lan kanggo nindakake iku, kita kudu ngerti kanthi lengkap fitur tartamtu supaya ngerti koleksi sing digunakake lan kapan.

1. Dhaptar

Ayo miwiti karo koleksi sing paling akeh digunakake.

Dhaptar minangka cedhak karo array lawas kosong.

Koleksi iki ngidini kita nyimpen dhaptar obyek saka jinis sing padha tanpa kuwatir babagan ukuran koleksi kasebut, kaya sing kudu ditindakake yen nggunakake array. Unsur koleksi diakses kanthi indeks. Yen kita ngerti persis ing ngendi obyek kasebut lan kudu kerep ngakses tanpa perlu nambah utawa mbusak unsur, dhaptar iku becik.

2. Set

Set nduweni struktur sing beda banget.

Set paling cocok nalika kita kudu nyimpen obyek unik. Contone, sakumpulan penulis ing perpustakaan sing saben penulis unik. Nanging kita ora bisa mung njupuk penulis tartamtu saka iku. Set ngidini kita mriksa kanthi cepet apa penulis tartamtu ana ing perpustakaan kita, yaiku kita bisa mriksa apa obyek unik ana ing Set . Kita uga bisa ngulang kabeh koleksi, ngakses saben unsur, nanging nindakake iku ora optimal.

Ing tembung liyane, kanggo perpustakaan kita, Set bisa makili koleksi kabeh penulis unik kanggo cepet mriksa yen ana penulis tartamtu.

3. Peta

Peta luwih kaya lemari arsip, ing ngendi saben file ditandatangani lan bisa nyimpen obyek individu utawa kabeh struktur. Peta kudu digunakake ing kasus nalika kita kudu njaga pemetaan saka siji nilai menyang liyane.

Kanggo Peta , hubungan kasebut diarani pasangan kunci-nilai.

Kita bisa nggunakake struktur iki ing perpustakaan kanthi nggunakake obyek penulis minangka tombol lan dhaptar ( Dhaptar obyek) buku minangka nilai. Dadi, sawise mriksa Set kanggo ndeleng manawa ana obyek penulis ing perpustakaan, kita bisa nggunakake obyek penulis sing padha kanggo entuk Dhaptar bukune saka Peta .

4. Antri

Antrian minangka koleksi sing - kaget! - ngleksanakake prilaku antrian. Lan antrian bisa dadi LIFO (Last In, First Out) utawa FIFO (First In, First Out). Apa maneh, antrian bisa dadi loro arah, utawa "ganda-rampung".

Struktur iki mbiyantu nalika obyek sing ditambahake ing kelas kudu digunakake ing urutan sing ditampa. Contone, njupuk perpustakaan kita.

Kita bisa nambah pengunjung sing mentas teka menyang Antrian lan ngladeni wong-wong mau kanthi giliran, ngetokake buku sing dituju.

Kaya sing kita deleng, saben struktur kasebut apik yen digunakake kanggo tujuan sing dituju. Lan kita nemokake panggunaan apik kanggo kabeh patang jinis koleksi ing conto perpustakaan siji.

2. Kompleksitas

Kaya sing wis dingerteni, koleksi sing kita anggep ing ndhuwur minangka antarmuka, tegese kudu duwe implementasine supaya bisa digunakake.

Kaya palu kuku nganggo mikroskop dudu ide sing paling apik, ora saben implementasine koleksi cocog kanggo saben kahanan.

Nalika milih alat sing tepat kanggo proyek, kita biasane ndeleng 2 ciri:

• Kepiye alat kasebut cocog karo proyek kasebut?
• Carane cepet iku bakal njaluk proyek rampung?

Kita wis ngginakaken sawetara wektu kanggo nemtokake cara kanggo milih alat cocok kanggo proyek, nanging kacepetan soko anyar.

Ing komputasi, kacepetan alat asring ditulis ing syarat-syarat kerumitan wektu lan dilambangake karo huruf kapital O.

Apa ing donya kerumitan wektu?

Ing istilah sing prasaja, kerumitan wektu nuduhake wektu sing dibutuhake kanggo algoritma ing koleksi kanggo nindakake tumindak tartamtu (nambah / mbusak unsur, nggoleki unsur).

ArrayList vs LinkedList

Ayo goleki iki nggunakake rong implementasi antarmuka List - ArrayList lan LinkedList .

Kanggo tampilan njaba, nggarap koleksi iki padha:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Nalika sampeyan bisa ndeleng, kanggo loro jinis koleksi, nambah, njupuk, lan mbusak unsur katon padha. Iki amarga iki minangka implementasi ing antarmuka sing padha. Nanging ing ngendi podho rampung.

Amarga implementasine beda saka antarmuka List , loro struktur iki nindakake tumindak beda luwih irit tinimbang liyane.

Coba njabut lan nambah unsur.

Yen kita kudu mbusak unsur saka tengah ArrayList , kita kudu nimpa bagean apa wae saka dhaftar nderek unsur kita mbusak.

Upaminipun kita duwe dhaptar 5 unsur lan kita arep mbusak siji 3rd.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Ing kasus iki, penghapusan mbebasake siji sel, mula kita kudu nulis unsur kaping 4 ing endi sing kaping 3, lan sing kaping 5 ing endi sing nomer 4.

Iki banget ora efisien.

Padha mengkono nalika nambah unsur ing tengah dhaftar.

LinkedList disusun kanthi cara sing beda. Nambah utawa ngilangi unsur cepet, amarga kita mung kudu ngganti referensi ing unsur sadurunge lan sabanjure, saéngga ora kalebu obyek sing bakal dibusak saka rantai unsur.

Bali menyang conto dhaptar 5 unsur sing padha, sawise ngilangi unsur 3, kabeh sing kudu ditindakake yaiku ngganti referensi unsur 2 menyang unsur sabanjure lan referensi unsur kaping 4 menyang sing sadurunge.

Nalika unsur ditambahake menyang dhaptar, proses sing padha kedadeyan, nanging mbalikke.

Wigati sepira kurang karya sing kudu ditindakake ing LinkedList dibandhingake karo ArrayList . Lan iku mung 5 unsur. Yen dhaptar kita duwe 100 utawa luwih unsur, kaunggulan LinkedList bakal dadi luwih katon.

Nanging kepiye kahanan diganti yen kita ngakses unsur kanthi indeks?

Kabeh iku ngelawan pas kene.

Wiwit ArrayList wis kabentuk minangka array biasa, njupuk sembarang unsur dening indeks bakal gampang banget kanggo kita. Kita mung mindhah pointer menyang panggonan tartamtu lan entuk unsur saka sel sing cocog.

Nanging LinkedList mung ora bisa digunakake. Kita kudu ngliwati kabeh unsur dhaptar kanggo nemokake unsur kanthi indeks tartamtu.

Apa kita bakal nyoba kanggo nyebut kabeh iki ing syarat-syarat O amba?

Ayo miwiti kanthi ngakses unsur kanthi indeks.

Ing ArrayList , iki kelakon ing siji langkah, preduli saka ngendi unsur dumunung ing dhaftar. Apa ing pungkasan utawa wiwitan.

Ing kasus iki, kerumitan wektu bakal dadi O(1) .

Ing LinkedList , kita kudu ngulang sawetara unsur sing padha karo nilai indeks sing kita butuhake.

Kompleksitas wektu kanggo tumindak kasebut yaiku O(n) , ing ngendi n minangka indeks saka unsur sing kita butuhake.

Ing kene sampeyan bisa ndeleng manawa nomer sing dilebokake ing kurung gedhe-O cocog karo jumlah tumindak sing ditindakake.

Shell kita bali kanggo njabut lan nambah?

Ayo dadi miwiti karo LinkedList.

Amarga kita ora perlu nindakake akeh tumindak kanggo nambah utawa mbusak unsur, lan kacepetan operasi iki ora gumantung ing sembarang cara ing ngendi unsur dumunung, kerumitan ditulis minangka O (1) lan ngandika . dadi pancet.

Kerumitan wektu operasi iki kanggo ArrayList uga O(n) , sing diarani kerumitan linier.

Ing algoritma kanthi kerumitan linier, wektu mlaku gumantung langsung marang jumlah unsur sing bakal diproses. Bisa uga gumantung ing posisi unsur, apa ana ing wiwitan dhaptar utawa ing pungkasan.

Kompleksitas wektu uga bisa logaritmik. Iki ditulis minangka O(log n) .

Contone, nimbang TreeSet diurutake sing dumadi saka 10 nomer. Kita pengin golek nomer 2.

Wiwit dhaptar diurutake lan ora ana duplikat, kita bisa dipérang dadi setengah lan mriksa sing setengah bakal ngemot nomer sing dikarepake, mbusak bagean sing ora cocog lan banjur baleni proses iki nganti tekan unsur sing dikarepake. Wekasanipun, kita bakal nemokake (utawa ora nemokake) nomer sawise Processing log (n) nomer unsur.

Mangkene tabel sing ngringkes kerumitan wektu liyane saka koleksi.

Saiki kita duwe tabel sing nuduhake kerumitan wektu koleksi populer, kita bisa mangsuli pitakon kenapa, saka akeh koleksi, kita paling kerep nggunakake ArrayList , HashSet lan HashMap .

Iku mung sing paling efisien kanggo akeh tugas :)