inf202: struktur data linked list (senarai · pdf file1. dasar teori linked list merupakan...

Click here to load reader

Post on 24-Aug-2019

247 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • Pertemuan 12:

    INF202: Struktur Data

    LINKED LIST (Senarai

    Berantai)

    Dosen: Wayan Suparta, PhD

  • 1. Dasar Teori

     Linked List merupakan deretan elemen yang

    berdampingan di memori namun masih terpencar-pencar.

     Untuk mengakses semua elemen digunakan pointer

    tunggal.

     Masing-masing elemen terdiri dari dua bagian, yaitu

    sebuah data dan sebuah pointer yang disebut dengan

    pointer next.

     Dengan menggunakan struktur two-member seperti ini,

    linked list dibentuk dengan cara menunjuk pointer next

    suatu elemen ke elemen yang mengikutinya. Pointer next

    pada elemen terakhir merupakan NULL, yang

    menunjukkan akhir dari suatu list.

     Elemen pada awal suatu list disebut head, dan elemen

    terakhir dari suatu list disebut tail.

  •  Ketika sebuah variabel dideklarasikan, terlebih dahulu

    harus diinisialisasi termasuk juga ’pengalokasian secara

    dinamis’.

     Fungsi untuk mengalokasikan sebuah node baru: fungsi

    allocate_node() menggunakan malloc() untuk

    mendapatkan memori aktual, yang akan menginisialisasi

    suatu field data.

     next selalu diinisialisasi sebagai NULL.

     Untuk melihat kemungkinan alokasi memori gagal, maka

    fungsi allocate_node menghasilkan 0, sebaliknya 1 jika

    berhasil.

     Untuk membebaskan node digunakan fungsi free_node.

    Fungsi dari alokasi node adalah sebagai berikut :

  •  Inisialisasi LIST setelah alokasi untuk node pertama sebagai

    berikut:

     Fungsi free_node() akan menghancurkan node yang

    menunjuk ke pointer yang dilewati karena itu pointer

    didefinsikan dengan NULL:

  • 2. Operasi Pada Linked List

     Opearsi penting pada Linked List:

     Insert

     Delete

     Fungsi INSERT meliputi

     insert sebagai node awal (head) dari linked list

     insert setelah node tertentu

     insert sebelum node tertentu

     insert sebagai node akhir (tail) dari linked list.

     Fungsi DELETE meliputi

     delete sebagai simpul pertama(head) dari linked list

     delete setelah simpul tertentu

     delete simpul terakhir

  • (a) Insert sebagai node awal (head) dari linked list

  • (b) Insert setelah node tertentu

  • (c) Insert sebelum node tertentu

    Statement untuk insert setelah node tertentu dari linked list adalah

  • (d) Insert di akhir (tail) dari linked list

  • do

  • (2) Fungsi DELETE

    (a)

    Langkah

    penghapusan

    1. Pointer first

    diarahkan data

    ke-2

    2. Pointer p

    diarahkan pada

    data ke-1

    3. Bebaskan

    pointer p

    (secara otomatis

    data ke-1

    terhapus)

  • (b)

  • (c)

    Langkah-langkah untuk proses di atas adalah sebagai berikut:

    1. Telusuri simpul s/d first->next = NULL

    2. Arahkan pointer p ke first

    3. Bebaskan pointer p->next (Simpul Terakhir)

    4. Arahkan p->next ke NULL

  • 3. MERUBAH ISI DARI SUATU SIMPUL PADA

    LINKED LIST

    1. Menulusuri linked list sampai didapatkan simpul yang akan dirubah.

  • Contoh KASUS Polinomial

     Pertimbangkan dua polinomial f(x) dan g(x), yang dapat diwakili

    menggunakan linked list.

     h (x) dapat direpresentasikan dengan h(x)= f(x)+ g(x)=

    f(x) = ax3 + bx + c dan g(x) = mx4 + nx3 + ox2 + px + q

    Yaitu menambahkan konstanta dari polynomial yang sesuai dari

    eksponensial sama.

     Kedua polinomial dapat ditambahkan dengan:

    h(x)= f(x)+ g(x)= mx4 + (a + n) x3 + ox 2 + (b + p)x + (c + q)

    yaitu menambahkan konstanta dari polinomial yang sesuai dari

    eksponensial sama.

     Hasil dari H(x) dapat dijabarkan seperti gambar berikut:

    http://4.bp.blogspot.com/-ZdJyVIiJwb8/T3lEEod1rbI/AAAAAAAAAJU/czA52ZHe4kY/s1600/1.jpg http://1.bp.blogspot.com/-Uvj1PBMdGBQ/T3lEtdvbe3I/AAAAAAAAAJc/YGZM8Gvdc_Q/s1600/2.jpg http://4.bp.blogspot.com/-ZdJyVIiJwb8/T3lEEod1rbI/AAAAAAAAAJU/czA52ZHe4kY/s1600/1.jpg http://1.bp.blogspot.com/-Uvj1PBMdGBQ/T3lEtdvbe3I/AAAAAAAAAJc/YGZM8Gvdc_Q/s1600/2.jpg

  • Contoh Program 1:

    Menambah data di depan dan di akhir

    //Program linked list for Node Insert Kiri dan Insert Kanan #include #include #include #include using namespace std; struct node { int urut; node *next; }; node *awal_ptr = NULL; node *posisi; //digunakan untuk membaca sepanjang list int option = 0;

    //Tambah data di depan void tambah_awal_list() { node *baru; baru = new node; cout > baru->urut; baru->next = NULL; if(awal_ptr == NULL) { awal_ptr=baru; awal_ptr->next = NULL; } else { baru->next = awal_ptr; awal_ptr = baru; } }

  • //Tambah data di akhir

    void menambah_node_di_akhir()

    {

    node *temp, *temp2; // Temporary pointers

    // menciptakan node baru

    temp = new node;

    cout > temp->urut;

    temp->next = NULL;

    // Set up link pada node

    if (awal_ptr == NULL) {

    awal_ptr = temp;

    posisi = awal_ptr; }

    else

    { temp2 = awal_ptr;

    // node tidak NULL – list tidak kosong

    while (temp2->next != NULL)

    { temp2 = temp2->next;

    // Memindahkan pada next link dalam rantai

    }

    temp2->next = temp; }

    }

    //Menampilkan data

    void display_list()

    {

    node *temp;

    temp = awal_ptr;

    cout

  • //Inisialisasi Nilai

    int init(int nilai){

    node *baru;

    baru = new node;

    baru->urut=nilai;

    baru->next = NULL;

    if(awal_ptr == NULL)

    {

    awal_ptr=baru;

    awal_ptr->next = NULL;

    }

    else

    {

    baru->next = awal_ptr;

    awal_ptr = baru;

    }

    }

    //Program Utama

    int main()

    {

    cout

  • switch (option)

    {

    case 1 : tambah_awal_list();

    break;

    case 2 : menambah_node_di_akhir();

    break;

    }

    }

    while (option != 3);

    }

    Output Program:

    Tambah data kiri: Tambah data kanan:

  • Contoh Program 2: Fungsi lainnya

    //Hapus data di depan

    void hapus_awal_node()

    {

    node *temp;

    temp = awal_ptr;

    awal_ptr = awal_ptr->next;

    delete temp;

    }

    //Hapus data di akhir

    void hapus_akhir_node()

    {

    node *temp1, *temp2;

    if (awal_ptr == NULL)

    cout next != NULL)

    {

    temp2 = temp1;

    temp1 = temp1->next;

    }

    delete temp1;

    temp2->next = NULL;

    }

    }

    }

  • //Pindah pointer ke posisi sebelumnya

    void pindah_posisi_sebelumnya()

    {

    if (posisi->next == NULL)

    cout next; }

    posisi = previous; }

    }

    //Tambah data di tengah

    void tambah_tengah_list()

    { node *baru, *bantu;

    int posisi_sisip;

    if(awal_ptr != NULL) {

    cout>posisi_sisip;

    baru =new node;

    bantu=awal_ptr;

    for(int i=1;inext != NULL)

    bantu=bantu->next;

    else

    break; }

    cout > baru -> urut;

    baru->next = bantu -> next;

    bantu->next=baru; }

    else

    { cout

  • //Hapus data di posisi tengah

    void Hapus_tengah_list()

    {

    int bykdata,posisi_hapus,poshapus;

    node *hapus, *bantu;

    if(awal_ptr != NULL)

    {

    coutposisi_hapus;

    bykdata=1;

    bantu=awal_ptr;

    while(bantu->next != NULL)

    {

    bantu=bantu->next;

    bykdata++;

    }

    if((posisi_hapusbykdata))

    {

    coutnext;

    bantu->next=hapus->next;

    delete hapus;

    }

    }

    else

    cout

  • //Program Utama Lengkap

    display_list();

    cout

  • LATIHAN 18 A. Diketahui:

    P1 = 6x8 + 8x7 + 5x5 + x3 + 15

    P2 = 3x9 + 4x7 + 3x4 + 2x3 + 2x2 + 10

    P3 = x2 + 5

    Representasikan bilangan polinom dengan menggunakan

    linked list dan buatlah prosedur-prosedur untuk :

    • Menyisipkan simpul di awal jika pangkat yang dimasukkan

    lebih dari pangkat tertinggi dari bilangan polinomial.

    • Menyisipkan simpul di tengah jika pangkat dari bilangan yang

    kita sisipkan berada di tengah.

    • Menyisipkan simpul di akhir jika pangkat dari bilangan yang

    disisipkan adalah 0.

    • Menghapus simpul, baik di awal, di tengah, ataupun di akhir.