heru blog: POINTER DAN LINKED LIST

2.1.1 Definisi Pointer

Pointer(variable pointer) merupakan suatu variable yang menyimpan alamat suatu objek/variable lain berupa data tunggal atau sebuah record (node). Karenanya ,biasa di katakana bahwa pointer bukan berisi data, Pointer merupakan variabel level rendah yang dapat digunakan untuk menunjuk nilai integer, character, float, double, atau single, dan bahkan tipe-tipe data lain yang didukung oleh bahasa C. Variabel biasa, sifatnya statis dan sudah pasti, sedangkan pada pointer sifatnya dinamis dan dapat lebih fleksibel. Variabel pointer yang tidak menunjuk pada nilai apapun berarti memiliki nilai NULL, dan disebut sebagai dangling pointer karena nilainya tidak diinisialisasi dan tidak dapat diprediksi.melainkan berisi alamat dari suatu data .

Perhatikanlah ilustrasi berikut:

R adalah pointer yang menunjuk record Dewi ,V adalah pointer ke record Dita. Pointer juga bersifat fleksibel ,misalnya dua pointer dapat menunjuk pada record yang sama ,seperti T dan U yang menunjuk record Dedek . Namun pointer juga dapat tidak menunjuk ke suatu record apapun (nil) seperti pointer S. dari sifat pointer yang fleksibel ,kita juga harus berhati_hati dalam memindahkan arah pointer agar jangan sampai ada record yang hilang .record Diah merupakan record yang hilang sebab tidak ada pointer yang menunjuk kepadanya .

Sebagian besar bahasa pemograman menyediakan fasilitas untuk memproses pointer ,prosedur prosedur standart untuk meminta alokasi memori tambahan ,serta melepaskan memori selama pemograman di jalankan. Contoh lain variable pointer.

P adalah variabel pointer yang menunjuk ke alamat memori 100 yang berisi data bertipe string “Aku”. Apabila anda ingin menambah data dengan menggunakan variabel yang berbeda, maka anda dapat mendeklarasikan variabel pointer baru misalnya Q dan R dst sehingga tampak sbb :

2.1.2 Deklarasi Pointer

Deklarasi:Karena pointer merupakan sebuah type data, maka pen-deklarasi-an pointer berada pada bagian type.

Bentuk:Type pengenal = ^simpul;

Simpul = tipe;

Contoh : type bil_bulat = ^integer;

var i, j : bil_bulat;

Umumnya tipe berupa rekaman (struktur) record, misal deklarasi :

Type str30 = string[30];

point = ^data;

data = record

nomer : integer;

nama_peg : str30;

alamat : str30;

pekerjaan : str30;

end;

Kemudian bentuk definisinya :

var P1, P2 : point;

a,b,c : str30;

Agar nampak bahwa P1 dan P2 bersifat dinamis terhadap kebutuhan memori, deklarasi di atas

dimodifikasi sebagai berikut :

Type str30 = string[30];

point = ^data;

data = record

nomer : integer;

nama_peg : str30;

alamat : str30;

pekerjaan : str30;

next : point; {elemen ini baru}

end;

Setelah pendefinisian, kemudian minta memori kepada sistem dengan perintah :

new (P1); new (P2);

maka P1 dan P2 sekarang siap diakses. Di sini ada dua elemen yang perlu dibedakan. Pertama untuk isi

data sedangkan komponen kedua untuk pointer yang menunjuk kepada elemen berikutnya. Karena P1

dan P2 dalam hal ini hanya masih berdiri sendiri, maka elemen kedua P1 dan P2 sesuai definisi masingmasing

menunjuk ke NIL ( Not In List, tak ada elemen yang mengikuti).

2.1.3 Operasi pada pointer

Secara umum ada 2 operasi dasar yang dapat di lakukan terhadap pointer, yaitu:

Ø Mengkopi pointer

Ø Mengkopi isi simpul

Untuk memahami kedua operasi tersebut ,perhatikan contoh berikut. Pertama kali kita deklarasikan tipe pointer, yaitu:

Pada deklarasi di atas , pointer T! dan T2 mempunyai deklarasi simpul yang sama sehingga memnuhi syarat untuk kedua operasi tersebut . sekarang ,jika kita memberikat statement:

Kita mempunyai 2 simpul ,yaitu:

Dengan menggunakan statement:

Maka keadaan 2 simpul di atas berubah menjadi:

Statement statement yang tidak di izinkan dalam operasi simpul adalah:

Sebab statement pemberian nilai hanya dapat dilakukan terhadap peubah –peubah dengan tipe data yang sama.

2.1.3.1 Operasi Mengkopi Pointer

Operasi mengkopi pointer akan mengakibatkan sebuah simpul akan di tunjuk oleh lebih dari satu pointer .

Bentuk deklarasi statement:

Setelah statement tersebut di jalankan ,keadaan memori berubah menjadi:

Dari gambar diatas bisa kita perhatikan bahwa sekarang pointer T2 juga menunjuk ke simpul yang di tunjuk oleh pointer T1. Simpul yang semula di tunjuk oleh pointer T2 menjadi lepas. Simpul yang sudah terlepas tidak dapat di akses lagi karena tidak di kerahui lagi lokasinya ,kecuali pada pointer lain yang menunjuk.

Selain operasi pemberian nilai ( := ) , operasi –operaso pembandingan juga dapat di berikan trhadap data bertipe pointer. Tatapi operator pembandingan yang boleh = dan <>. Sebagai contoh:

2.1.3.2 Mengkopi isi simpul

Operasi mengkopi isi simpul akan mengakibatkan dua atau lebih simpul yang di tunjuk oleh pointer yang berbeda akan memiliki isi yang sama.

Bentuk deklarasi statemen:

Maka hasil yang di peroleh:

2.1.4 Menghapus pointer

Suatu pointer yang telah dialokasikan pada waktu program dieksekusi ,dapat didealokasikan kembali pada saat eksekusi program tersebut . setelah suatu pointer di hapus , maka lokasi yang semula di tempati oleh simpul yang di tunjuk oleh pointer tersebut akan bebas dan dapat digunakan oleh peubah yang lain.

Deklarasi penghapusan suatu pointer:

Dengan peubah adalah sembarang peubah yang bertipe pointer.

Masih mengunakan contoh-contoh di atas ,misalnya pointerT2 sudah tidak digunakan lagi, maka pointer ini dapat di hapuis dengan statement:

2.1.5 Contoh program

Contoh 1

Ketika p menunjuk ke m ( p:=@m;), mengakses p^{^} sama dengan mengakses m.

Contoh 2:

Pada blok begin ….end blok,terlihat bahwa meskipun p tidak menunjuk pada suatu variable ,tetapi dapat diisi dengan nilai.

Pernyataan new(p); tidak memerlukan alokasi memori . setelah itu kita bsia melakukan apapun pada variable tersebut sampai kita membuangnya dari memori dengan memakai perintah sipose(p);. Variable dengan cara ini dinamakan dengan dynamic variable.

LINKED LIST

2.2.1 DEFINISI linked list

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 :

2.2.2 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 :

NODE(P) = node yang ditunjuk oleh P yaitu node pertama.

INFO(P) = A

NEXT(P) = node ke-dua INFO(NEXT(NEXT(P))) = C

2.2.3 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

2.2.4 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;