struktur data . pointer & linked list

8/14/2019 Struktur Data . Pointer & Linked List

http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 1/29

Pointer & Linked List (Senarai Berantai)

08620212 - Struktur Data

Program Studi Teknik InformatikaUniversitas Muhammadiyah Gresik



Pointer

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Pointer

Tipe data yang digunakan untuk menyimpanALAMAT MEMORI (bukan data!).

Pengalokasian bersifat dinamik : dapatdibangun atau dihapus selama program

berjalan (runtime).

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Operasi-operasi terhadap variabel pointer Penugasan (Menyalin Alamat) pointvar1 := pointvar2;

Penugasan (Menyalin isi ruang yang ditunjuk olehalamat pointer) pointvar1^ := pointvar2^;

Perbandingan (operator logika)

Yang dapat digunakan hanya “=“ atau “<>”. Menghapus pointer Jika ruang yang ditunjuk oleh variabel pointer sudah tidak

diperlukan lagi, maka isi variabel pointer yang digunakansebaiknya dihapus untuk menghemat memori.

Tetapi, perlu berhati-hati. Karena jika sudah terlanjur

dihapus dan ternyata isi ruang yang ditunjuk oleh variabelpointer masih digunakan, maka akan timbul dangling pointer .

Fungsi yang digunakan –dalam pascal– adalah dispose.

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Deklarasi pointer di pascalPROGRAM PointerExample(OUTPUT);

VAR

MyIntegerPointer :^INTEGER;

MyInteger :INTEGER;

BEGIN

MyInteger := 50;

new(MyIntegerPointer); {mengalokasikan ruang untuk variabel

pointer} MyIntegerPointer^ := 500; {mengisi nilai untuk ruang yangditunjuk variabel pointer}

MyInteger := MyIntegerPointer^; { ??? }

WRITELN('The value of MyInteger is: ', MyInteger);

WRITELN('The value pointed to by MyIntegerPointer is: '

, MyIntegerPointer^);

dispose(MyIntegerPointer); {mendealokasikan ruang untuk variabel pointer}

WRITELN('Press any key to continue...');

READLN;

END.

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



PROGRAM contohPointer;

VAR

IntegerPointerku :^INTEGER;

Integerku : INTEGER;

BEGIN

Integerku := 50;

new(IntegerPointerku);

IntegerPointerku^ := 500;

Integerku := IntegerPointerku^;

