Ennen vanhaan ohjelmointikielissä ei tavallisesti ollut ArrayListin kaltaista näppärää tietorakennetta. Tyypillinen ainoa tietorakenne oli taulukko, joka on myös Javan perustietorakenne.
Taulukko muistuttaa ArrayList-rakennetta, mutta sen käyttämiseen liittyvät seuraavat erot:
contains (onko luku taulukossa) puuttuu.
Taulukko näyttää ensisilmäyksellä rajoittuneelta, mutta taitava ohjelmoija pystyy toteuttamaan sen avulla minkä tahansa tietorakenteen. Myös ArrayList on toteutettu sisäisesti taulukon avulla.
Taulukkoa ei tarvitse kovin usein Javassa, mutta siitä kannattaa silti olla tietoinen. Yksi syy on, että jotkin Javan kirjastoon kuuluvat metodit käyttävät taulukoita. Lisäksi ohjelmoijan sivistykseen kuuluu tietää, miten erilaiset asiat voisi tehdä taulukolla, vaikka käytännössä yleensä voikin turvautua Javan kehittyneempiin tietorakenteisiin.
Seuraava koodi määrittelee taulukon, johon voi tallentaa 10 lukua:
int[] taulukko = new int[10];
Muunlaiset taulukot määritellään vastaavasti. Toisin kuin ArrayListin määrittelyssä taulukossa käytetään tavallisia muuttujatyyppejä.
Taulukon voi myös määritellä antamalla suoraan sen sisällön:
int[] taulukko = {4, 8, 3, 2, 9};
Yllä oleva koodi määrittelee taulukon, jossa ovat annetut viisi lukua.
Taulukon arvot on numeroitu nollasta alkaen samaan tapaan kuin ArrayListin arvot. Esimerkiksi äsken määritelty taulukko on muistissa seuraavasti:
| kohta | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arvo | 4 | 8 | 3 | 2 | 9 |
Taulukon arvoihin viitataan antamalla taulukon nimi ja hakasulkeissa haluttu kohta taulukossa.
Seuraava koodi tulostaa taulukon toisen arvon:
System.out.println(taulukko[1]);
Seuraava koodi muuttaa taulukon kolmanneksi arvoksi luvun 6:
taulukko[2] = 6;
Perinteinen tapa käydä taulukko läpi on seuraava:
int[] taulukko = {4, 8, 3, 2, 9};
for (int i = 0; i < taulukko.length; i++) {
System.out.println(taulukko[i]);
}
Ohjelman tulostus on seuraava:
4 8 3 2 9
Javassa on mahdollista käyttää myös samanlaista for-silmukkaa kuin ArrayListin läpikäynnissä:
int[] taulukko = {4, 8, 3, 2, 9};
for (int luku : taulukko) {
System.out.println(luku);
}
Suoraviivainen tapa etsiä arvoa taulukosta on käydä taulukko läpi for-silmukalla ja katsoa, esiintyykö arvo jossain kohtaa taulukkoa. Tällaisen etsintätavan nimi on peräkkäishaku. Koodi ei ole vaikea:
public static boolean perakkaishaku(int[] taulukko, int haettava) {
for (int luku : taulukko) {
if (luku == haettava) {
return true;
}
}
return false;
}
Miten taulukon voisi järjestää kotikonstein?
Yksi yksinkertainen tapa järjestää taulukko on kuplajärjestäminen. Siinä taulukkoa käydään toistuvasti läpi ja jos jossain kohtaa kaksi vierekkäistä arvoa on väärin päin, niiden järjestys korjataan. Järjestäminen on valmis, kun läpikäynnin aikana ei tarvitse muuttaa mitään.
Kuplajärjestämisen voi toteuttaa seuraavasti:
public static void jarjestaminen(int[] taulukko) {
boolean eiValmis = true;
while (eiValmis) {
eiValmis = false;
for (int i = 0; i < taulukko.length - 1; i++) {
if (taulukko[i] > taulukko[i + 1]) {
int vaihto = taulukko[i];
taulukko[i] = taulukko[i + 1];
taulukko[i + 1] = vaihto;
eiValmis = true;
}
}
}
}
Tässä on esimerkki kuplajärjestämisen toiminnasta:
4<->8 3 2 9
4 3<->8 2 9
4 3 2<->8 9
4 3 2 8<->9
3<->4 2 8 9
3 2<->4 8 9
3 2 4<->8 9
3 2 4 8<->9
2<->3 4 8 9
2 3<->4 8 9
2 3 4<->8 9
2 3 4 8<->9
Jos taulukko on järjestyksessä, sieltä etsimisen voi toteuttaa todella tehokkaasti. Binäärihaku jakaa joka vaiheessa etsintäalueen kahteen yhtä suureen osaan ja katsoo osien välissä olevasta arvosta, kumpaan suuntaan hakua tulee jatkaa. Jos mietit nimen etsimistä puhelinluettelosta, saat hyvän idean binäärihaun toiminnasta.
Binäärihaun idean voi kuvata helposti, mutta algoritmin toteuttaminen täysin toimivaksi on vaikeaa. Seuraavassa on yksi yritys:
public static boolean binaarihaku(int[] taulukko, int haettava) {
int vasen = 0;
int oikea = taulukko.length - 1;
boolean onTaulukossa = false;
while (vasen <= oikea) {
int keski = (vasen + oikea) / 2;
if (taulukko[keski] == haettava) {
return true;
}
if (taulukko[keski] < haettava) {
vasen = keski + 1;
} else {
oikea = keski - 1;
}
}
return false;
}
Seuraavassa esimerkissä taulukosta haetaan lukua 10. Merkit
v, k ja o tarkoittavat vastaavasti
muuttujia vasen, keski ja oikea.
3 5 8 9 10 12 16 17 19 25 27 30 34
v k o
3 5 8 9 10 12 16 17 19 25 27 30 34
v k o
3 5 8 9 10 12 16 17 19 25 27 30 34
v k o