q Dalam suatu linier list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
q Misalkan ada 1500 item yang merupakan elemen dari suatu linier list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linier list tersebut. Tetapi elemen ke–57akan 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.
q 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
q Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
q Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu:
Ø INFO berisi informasi tentang elemne 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:
|
Info next info next info next info next
|
Node ke-1 node ke-2 node ke-3 node ke-4
Pada node ke-4 field NEXT–nya berisi NULL , artinya node ke-4 tsb adalah node terakhir.
q 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:
Info next
Info next
|
Info next 
Info next  |
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 .
OPERASI DASAR PADA LINKED LIST
q Ada beberapa aturan yang didefinisikan pada operasi didalam linked list yaitu:
Ø Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
Ø Operasi yang didefinisikan pada suatu variabel pointer adalah:
1. Test apakah sama dengan NULL
2. Test untuk kesamaan denganvariabel pointer lain
3. Menetapkan sama dengan NULL
4. Menetapkan menuju ke node lain
q Notasi yang didefinisikan sehubungan dengan operasi diatas adalah
- NODE (P), artinya node yang ditunjuk oleh pointer P
- INFO (P), artinya nilai INFO dari node yang ditunjuk pointer P
- NEXT (P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P
Sebagai contoh, perhatikan linked list dibawah ini:
Info next
 |
|
start Info next info next
|
node ke-2 
node ke-1
|
node ke-3
 |
null
D
Info next
null
|
D |
|
NODE (P) = node yang ditunuk oleh P yaitu node pertama
INFO (P) = A
NEXT (P) = node kedua
INFO (NEXT(NEXT(P))) = C
MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE)
q Untuk menghapus node dalam linked list digunakan procedure FREENODE.
q Jika Q adalah suatu variabel pointer, maka FREENODE (Q) akan menyebabkan node yang ditunjuk oleh variabel poinnter Q dihapus dalam linked list.
Perhatikan linked list berikut :
Ø Langkah ke-1 :
Q := Next (P)
Info next info next info next
 |  |  | |||||
 | |||||||
P Q
Info next
…….
Ø Langkah ke-2 :
Next (P) := Next (Q)
Info next | |||||
 | |||||
 | |||||
Info next info next info next | |||||||||
 | |||||||||
| |||||||||
 | | ||||||||
Ø Langkah ke-3 :
Freenode (Q)
Procedure Freenode (Q)
(a) Next (Q) := Avail
(b) Info (Q) := Null
(c) Avail := Q
MENYISIPKAN SUATU NODE KEDALAM LINKED LIST
q Untuk menyisipkan node dalam linked list digunakan procedure GETNODE
q Jika NEW adalah suatu variabel pointer, maka GETNODE (NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW disisipkan kedalam linked list.
Perhatikan linked list berikut:
Procedure Getnode (NEW)
If Avail = Null
Then out-of-free-space
(a) else begin
Getnode := Avail
(b) Avail := Next (Avail)
(c) Next (Getnode) := Null;
End;
q Algoritma menyisipkan sebuah node :
(a) Getnode (NEW)
(b) Info (NEW) := Name;
(c) Q := Next (P)
(d) Next (P) := NEW
(e) Next (NEW) := Q
Tidak ada komentar:
Posting Komentar