MODUL STRUKTUR DATA ILAB PART 2

2. POINTER dan SINGLE LINK LIST

TUJUAN PRAKTIKUM

1.      Praktikan mengetahui tipe struktur data baru yaitu tipe data Pointer.

2.      Praktikan menggunakan pointer didalam pembuatan program dan dapat menerapkannya dalam sebuah variabel dinamik (Link List).

3.      Praktikan mengetahui perbedaan antara variabel Pointer, Variabel Statis dan Variabel Dinamis.

TEORI PENUNJANG

            Pada pertemuan sebelumnya telah dijelaskan mengenai variabel yang bertipe Array, suatu tipe data yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu ruang memori yang dipakai oleh variabel tersebut tidak dapat dihapus jika variabel tersebut tidak digunakan kembali.

            Untuk mengatasi masalah diatas maka pascal menawarkan suatu fasilitas yang di mungkinkan suatu pengubah/variabel bersifat dinamis. Variabel dinamis adalah suatu variabel yang akan dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi. Variabel-variabel ini juga dapat dihapus pada saat program dieksekusi, sehingga ukuran variabel akan selalu berubah.

2.1. Variabel Pointer

Variabel dinamik tidak dapat dideklarasikan secara eksplisit seperti halnya mendeklarasikan variabel statik dan tidak dapat secara langsung ditunjukkan oleh suatu pengenal (identifier). Variabel dinamik hanya dapat ditunjukkan oleh variabel khusus yang berisi alamat memori yang digunakan oleh variabel dinamik tersebut. Variabel khusus ini disebut juga dengan variabel pointer. Variabel Pointer adalah suatu variabel yang menunjuk ke alamat memori yang digunakan untuk menampung data yang akan diproses.

Deklarasi Variabel Pointer :

Var <Nama Variabel> : ^<Tipe Data>

Contoh Pendeklarasian :

Var

JumlahData        :    ^Integer;

NamaSiswa        :    ^String[25];

NilaiSiswa          :    ^Real;

Pendeklarasian variabel pointer tidak jauh berbeda dengan pendeklarasian variabel biasa, hanya perlu ditambahkan simbol topi ( ^ ) – biasa juga disebut ceret atau circumflex. Simbol topi tersebut menandakan bahwa variabel tersebut menunjuk ke lokasi tertentu di memori.

2.2. Operasi Pada Pointer

Pada pointer ada dua operasi dasar yang dapat dilakukan yaitu :

1.      Operasi mengkopi simpul

2.      Operasi mengkopi isi simpul

Untuk memahami operasi di atas perhatikan contoh berikut. Pertama kali kita deklarasikan variabel pointernya, yaitu :

Var

P1, P2 : ^Byte;

Posisi P1 dan P2 di memory sekarang ini adalah P1 menunjuk ke tipe data Byte dan P2 juga menunjuk ke tipe data Byte.

Jika kita mengisi variabel P1 dengan 5 san P2 dengan 8 maka posisi P1 dan P2 sekarang adalah :

P1:=5; P2:=8;

Jika kita memberikan statement :

P1:=P2;

Maka gambar diatas berubah menjadi :

 2. POINTER dan SINGLE LINK LIST

TUJUAN PRAKTIKUM

1.      Praktikan mengetahui tipe struktur data baru yaitu tipe data Pointer.

2.      Praktikan menggunakan pointer didalam pembuatan program dan dapat menerapkannya dalam sebuah variabel dinamik (Link List).

3.      Praktikan mengetahui perbedaan antara variabel Pointer, Variabel Statis dan Variabel Dinamis.

TEORI PENUNJANG

            Pada pertemuan sebelumnya telah dijelaskan mengenai variabel yang bertipe Array, suatu tipe data yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu ruang memori yang dipakai oleh variabel tersebut tidak dapat dihapus jika variabel tersebut tidak digunakan kembali.

            Untuk mengatasi masalah diatas maka pascal menawarkan suatu fasilitas yang di mungkinkan suatu pengubah/variabel bersifat dinamis. Variabel dinamis adalah suatu variabel yang akan dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi. Variabel-variabel ini juga dapat dihapus pada saat program dieksekusi, sehingga ukuran variabel akan selalu berubah.

2.1. Variabel Pointer