WRITELN(‘Integerku = ', Integerku);

WRITELN(‘IntegerPointerku = '

, IntegerPointerku^);

dispose(IntegerPointerku);

WRITELN(‘Tekan ENTER untuk keluar...');

READLN;

END.

> Integerku = 500> IntegerPointerku = 500

> Tekan ENTER untuk keluar...

ayar Monitor :

Memori :

IntegerPointerku

Integerku

50

IntegerPointer

ku

9 (alamat)

500

500



Declaring a Pointer (C)

char *ptGrade; Data type : The data type of the memory

address stored in the pointer.

Asterisk (*) : Tells the computer that you aredeclaring a pointer.

Variable name : The name that uniquelyidentifies the pointer and is used to reference

the pointer within your program. Semicolon (;) : Tells the computer this is an

instruction (statement).

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Pointers to RecordsPROGRAM PointersToRecords(OUTPUT);

TYPE

emprec = RECORD

ID:INTEGER;

Wage: REAL;

END;

empptr = ^emprec;

VAR

ptr1, ptr2 : empptr;

BEGIN

NEW(ptr1);

NEW(ptr2);

ptr1^.ID := 123;

ptr1^.Wage := 25.5;

ptr2^.ID := 456;

ptr2^.Wage := 33.25;

………….

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Masih ada pertanyaan tentangpointer ?

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Linked List



Linked List Salah satu bentuk struktur data fundamental.

Dapat digunakan untuk membentuk struktur data yang lebihkompleks.

Serangkaian simpul/node yang berisi data dan saling terkait.

Memanfaatkan kombinasi dari tipe data pointer dan tipe datarecord/structure ( pointer to records).

Setara dengan array of record , tetapi dengan kelebihan : Alokasi memori lebih fleksibel (dinamis), karena :

Tidak perlu memindah-mindahkan data.

Tidak perlu menempatkan data secara berurut dalam ruang memori.

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



Deklarasi Linked List (Pascal)

TYPEListPointer = ^ListRecord;

ListRecord = RECORD

DataField :INTEGER;

NextField :ListPointer;

END;

VAR

FirstPointer, ToolPointer :ListPointer;

DAT A

S T R U C T URE S

L E C T U

RE

N OT E S



PROGRAM tambahsimpuldepan;

......

VAR

FirstPointer, ToolPointer :ListPointer;

BEGIN

FirstPointer := NIL;

new(ToolPointer);

WRITELN(“Masukkan Data Baru : ”);

READLN(ToolPointer^.DataField);

ToolPointer^.NextField := FirstPointer;

FirstPointer := ToolPointer;

new(ToolPointer);

WRITELN(“Masukkan Data Baru Lagi : ”);

READLN(ToolPointer^.DataField);

ToolPointer^.NextField := FirstPointer;

FirstPointer := ToolPointer;

END.

> Masukkan Data Baru : 100> Masukkan Data Baru Lagi : 300

Layar Monitor:

Memori :

FirstPointer ToolPointer

ToolPointer

9 (alamat)Ø

DataField = 100DataField = 100; NextField = Ø

9 (alamat)

ToolPointer

17 (alamat)

DataField= 300DataField = 300; NextField = 9

17 (alamat)



Bentuk-bentuk linked listDAT A

S T R U C T URE S

L E C T URE

N OT E S



Singly-linked list

Satu simpul/node memiliki sebuah variabelpointer yang digunakan untuk menunjuk padasimpul/node berikutnya.

DAT A

S T R U C T URE S

L E C T URE N OT E S



Doubly-linked list

Satu simpul/node menyimpan dua variabel bertipepointer. Satu pointer menunjuk ke simpul/node berikutnya.

Pointer yang lain menunjuk ke simpul/node sebelumnya.

Varian : Multiply-Linked List

Jumlah variabel pointer yang dimiliki masing-masingsimpul lebih dari dua.

DAT A

S T R U C T URE S




Headed linked list

Simpul pertama tidak diisi dengandata, tetapi diisi dengan informasiyang berhubungan dengan metadatalinked list

DAT A

S T R U C T URE S




Operasi-operasi terhadap linked list

Menambah Simpul/Node Baru Menambah di depan.

Menambah di tengah.

Menambah di belakang.

Menghapus Simpul/Node Menghapus di depan.

Menghapus di tengah.

Menghapus di belakang.

Membaca isi simpul/node. Membaca maju

Membaca mundur

DAT A

S T R U C T URE S




Menambah (simpul) di depanDAT A

S T R U C T URE S




Menambah (simpul) di tengahDAT A

S T R U C T URE S


G 49

6 20 1

awal bantu

F 20 I Ø

H Ø

baru^.next := bantu^.next;

bantu^.next := baru;

baru

1

49



Menambah (simpul) di belakangDAT A

S T R U C T URE S


G Ø

6 20 1

awal bantu

F 20 H

baru^.next := NIL;


baru

1 Ø



Menghapus (simpul) di depanDAT A

S T R U C T URE S


G 49

6

awal

F 20 I Ø

bantu := awal^.next;

awal^.next := NIL;

awal := bantu;

bantu := NIL

20

bantu

Ø

20 Ø



Menghapus (simpul) di tengahDAT A

S T R U C T URE S


G 49

6 20 Ø

awal bantu

F 20 I Ø



baru

1



Menghapus (simpul) di belakangDAT A

S T R U C T UR

E S


G 49

6 20 1

awal bantu

F 20 I Ø

H Ø



baru

1

49



Membaca maju (linked list)DAT A

S T R U C T UR

E S


G 49

6

awal bantu

F 20 I 1 H Ø

bantu := awal;

while bantu <> NIL

begin

writeln (bantu^.data);

bantu := bantu^.next ;

end;

CEK !!6

2049

1Ø



Struktur data yang dibangun denganLinked List

Dynamic Hash Table. Struktur Pohon (Tree)

Heap Lebih sering diimplementasikan dengan array

DAT A

S T R U C T UR

E S




Linked Lists vs Arrays

Arrays Linked Lists

Memperbolehkan melakukanpengaksesan secara random

Hanya memperbolehkanpengaksesan secara sekuensialterhadap elemen

Tidak memerlukan ruangpenyimpanan ekstra untukmenyimpan alamat memori

Memerlukan ruang penyimpananekstra untuk reference (penyimpanalamat memori)

Tidak bisa dirubah ukuranalokasi memorinya

Ukuran alokasi memori dapat diubahsesuai dengan kebutuhan

DAT A

S T R U C T UR

E S




Pertanyaan ? DAT A

S T R U C T UR

E S


struktur data . pointer & linked list

Documents