Concept and Implementation Code: Linked List

Angelia
2301854492
COMP6048 - CB01

Pada pertemuan F2F ke-2 di kelas besar, sesi ini penuh diberikan oleh Pak Ferdinand. Pembahasan kali ini merupakan topik lanjutan dari sesi Linked List. Berikut ini beberapa ringkasan yang saya buat dari pembahasan yang diberikan:

A. Konsep Linked List
Linked List itu berarti serangkaian data yang terhubung dengan data lain melalui penyimpanan alamat memori data sebelum/selanjutnya dengan pointer prev/next.


Alamat memori bisa dipesan dengan menggunakan malloc, yang di-assign ke current.
Pemesanan memori tersebut sebesar struct data yang digunakan.
Dalam memori tersebut, bisa diibaratkan seperti ada sebuah gerbong dengan 3 sekat, seperti gambar berikut:
Sumber: https://www.mahirkoding.com/
Penjelasan:
Head selalu ada di awal rangkaian data.
Tail berada di paling akhir rangkaian data.
Kotak besar diibaratkan sebagai gerbong yang memiliki 3 sekat, merupakan memori yang dipesan.
Bagian kotak warna putih merupakan value dari alamat memori.
'NEXT' akan diisi dengan alamat memori data selanjutnya. Untuk 'NEXT' pada rangkaian data paling akhir akan diisi NULL. (tail->next = NULL)
'PREV' akan diisi dengan alamat memori data sebelumnya. Untuk 'PREV' pada rangkaian data paling awal akan diisi NULL. (head->prev = NULL)

Perbedaan Single Linked List dengan Double Linked List terletak pada pointer 'PREV' dimana Single Linked List tidak menggunakan pointer 'PREV' sedangkan Double Link List menggunakan pointer 'PREV' dan 'NEXT' untuk mengakses data.

B. Implementasi Source Code
Dalam pengimplementasian kode, sangat sulit untuk menemukan error karena mayoritas error yang terjadi hanya bisa diketahui setelah program dijalankan (Run Error). Beberapa hal yang menjadi penyebab error adalah:
1. Lupa memberi null untuk *prev dari head dan *next dari tail
2. Logic algorithmnya salah sehingga data yang tercetak berbeda dari yang seharusnya/app crash

Berikut ini source code beserta penjelasannya:

#include<stdio.h>
#include<stdlib.h>

//Awalnya dibuat struct untuk data, kemudian pendeklarasian struct untuk head, current, dan tail. Selain itu, struct Data juga bisa dideklarasi untuk tambahan pointer lain yang akan berguna.
struct Data
{
    int value; //Akan digunakan untuk mengisi value
    struct Data *next,*prev; //Pointer untuk menunjuk alamat memori data sebelumnya (*prev) dan alamat memori data selanjutnya (*next)
}*head,*curr,*tail;

//1. Fungsi Push (Insert Belakang)
//Bedanya untuk Single Linked List dengan Double Linked List
//Single Linked List, penghubungnya hanya 1 yaitu pointer *next
//Double Linked List, penghubunganya dengan *next dan *prev
void push(int a)
{
    //Memesan memori sebesar struct data
    curr = (struct Data*)malloc(sizeof(struct Data));
    //Value dari alamat memori current adalah a
    curr->value = a;
    
    //Cek apakah linked list baru saja dibuat, tandanya head pasti null
    if(head==NULL){
        //Buat head dan tail berada di alamat memori yang sama dengan current
        head = tail = curr;
    }
    else{
        //Kalau data sudah pernah ada, maka assign gerbong yang terdapat tail dengan meng-assign pointer next yaitu alamat memori current
        tail->next = curr;
        //Assign gerbong current dengan pointer prev yaitu alamat memori dari tail sekarang
        curr->prev = tail;
        //Assign tail untuk pindah ke posisi gerbong sama dengan current
        tail = curr;
    }
    //Pastikan bahwa pointer prev dari head dan pointer next dari tail adalah NULL untuk menghindari crash
    head->prev = tail->next = NULL;
}

//2. Fungsi Pop 
//Pop Belakang jika tidak ada pointer *prev (utk Single Linked List)
void popBelakang()
{
    //Pertama, buat posisi current berada di head
    curr = head;
    
    //Kalau data tinggal satu
    if(tail == head){
        //Hapus alamat memori sekarang. Bisa menggunakan curr/head/tail untuk free karena berada di alamat memori yang sama
        free(curr);
        //Pastikan bahwa head, tail, dan current adalah null agar app tidak crash
        tail = head = curr = NULL;
    }
    //Apabila data masih tersisa lebih dari satu
    else{
        while(curr->next != tail){
            //Selamat *next dari current bukanlah tailnya maka looping maju terus dari current
            curr = curr->next;
        }
        //Posisi current setelah keluar dari while adalah current sekarang berada di sebelum tail
        //Hapus alamat memori data paling akhir (tail)
        free(tail);
        //Set tail mundur menjadi posisi current yang sekarang
        tail = curr;
        //Pastikan bahwa *next dari tail adalah NULL untuk menghindari crash
        tail->next = NULL;
    }
}

//Pop Belakang jika ada pointer *prev (utk Double Linked List)
void popBelakang2() 
{
    //Kalau data tinggal satu
    if(tail == head){
        //Hapus alamat memori sekarang. Bisa menggunakan curr/head/tail untuk free karena berada di alamat memori yang sama
        free(curr);
        //Pastikan bahwa head, tail, dan current adalah null agar app tidak crash
        tail = head = curr = NULL;
    }
    else
    {
        //Mundurin tail ke belakang 1 langkah
        tail = tail->prev;
        //Hapus memori yang posisinya ada di setelah tail (posisi tail sebelumnya, bukan yang sekarang)
        free(tail->next);
        //Pastikan bahwa *next dari tail adalah NULL untuk menghindari crash
        tail->next = NULL;
    }
}

//3. Print Linked List
void cetak()
{
    //Buat posisi current sama dengan posisi head
    curr = head;
    while(curr!=NULL){
        //Selama current bukan null, maka print value dari alamat memori yang posisi current
        printf("%d\n",curr->value);
        //Setelah print, majukan posisi current
        curr = curr->next;
    }
}

int main()
{
    push(10);
    push(20);
    push(30);
    push(40);
    
    cetak();
    //Hasil = 10, 20, 30, 40
    popBelakang();
    popBelakang2();
    cetak();
    //Hasil = 10, 20
    push(50);
    cetak();
    //Hasil = 10, 20, 50

    getchar();
    return 0;
}

Untuk implementasi code yang lebih lengkap ada di post blog saya yang sebelumnya
Pertemuan F2F ke-1 :

Demikian pembahasan rangkuman materi yang saya dapatkan hari ini. Mohon maaf apabila ada kesalahan.
Terima kasih.

Angelia
2301854492
COMP6048 - CB01
Referensi Materi:
Kelas Besar Data Structure (03/03/20)
https://www.mahirkoding.com/

Comments

Post a Comment

Popular Posts