Variabel dinamik tidak dapat dideklarasikan secara eksplisit seperti halnya mendeklarasikan variabel statik dan tidak dapat secara langsung ditunjukkan oleh suatu pengenal (identifier). Variabel dinamik hanya dapat ditunjukkan oleh variabel khusus yang berisi alamat memori yang digunakan oleh variabel dinamik tersebut. Variabel khusus ini disebut juga dengan variabel pointer. Variabel Pointer adalah suatu variabel yang menunjuk ke alamat memori yang digunakan untuk menampung data yang akan diproses.

Deklarasi Variabel Pointer :

Var <Nama Variabel> : ^<Tipe Data>

Contoh Pendeklarasian :

Var

JumlahData        :    ^Integer;

NamaSiswa        :    ^String[25];

NilaiSiswa          :    ^Real;

Pendeklarasian variabel pointer tidak jauh berbeda dengan pendeklarasian variabel biasa, hanya perlu ditambahkan simbol topi ( ^ ) – biasa juga disebut ceret atau circumflex. Simbol topi tersebut menandakan bahwa variabel tersebut menunjuk ke lokasi tertentu di memori.

2.2. Operasi Pada Pointer

Pada pointer ada dua operasi dasar yang dapat dilakukan yaitu :

1.      Operasi mengkopi simpul

2.      Operasi mengkopi isi simpul

Untuk memahami operasi di atas perhatikan contoh berikut. Pertama kali kita deklarasikan variabel pointernya, yaitu :

Var

P1, P2 : ^Byte;

Posisi P1 dan P2 di memory sekarang ini adalah P1 menunjuk ke tipe data Byte dan P2 juga menunjuk ke tipe data Byte.

Jika kita mengisi variabel P1 dengan 5 san P2 dengan 8 maka posisi P1 dan P2 sekarang adalah :

P1:=5; P2:=8;

Jika kita memberikan statement :

P1:=P2;

   Dari nilai diatas dapat di perhatikan bahwa sekarang pointer P2 juga menunjuk ke simpul yang ditunjuk oleh pointer P1. Simpul yang tadinya ditunjuk oleh P2 menjadi terlepas. Dalam keadaan seperti ini, karena tidak ditunjuk oleh suatu pointer lain, maka simpul tersebut tidak bisa dimasuki lagi karena lokasi simpul tersebut dalam variabel tidak diketahui lagi (kecuali apabila simpul ini ditunjuk oleh pointer yang lain). Operasi inilah yang disebut dengan operasi mengkopi pointer.

Kita kembali lagi ke gambar sebelumnya. Jika statemen yang diberikan adalah :

P1^:=P2^;

  

Operasi inilah selanjutnya yang disebut dengan operasi mengkopi isi simpul.

2.3. Variabel Dinamik

 Variabel dinamik dibentuk dengan menggunakan variabel pointer yang telah dialokasikan. Pengalokasian variabel ini menggunakan statement New(). Jika kita tidak membutuhkan variabel dinamik yang telah kita bentuk maka kita dapat menghapusnya dari memory dengan menggunakan statemen Dispose(). Sampai saat ini kita baru membentuk satu buah variabel dinamik.

Jika kita memakai banyak variabel dinamis maka kita akan membutuhkan banyak variabel pointer. Oleh karena itu ada baiknya jika kita hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut dengan link list.

2.4. Linked List

      Link list merupakan suatu variabel yang bertipe pointer yang membentuk suatu untaian yang saling berhubungan. Tiap untaian tersebut diletakkan pada memory. Tempat yang disediakan pada suatu area memori tertentu untuk menyimpan data dikenal dengan  sebutan Node/Simpul.  Linked list juga disebut dengan seranai beranai merupakan suatu variabel pointer yang simpulnya bertipe Record.

Gambar 2.1 Simpul-simpul yang membentuk seranai beranai

Deklarasi Linked List di dalam Pascal :

Type

PSimpul      =       ^Simpul

Simpul        =       Record

                                   Info : Tipe Data;

                                   Next : PSimpul;

                             End;

Var

Head, Tail : PSimpul;

Variabel Head dan Tail selanjutnya dialokasikan dengan statement New(), yang dihasilnya nantinya merupakan link list yang sudah terbentuk.

Ada beberapa hal yang harus diketahui mengenai link list, diantaranya adalah :

1.            Link list selalu memiliki pointer petunjuk yang selalu menunjuk pada awal dari list yang disebut Head.

2.            Link list juga selalu memiliki pointer petunjuk menunjuk pada akhir dari list yang disebut Tail, kecuali untuk jenis circular.

