double linked list

I. JUDUL PRAKTIKUM : DOUBLE LINKED LIST
II. TUJUAN PRAKTIKUM :
1. Mengetahui apa itu Double Linked List
2. Mengetahui penerapan linked list pada program
3. Mengetahui cara penyisipan elemen linked list
4. Mengetahu cara penghapusan elemen linked list
5. Dapat membuat procedure-procedure yang terdapat pada linked list
6. Dapat membuat program sederhana menggunakan linked list



























III. Dasar Teori
Double linked list adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field yaitu, 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Double linked list pointer next dan prevnya menunjuk ke dirinya sendiri secara circular. Linked list merupakan struktur data yang memiliki kelebihan dalam efisiensi memori dan kecepatan dalam menyisipkan data. Linked list berguna untuk menyimpan beberapa data dalam memori.
Definisi
Secara umum, sebuah list bertipe T adalah sebuah barisan elemen-elemen bertipe T beserta operasi-operasinya yang meliputi :
1. Membuat list (menginisialisasi list), yaitu membuat list menjadi kosong.
2. Menentukan apakah status list kosong atau tidak.
3. Menentukan apakah status list penuh atau tidak.
4. Mengetahui panjang (jumlah elemen) list.
5. Mengetahui sebarang node dari list (menghapus node).
6. Mengakses sebarang node dalam list, dengan membaca nilai atau menganti nilai yang ada dengan nilai yang baru.
7. Menyisipkan node baru ke dalam list di sebarang lokasi.
Linked List dengan Pointer
Pascal menyediakan prosedur standar untuk membuat dan menghapus sebuah variable dinamis, yaitu new dan dispose. Jika p telah dideklarasikan sebagai sebuah variable pointer bertipe node, maka pernyataan new(p) akan menciptakan sebuah variable dinamis baru bertipe node dan menandai lokasinya dengan pointer p. Sedangkan pernyataan dispose (p) akan mengembalikan ruang yang digunakan pada lokasi yang ditunjuk p ke sistem computer,pointer p menjadi tidak terdefinisi lagi. Kadang-kadang sebuah pointer tidak menunjuk ke suatu variable dinamis.
Kondisi ini harus ditandai dengan mengisi pointer tersebut dengan nilai standar nil. Hal ini dapat dilakukan dengan pernyataan p:=nil; dan pada kesempatan lain kondisi ini dapat diperiksa dengan pernyataan if p = nil…atau if p <>nil…Kata nil merupakan kata tercadang dalam pascal. Nil merupakan nilai generic dan dapat diisikan ke sebarang variable pointer dengan tipe apapun.
Double linked list dipilih bila banyak operasi yang memerlukan predesesor. Sebagaimana yang telah kita pelajari, untuk menghapus elemen senarai perlu alamat predesesornya, begitu juga untuk menyisipkan elemen. Untuk menghindari pencarian predesesor, maka pada setiap elemen ditambahkan field prev dan field next yang membuat operasi pada senarai ini lebih kompleks.
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 :

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.
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 dengan variabel pointer lain.
3. Menetapkan sama dengan NULL.
4. Menetapkan menuju ke node lain.
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :
1. NODE(P), artinya node yang ditunjuk oleh pointer P.
2. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
3. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Sebagai contoh, perhatikan linked list dibawah ini :

MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE).
Untuk menghapus node dalam linked list digunakan procedure FREENODE. Jika Q adalah suatu variabel pointer, maka FREENODE(Q) akan menyebabkan node yang ditunjuk oleh variabel pointer Q dihapus dari linked list.
Perhatikan linked list berikut :
langkah ke-1 :
Q := Next(P)

langkah ke-2 :
Next(P) := Next(Q)

langkah ke-3 :
Freenode(Q)
procedure Freenode(Q)
(a) Next(Q) := Avail

(b) Info(Q) := Null
(c) Avail := Q

MENYISIPKAN SUATU NODE KE DALAM LINKED LIST
Untuk menyisipkan node dalam linked list digunakan procedure GETNODE. Jika NEW adalah suatu variabel pointer, maka GETNODE(NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW disisipkan ke dalam linked list.
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;

Algoritma menyisipkan sebuah Node :
(a) Getnode(NEW);
(b) Info(NEW) := Name;

(c) Q := Next(P)
(d) Next(P) := NEW

(e) Next(NEW) := Q

Jika sebuah Linked List digunakan untuk menggambarkan suatu antrean, dalam hal ini pointer dapat langsung menunjuk ke rear/akhir dari antrean untuk menghindari pengulangan melalui semua node untuk menemukan node terakhir.








Circular Linked List

Head Nodes

Circular Linked List dengan Head Node

Circular Linked List dengan Head Node kosong
Algoritma penyisipan node yang berisi variabel Name pada head dalam Linked List
a. Ambil node baru pada free storage kemudian node tersebut ditunjuk oleh pointer NEW
b. Isikan Info dengan Name pada node baru tsb.
c. Next dari node baru tsb. menunjuk ke node yang ditunjuk oleh pointer Head
d. Pindahkan pointer Head menunjuk ke node yang baru.
Untuk lebih jelas mengenai penggunaan double linked list, berikut contoh program sederhananya :








Ini merupakan bagian deklarasi program, dimana sebuah pointer diinisialisasikan dengan nama ptrsimpul dan di dalam sebuah simpul tersebut terdapat 3 buah field yaitu prev, nilai, dan next. Field prev dan next di sini bertipe data ptrsimpul dimana dengan tipe data tersebut, maka kedua field ini bias digunakan sebagai pemanggil dari sebuah simpul yang berbeda.
Ada beberapa variable yang bertipe data ptrsimpul yaitu belakang, depan dan next. Variabel belakang digunakan sebagai alamat dari simpul belakang, variable depan digunakan sebagai alamat dari simpul depan sedangkan variable baru digunakan sebagai simpul pembantu dalam proses input. Selanjutnya juga dipakai variable-variabel pembantu seperti angka,I dan n yang fungsinya menyesuaikan.
Berikut ini juga diberikan procedure tulis yang digunakan untuk mencetak atau menuliskan double linked list yang terbentuk ke layar.







Berikut diberikan procedure hapuskan untuk menghapus data dalam double linked list yang terbentuk.



















Daftar Pustaka
http://Google.com/double linked list
Akses : Selasa , 16 November 2010 21: 19.
http://google.com/ Modul Praktikum Struktur Data – IT045329 .
Akses : Selasa ,16 November 2010. 21.17.
http://wikipedia.co.id/Double Linked list pada Pascal
Akses : Senin, 16 November 2010 21: 15.
Tim Asisten. 2010. Modul Praktikum Pemrograman Komputer II. Inderalaya : Mitra Kharisma.