List Asosiasi (Java)

Salah satu aplikasi pencarian yang banyak digunakan adalah yang menggunakan list asosiasi (association list). Contoh umum dari suatu list asosiasi adalah kamus. Kamus menghubungan kata dengan definisi. Dengan kata tertentu, kita bisa menggunakan kamus untuk mencari definisinya. Kita bisa membayangkan kamus sebagai daftar suatu pasangan (pair) dalam bentuk (k,d) di mana k adalah kata dan d adalah definisi. Secara umum, kita menganggap bahwa tidak ada dua pasangan dalam list yang memiliki kunci yang sama. Operasi dasar dari list asosiasi adalah sebagai berikut : Dengan kunci k, cari nilai n yang berhubungan dengan k, jika ada.

List asosiasi digunakan secara luas dalam ilmu komputer. Misalnya, suatu kompiler harus melacak di mana lokasi suatu variabel pada memori. Kompiler dapat menggunakan list asosiasi di mana kuncinya adalah nama variabel dan nilainya adalah alamat variabel tersebut di memori. Contoh lainnya adalah mailing list, yang menghubungkan nama dan alamat email dalam daftar tersebut. Contoh lain yang mungkin berhubungan adalah direktori telepon yang menghubungkan nama dan nomor telepon. Item di dalam list tersebut mungkin berupa objek dari kelas :

class EntriTelepon {
    String nama;
    String noTelp;
}

Data dalam direktori telepon adalah array yang bertipe EntriTelepon[ ] dan variabel integer untuk menyimpan berapa banyak item yang disimpan dalam direktori tersebut. (Contoh ini adalah contoh dari "array setengah penuh" yang dibahas pada bagian sebelumnya. Mungkin lebih baik jika kita menggunakan array dinamis atau ArrayList untuk menyimpan daftar telepon.) Direktori telepon mungkin berupa objek di dalam kelas

class DirektoriTelepon {
 
    EntriTelepon[] info = new EntriTelepon[100];  // Tempat untuk 100 entri
    int jmlEntri = 0;  // Jumlah entri aktual di dalam array
 
    void tambahEntri(String nama, String noTelp) {
        // Tambah entri baru di akhir array
        info[jmlEntri] = new EntriTelepon();
        info[jmlEntri].nama = nama;
        info[jmlEntri].noTelp = noTelp;
        jmlEntri++;
    }
 
    String getNoTelp(String nama) {
        // Ambil nomor telepon dari nama ini atau 
        // kembalikan null jika tidak ada nama ini
        // di dalam array.
        for (int idks = 0; idks < jmlEntri; idks++) {
            if (nama.equals( info[idks].nama ))  // Nama ketemu!
                return info[idks].noTelp;
        }
        return null;  // Nama tidak ketemu.
    }
}

Lihat bahwa metode getNoTelphanya mengambil lokasi dalam array yang telah diisi dengan EntriTelepon. Dan juga tidak seperti rutin pencarian yang disebutkan sebelumnya, rutin ini tidak mengembalikan lokasi item dalam array. Akan tetapi ia mengembalikan nilai lain yang berhubungan dengan kata kuncinya, yaitu nama. Hal ini sering dilakukan untuk list asosiasi.

Kelas ini bisa diperbaliki lebih lanjut. Satu hal, mungkin lebih baik jika kita melakukan pencarian dengan menggunakan pencarian biner dan bukan pencarian linier sederhana dalam metode getNoTelp. Akan tetapi, kita hanya bisa lakukan ini apabilaEntriTelepon diurut terlebih dahulu berdasarkan nama. Dan sebenarnya, tidak terlalu suit untuk membuat entri tersebut dalam urutan, yang akan kita lihat berikutnya.