Download - 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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 2/29
Pointer
DAT A
S T R U C T URE S
L E C T U
RE
N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 3/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 4/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 5/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 6/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 7/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 8/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 9/29
Masih ada pertanyaan tentangpointer ?
DAT A
S T R U C T URE S
L E C T U
RE
N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 10/29
Linked List
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 11/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 12/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 13/29
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)
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 14/29
Bentuk-bentuk linked listDAT A
S T R U C T URE S
L E C T URE
N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 15/29
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
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 16/29
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
L E C T URE N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 17/29
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 18/29
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
L E C T URE N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 19/29
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
L E C T URE N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 20/29
Menambah (simpul) di depanDAT A
S T R U C T URE S
L E C T URE N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 21/29
Menambah (simpul) di tengahDAT A
S T R U C T URE S
L E C T URE N OT E S
G 49
6 20 1
awal bantu
F 20 I Ø
H Ø
baru^.next := bantu^.next;
bantu^.next := baru;
baru
1
49
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 22/29
Menambah (simpul) di belakangDAT A
S T R U C T URE S
L E C T URE N OT E S
G Ø
6 20 1
awal bantu
F 20 H
baru^.next := NIL;
bantu^.next := baru;
baru
1 Ø
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 23/29
Menghapus (simpul) di depanDAT A
S T R U C T URE S
L E C T URE N OT E S
G 49
6
awal
F 20 I Ø
bantu := awal^.next;
awal^.next := NIL;
awal := bantu;
bantu := NIL
20
bantu
Ø
20 Ø
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 24/29
Menghapus (simpul) di tengahDAT A
S T R U C T URE S
L E C T URE N OT E S
G 49
6 20 Ø
awal bantu
F 20 I Ø
baru^.next := bantu^.next;
bantu^.next := baru;
baru
1
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 25/29
Menghapus (simpul) di belakangDAT A
S T R U C T UR
E S
L E C T URE N OT E S
G 49
6 20 1
awal bantu
F 20 I Ø
H Ø
baru^.next := bantu^.next;
bantu^.next := baru;
baru
1
49
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 26/29
Membaca maju (linked list)DAT A
S T R U C T UR
E S
L E C T URE N OT 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Ø
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 27/29
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
L E C T URE N OT E S
8/14/2019 Struktur Data . Pointer & Linked List
http://slidepdf.com/reader/full/struktur-data-pointer-linked-list 28/29
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
L E C T URE N OT E S