INTRODUKSI LIST LINIER

PERSOALAN

Dipunya sebuah tabel yang setiap elemennya terdiri beberapa item data, dan tabelnya berukuran relatif cukup besar.
Misalnya sebuah tabel yang diberikan dalam kamus umum sebagai berikut :
klik disini

Dari tabel tersebut, dikehendaki untuk mendapatkan daftar dari nama mahasiswa sesuai dengan urutan tertentu (misalnya sesuai dengan nilaiTot dan disusun mulai dari yang terbesar sampai yang terkecil). Kebutuhan ini dapat dilakukan berbagai cara. Untuk mendapatkan daftar dari tabel dengan urutan tertentu, isi tabel dapat diurutkan secara fisik (elemennya benar terurut sesuai posisi indeks pada tabel), atau hanya secara lojik (elemen tabel tidak terurut menurut posisi indeks, tetapi daftar yang dicetak terurut). Semua contoh berikut memakai kamus umum di atas.

1. Cara pertama : Pengurutan terhadap tabel, kemudian cetak tabel terurut. Solusi yang paling sederhana adalah dengan mengurut tabel. Pengurutan dilakukan dengan salah satu metoda yang telah dipelajari, kemudian dicetak. Misalnya untuk persoalan ini dipakai pengurutan berdasarkan harga maksimum suksesif. klilk disini, setelah itu klik disini, selanjutnya klik disini
   Perhatikan bahwa pada solusi ini:
   Tabel diurut secara "fisik". Elemen-elemennya berpindah-pindah tempat (walaupun pada keadaan awal, tabel sudah terurut!). Metoda pengurutan apapun yang dipakai tidak mungkin menghindari pertukaran tempat elemen tabel. Jika primitif assignment sebuah elemen tabel secara menyeluruh tidak tersedia, maka proses pertukaran akan membuat algoritma tidak efisien, karena pergeseran sebuah elemen meliputi banyak assignment jika elemen tabel terdiri dari banyak item. Pada contoh di atas, karena ada 7 item, dan untuk setiap kali pertukaran tempat harus dilakukan 3 assignment maka untuk setiap pass, diperlukan 21 assignment.
2. Cara kedua: Pembuatan Tabel RANKING
   Ide kedua adalah untuk menghindari banyak assignment, atau mengurutkan isi tabel secara fisik. Akan dibuat sebuah tabel lain yang hanya memuat "ranking" dari tabel: TabRanki berisi indeks pada TabMhs yang rankingnya ke-i, maka pengurutan dan pergeseran elemen hanya dilakukan terhadap tabel ranking. Dengan cara ini, isi tabel tidak terurut secara fisik.

Contoh berikut adalah jika pengurutan terhadap tabel ranking dilakukan dengan Maximum suksesif, tanpa harus mengadakan perubahan terhadap elemen-elemen TabMhs. klik disini

Catatan :
TabMhsTabRank(i) dituliskan untuk menunjukkan bahwa indeks TabRank adalah i, dan TabRanki merupakan indeks dari TabMhs. Penulisan tersebut adalah karena keterbatasan word processor. klik disini

Perhatikan bahwa:

1. Walaupun ada pertukaran harga karena pengurutan, yang ditukar hanyalah harga ranking pada tabel TabRank, dan tidak pada setiap elemen tabel Mahasiswa.
2. TabMhs tidak berganti keadaan : semua elemennya berada pada tempatnya semula.
3. Pemakaian tabel "ranking" seperti di atas banyak dilakukan dalam pengolahan data dalam basis data, dan dikenal sebagai "indeks". Jika data disimpan dalam arsip, maka tabel ranking juga diimplementasikan dalam sebuah arsip, dan disebut sebagai "Indeks File". Arsip yang mempunyai indeks tidak perlu digeser-geser datanya kalau terjadi penyisipan, tetapi setiap kali ada perubahan atau penambahan data, arsip harus di indeks kembali, artinya membuat "ranking" yang baru.
   Implementasi tabel pengakses (indeks) pada basis data tentu tidak sesederhana itu, mempergunakan teknik-teknik yang membuat akses lebih efisien, dengan struktur yang lebih kompleks (misalnya B-tree).