linked list

LINKED LIST


PENDAHULUAN.
Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
Misalkan ada 1500 item yang merupakan elemen dari suatu linear list.
Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.
Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.

DEFINISI.
Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
- INFO , berisi informasi tentang elemen data yang bersangkutan.
- NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.

Berikut ini sebuah contoh linked list yang terdiri atas 4 node :



Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.

Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :



CATATAN :
- Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini,
yaitu :
1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.
2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.

- Sedangkan keuntungannya adalah :
1. Jenis data yang berbeda dapat di-link.
2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja.