struktur data . pointer & linked list

Click here to load reader

Post on 30-May-2018

223 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • 8/14/2019 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

    2/29

    Pointer

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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).

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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 danglingpointer.

    Fungsi yang digunakan dalam pascal adalah dispose.

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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 untukvariabel pointer}

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

    READLN;

    END.

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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

    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).

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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;

    .

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

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

    9/29

    Masih ada pertanyaan tentangpointer ?

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

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

    10/29

    Linked List

  • 8/14/2019 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.

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

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

    12/29

    Deklarasi Linked List (Pascal)

    TYPEListPointer = ^ListRecord;

    ListRecord = RECORD

    DataField :INTEGER;

    NextField :ListPointer;

    END;

    VAR

    FirstPointer, ToolPointer :ListPointer;

    DATA

    STRUCTURES

    LECTU

    RE

    NOTES

  • 8/14/2019 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

    14/29

    Bentuk-bentuk linked listDATA

    STRUCTURES

    LECTURE

    NOTES

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

    15/29

    Singly-linked list

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

    DATA

    STRUCTURES

    LECTURENOTES

  • 8/14/2019 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.

    DATA

    STRUCTURES

    LECTURENOTES

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

    17/29

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

    18/29

    Headed linked list

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

    DATA

    STRUCTURES

    LECTURENOTES

  • 8/14/2019 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

    DATA

    STRUCTURES

    LECTURENOTES

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

    20/29

    Menambah (simpul) di depanDATA

    STRUCTURES

    LECTURENOTES

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

    21/29

    Menambah (simpul) di tengahDATA

    STRUCTURES

    LECTURENOTES

    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

    22/29

    Menambah (simpul) di belakangDATA

    STRUCTURES

    LECTURENOTES

    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

    23/29

    Menghapus (simpul) di depanDATA

    STRUCTURES

    LECTURENOTES

    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

    24/29

    Menghapus (simpul) di tengahDATA

    STRUCTURES

    LECTURENOTES

    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

    25/29

    Menghapus (simpul) di belakangDATA

    STRUCTUR

    ES

    LECTURENOTES

    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

    26/29

    Membaca maju (linked list)DATA

    STRUCTUR

    ES

    LECTURENOTES

    G 49

    6

    awal bantu

    F 20 I 1 H