3.            Setiap simpul yang terbentuk selalu memiliki nilai NIL, kecuali jika simpul tersebut sudah ditunjuk oleh simpul yang lainnya (Link list belum terhubung).

4.            Posisi simpul terakhir pada link list selalu bernilai NIL karena ia tidak menunjuk pada  simpul yang lainnya, kecuali bentuk circular.

5.            Operasi yang dapat dilakukan pada Link List diantaranya adalah :

a.          Menambah Simpul (di Depan, Belakang dan Tengah).

b.         Menghapus Simpul (di Depan, Belakang dan Tengah).

c.          Membaca isi link list (Membaca maju dan mundur).

Struktur umum Link List dapat dilihat pada gambar 2.2 dibawah ini:

Gambar 2.2 Struktur Umum Link List

2.5. Operasi Pada Link List

Ada tiga jenis operasi pada link list, yaitu :

1.   Menambah Simpul

     Menambah simpul pada link list ada tiga macam yaitu menambah di depan, belakang dan tengah, tapi hanya penambahan yang umum dipakai saja oleh link list yang akan dibahas yaitu penambahan simpul dibelakang. Selanjutnya penambahan yang lain akan dibahas pada pertemuan-pertemuan selanjutnya. Penambahan di belakang maksudnya menambahkan simpul-simpul baru pada posisi Tail. Gambar 2.3 ini merupakan ilustrasi penambahan simpul di belakang.

 

Gambar 2.3 Ilustrasi Penambahan Simpul di Posisi Tail

             

Berikut ini merupakan procedure Tambah simpul pada Pascal :

Procedure Tambah(Var Head, Tail : PSimpul; Elemen : Char);

Var Temp : PSimpul;

Begin

      New(Temp);

      Temp^.Info := Elemen;

      If Head = NIL Then                     { Jika Link List Masih Kosong }

            Head := Temp

      Else

            Tail^.Next := Temp;                { Gambar 2.3.b. }

      Tail := Temp;                                 { Gambar 2.3.c. }

      Tail^.Next := NIL;

End;

2.   Menghapus Simpul

     Operasi menghapus simpul juga ada tiga macam yaitu menghapus simpul di depan, belakang dan tengah. Untuk menghapus sebuah simpul diperlukan satu buah tambahan variabel pointer yaitu variabel bantu yang berguna untuk menunjukkan simpul manakah yang akan dihapus. Procedure Hapus selengkapnya adalah sebagai berikut :

Procedure Hapus(Var Head, Tail : PSimpul; Elemen : Char);

Var Temp1, Temp2  : PSimpul;

Begin

     If Head = NIL Then { Jika Link List Masih Kosong }

          Writeln(‘Link List Masih Kosong’)

                 Else If Head^.Info = Elemen Then            { Simpul Pertama dihapus }

                       Begin

                             Temp2:=Head;

                             Head := Temp2^.Next;

                             Dispose(Temp2);

                       End

      Else    {Menghapus simpul tengah / }

                 Begin        {Akhir }

                       Temp1 := Head

                       { Memulai proses pencarian elemen yang akan dihapus }

                       While (Elemen <> Temp1^.Info) And (Temp1^.Next <> NIL)           Do

                       Temp1 := Temp1^.Next;

                       If Temp2 <> NIL Then                        { Jika simpul ketemu }

                             Begin

                                   { Jika Simpul yang di cari ada di tengah }

                                   If Temp2 <> Tail Then            

                                         Temp1^.Next := Temp2^.Next

                                   Else

                                   Begin

                                         Tail := Temp1;                                                                                                                                 Tail^.Next := NIL;                                                                                                                     End;                                                                                        Dispose(Temp2);

                                   End

                             Else

                                   { Simpul yang akan dihapus tidak ketemu }

                                   Writeln(‘Simpul Tidak di ketemukan !’);

                 End;

End;

3.   Membaca Isi Link List

     Ada dua jenis untuk membaca isi link list yaitu membaca maju dan membaca mundur.

a.    Membaca Maju

Membaca maju artinya membaca isi seranai beranai mulai posisi Head sampai ke posisi Tail. Berikut ilustrasi pembacaan isi simpul beserta prosedur pembacaannya :

Gambar 2.4 Ilustrasi pembacaan dari Head ke Tail

Procedure Baca_Maju(Head : PSimpul);

Var Temp : PSimpul;

Begin

      Temp := Head;

      Repeat

            Write(Temp^.Info,’  ‘);

            Temp := Temp^.Next

      Until Temp <> NIL;

End;

b.   Membaca Mundur

     Membaca mundur artinya membaca isi seranai beranai mulai posisi Tail sampai ke posisi Head. Berikut ilustrasi pembacaan isi simpul beserta prosedur pembacaannya :

 

Gambar 2.5 Ilustrasi pembacaan dari Tail ke Head

Procedure Baca_Mundur(Temp : PSimpul);

Begin

      If Temp <> NIL Then

            Begin

                  Baca_Mundur(Temp^.Next);

                  Write(Temp^.Info,’  ‘);

            End;

End;

            Ada berbagai jenis linked list, contoh diatas merupakan seranai beranai tunggal (Single Link List). Adapun jenis-jenis link list antara lain adalah :

1.   Single Link List / Link list satu arah (One Way List)

Disebut demikian karena pada setiap simpul hanya memiliki satu buah field yang berhubungan dengan simpul berikutnya. Dalam pembuatan Single Link List dapat menggunakan 2 metode, yaitu:

·         LIFO (Last In First Out), aplikasinya   : Stack (Tumpukan)

LIFO adalah suatu metode pembuatan Link List dimana data yang masuk paling akhir adalah data yang keluar paling awal.

·         FIFO (First In First Out), aplikasinya  : Queue (Antrian)

LIFO adalah suatu metode pembuatan Link List dimana data yang masuk paling awal adalah data yang keluar paling awal juga.

Link list ini memiliki beberapa variasi lain diantaranya :

a.    Header Single Link List : Jenis single link list yang memiliki simpul tambahan pada awal simpul yang berguna untuk informasi tambahan. Contoh dibawah ini merupakan header single link list yang pada simpul header-nya berisi informasi mengenai banyaknya simpul di dalam list

b.   Circular Single Link List : Jenis single link list yang tidak pernah mempunyai tail atau tidak pernah NIL selalu berputar Head = Tail;

c.    Header Circular Single Link List : Jenis circular single link list yang memiliki simpul tambahan di awal sebagai informasi tambahan. Contoh dibawah ini merupakan circular header single link list yang pada simpul headernya berisi informasi mengenai banyaknya simpul di dalam list.

2.Double Link List / Link list dua arah (Two Way List)

     Link List ini memiliki dua buah field yang digunakan untuk menunjuk ke simpul sebelumnya dan ke simpul sesudahnya. Banyak digunakan untuk mempermudah proses pencarian simpul dalam suatu seranai beranai. Link list ini memiliki beberapa variasi lain diantaranya :

a.          Header Double Link List : Jenis double link list yang memiliki simpul tambahan pada awal simpul yang berguna untuk informasi tambahan.

b.         Circular Double Link List : Jenis double link list yang tidak pernah mempunyai tail atau tidak pernah NIL selalu berputar Head = Tail;

c.          Header Circular Double Link List : Jenis circular double link list yang memiliki simpul tambahan di awal sebagai informasi tambahan.

LAPORAN PENDAHULUAN

1. Jelaskan pengertian dari:

a.      Variabel Statis

b.     Variabel Dinamis

c.      Variabel Pointer.

2. Bagaimana cara pendefinisian Variabel Pointer & Variabel Dinamis.
3. Apa yang dimaksud dengan Head, Tail dan NIL.
4. Jelaskan mengenai operasi pada pointer.
5. Jenis-jenis Link List dan operasi pada link list.

MATERI PRAKTIKUM

1. Mengetahui Variabel Statis, Dinamis dan Pointer terutama perbedaan diantara ketiganya.
2. Mengetahui jenis-jenis link list (keseluruhan jenisnya) minimal dengan menggunakan bagan/gambar atau juga dapat dengan program sederhana.
3. Membuat program-program sederhana berupa pendefinisan link list dan operasi-operasi link list.
4. Membuat program menu pulldown dengan menggunakan link list. Menu pulldown terdiri dari Create link list,  insert link list, delete link list, search link list dan exit main menu. Menu-menunya diisi semua kecuali search link list.
5. Nilai K (Keterampilan) didapat jika praktikan dapat mengisi menu pulldown search link list.

LAPORAN AKHIR

Buat Algoritma dan program sederhana dari Link List.

Kekurangannya dapat didownload pada website ILAB

Posted in: SEKILAS MATERI ILAB