Linked List ~ Pemrograman dan Teknologi

Linked list atau daftar berantai merupakan sebuah struktur data yang terdiri dari serangkaian data berupa record atau struct yang dihubungkan oleh salah satu anggotanya dengan menggunakan pointer. Perhatikan struct dibawah ini.

struct link{
int data;
struct link *next;
};

Linked list harus memiliki anggota berupa pointer yang menunjuk struct yang sama anggotanya. Dalam linked list, anggota struct dengan tipe data pointer digunakan untuk menghubungkan satu struct dengan struct lainnya. Pada contoh di atas, pointer / penunjuknya adalah next.

Cara Membuat Linked List

Linked list bisa dibuat dengan mengalokasikan memori menggunakan malloc yang terdapat dalam header "stdlib.h". Function malloc digunakan untuk mengalokasikan memori sesuai ukuran struct.

Sebelum menggunakan malloc untuk membuat linked list, perhatikan dua struct dalam kode program di bawah ini!

#include <stdio.h>

struct link{
    int data;
    struct link *next;
}struct1, struct2;

int main(){
    struct1.data=2;
    struct2.data=4;
    struct1.next=&struct2;
    printf("Struct1 : %d\n", struct1.data);
    printf("Struct2 : %d\n", struct1.next->data);//bisa juga ditulis printf("Struct2 : %d\n", struct2.data)
    return 0;
}

Kode program di atas menggunakan next sebagai anggota yang berupa pointer untuk menghubungkan struct1 dan struct2. Untuk menggunakan data pada struct2, kalian bisa menggunakan struct2.data. Tapi, cara seperti itu adalah "cara biasa" yang tidak menggunakan pointer.

Jika kalian menggunakan pointer next pada struct1 untuk menunjuk struct2, kalian bisa menggunakan struct1.next->data. Kalau belum ada struct lain yang ditunjuk pointer next, programnya akan menghasilkan error.

Ingat! Selain untuk menunjuk variabel yang sudah ada, kita juga bisa menggunakan pointer untuk menunjuk lokasi tertentu di dalam memori yang sudah dialokasikan dengan function malloc().

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

struct link{
    int data;
    struct link *next;
}structku;

int main(){
    structku.data=2;
    structku.next=(link*)malloc(sizeof(link));//alokasikan memori untuk ditunjuk oleh next
    structku.next->data=4;
    printf("Struct1 : %d\n", structku.data);
    printf("Struct2 : %d\n", structku.next->data);
    free(structku.next);
    return 0;
}

Penggunaan struct dan alokasi memori adalah dasar dari linked list. Linked list bisa kita gunakan untuk menghubungkan data-data berupa struct yang ada di dalam memori komputer. Untuk membuat data baru, kita cukup mengalokasikan memori dan menghubungkan data baru dengan data yang sudah ada atau data yang sudah ditunjuk. Linked list membuat penyimpanan data jadi lebih dinamis jika dibandingkan dengan array.

Menampilkan Data Linked List dengan Perulangan
Isi linked list akan lebih mudah ditampilkan dengan perulangan. Untuk menggunakan linked list dalam perulangan, data terakhir perlu ditandai dengan suatu cara. Cara yang biasa digunakan untuk menandai akhir linked list adalah dengan menggunakan pointer bernilai NULL / 0. Nilai 0 atau Null pada pointer bisa digunakan untuk menandakan bahwa pointer tidak menunjuk alamat memori manapun.

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

struct link{
    int data;
    struct link *next;
}structku;

struct link *penunjuk;

int main(){
int i=0;
    structku.data=2;
    //struct kedua
    structku.next=(link*)malloc(sizeof(link));//alokasikan memori untuk ditunjuk oleh next
    structku.next->data=4;
    //struct ketiga
    structku.next->next=(link*)malloc(sizeof(link));//alokasikan memori untuk ditunjuk oleh next
    structku.next->next->data=6;
    structku.next->next->next=0;//akhir data linked list

    //tampilkan isi struct
    penunjuk=&structku;
    while(penunjuk!=0){
        i++;
        printf("Struct ke-%d : %d\n", i, penunjuk->data);
        penunjuk=penunjuk->next;
    }

    free(structku.next);
    free(structku.next->next);
    return 0;
}

Perulangan yang bisa kita gunakan untuk menampilkan linked list adalah while. Sebelum menggunakan while untuk menampilkan linked list, data pertama perlu disimpan pada variabel yang akan kita gunakan sebagai penunjuk sekaligus iterator. Variabel penunjuk pada contoh di atas akan bernilai 0 atau NULL pada akhir perulangan sesuai syarat dalam kondisi perulangan.

Selain untuk menampilkan isi struct dalam linked list, kalian juga bisa menggunakan perulangan untuk menambah dan menghapus data linked list. Pada contoh di bawah ini, kita akan menambah, menampilkan dan menghapus semua isi linked list dengan menggunakan perulangan.

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

struct link{
    int data;
    struct link *next;
}structku, *penunjuk, *prev;

int main(){
int i=1;
int n=10;
    printf("Masukkan jumlah data!\n");
    scanf("%d", &n);//masukkan jumlah data yang diinginkan
    //buat linked list
    penunjuk=&structku;
    while(i<n){
        penunjuk->data=i*2;
        penunjuk->next=(link*)malloc(sizeof(link));
        penunjuk=penunjuk->next;
        i++;
    }
    penunjuk->next=0;
    penunjuk->data=i*2;

    //tampilkan isi struct dalam linked list
    i=0;
    penunjuk=&structku;
    while(penunjuk!=0){
        i++;
        printf("Struct ke-%d : %d\n", i, penunjuk->data);
        penunjuk=penunjuk->next;
    }
    //bebaskan semua memori yang sudah digunakan
    penunjuk=structku.next;
    while(penunjuk!=0){
        prev=penunjuk;
        penunjuk=penunjuk->next;
        free(prev);
    }
    return 0;
}

Jenis-jenis Linked List

Linked list minimal akan memerlukan satu pointer. Pointer tersebut bisa digunakan untuk menunjuk data sebelumnya atau data berikutnya. Linked list dengan satu pointer ada dua macam. Jenis-jenis linked list tersebut yaitu :

First In First Out (FIFO) / Queue / Antrian
Data dalam linked list jenis ini penunjuknya menunjuk data berikutnya. Sesuai namanya, linked list dengan jenis ini mirip dengan antrian. Penghapusan data dimulai dari bagian paling depan atau data yang lebih dulu ditambahkan.
Last In First Out (LIFO) / Stack / Tumpukan
Data dalam linked list jenis ini penunjuknya menunjuk data sebelumnya. Sesuai namanya, linked list dengan jenis ini mirip dengan tumpukan. Penghapusan data dimulai dari bagian paling atas atau data yang ditambahkan paling akhir.

Selain linked list dengan satu pointer, ada juga linked list yang memiliki dua pointer atau lebih. Linked list yang memiliki dua pointer sebagai penunjuk data sebelumnya dan berikutnya disebut Doubly Linked List.

struct link{
     int bulat;
     float pecahan;
     struct link *sebelumnya;
     struct link *berikutnya;
}

Jika awal dan akhir linked list saling terhubung maka linked list tersebut disebut Circular Linked List. Pengembangan konsep linked list yang menggunakan beberapa pointer sebagai cabang disebut dengan Tree. Tree yang cabangnya saling terhubung bisa digunakan untuk membentuk struktur data yang disebut dengan Graph. Tree dan Graph yang berbentuk linked list dan punya lebih dari dua cabang bisa dibuat dengan cara menyimpan pointer penunjuk struct dalam bentuk array dinamis.

Contoh Penerapan FIFO:

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

struct link{
    int data;
    struct link *next;
};

struct infoku{
    struct link *awal=0;
    struct link *akhir=0;
}info;

link *hapus_data(infoku *info){
link *selanjutnya=0;
    if(info->awal!=0){
        selanjutnya=info->awal->next;
        free(info->awal);
        info->awal=selanjutnya;
    }

    if(selanjutnya!=0){
        info->akhir=0;
    }
    return selanjutnya;
}

link *tambah_data(infoku *info){
link *penunjuk=0;
    penunjuk=(link*)malloc(sizeof(link));
    penunjuk->next=0;
    if(info->awal==0){
        info->awal=penunjuk;
    }else info->akhir->next=penunjuk;
    info->akhir=penunjuk;
    return penunjuk;
}

int main(){
int i=0;
int n=10;
struct link *penunjuk;
    info.awal=0;
    info.akhir=0;
    printf("Masukkan jumlah data!\n");
    scanf("%d", &n);//masukkan jumlah data yang diinginkan
    //buat linked list
    while(i<n){
        penunjuk=tambah_data(&info);
        penunjuk->data=i*2;
        i++;
    }
    //tampilkan isi struct dalam linked list
    printf("\nAntrian : ");
    penunjuk=info.awal;
    while(penunjuk!=0){
        printf("%d  ", penunjuk->data);
        penunjuk=penunjuk->next;
    }
    hapus_data(&info);
    //tampilkan isi struct dalam linked list setelah data pertama dihapus
    printf("\n\nSetelah data pertama dalam antrian dihapus?\n");
    printf("Antrian : ");
    penunjuk=info.awal;
    while(penunjuk!=0){
        printf("%d  ", penunjuk->data);
        penunjuk=penunjuk->next;
    }
    printf("\n");
    //bebaskan semua memori yang sudah digunakan
    penunjuk=info.awal;
    while(penunjuk!=0){
        penunjuk=hapus_data(&info);
    }
    return 0;
}

Contoh Penerapan LIFO

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

struct link{
    int data;
    struct link *prev;
};

struct infoku{
    struct link *atas=0;
    struct link *bawah=0;
}info;

link *hapus_data(infoku *info){
link *sebelumnya=0;
    if(info->atas!=0){
        sebelumnya=info->atas->prev;
        free(info->atas);
        info->atas=sebelumnya;
    }

    if(sebelumnya!=0){
        info->bawah=0;
    }

    return sebelumnya;
}

link *tambah_data(infoku *info){
link *penunjuk=0;
    penunjuk=(link*)malloc(sizeof(link));
    if(info->bawah==0){
        penunjuk->prev=0;
        info->bawah=penunjuk;
    }else penunjuk->prev=info->atas;
    info->atas=penunjuk;
    return penunjuk;
}

int main(){
int i=0;
int n=10;
struct link *penunjuk;
    info.atas=0;
    info.bawah=0;
    printf("Masukkan jumlah data!\n");
    scanf("%d", &n);//masukkan jumlah data yang diinginkan
    //buat linked list
    while(i<n){
        penunjuk=tambah_data(&info);
        penunjuk->data=i*2;
        i++;
    }
    //tampilkan isi struct dalam linked list
    i=0;
    penunjuk=info.atas;
    while(penunjuk!=0){
        i++;
        printf("Tumpukan ke-%d : %d\n", i, penunjuk->data);
        penunjuk=penunjuk->prev;
    }

    hapus_data(&info);
    //tampilkan isi struct dalam linked list setelah data pertama dihapus
    printf("\nSetelah data pertama dalam tumpukan dihapus?\n");
    i=0;
    penunjuk=info.atas;
    while(penunjuk!=0){
        i++;
        printf("Tumpukan ke-%d : %d\n", i, penunjuk->data);
        penunjuk=penunjuk->prev;
    }

    //bebaskan semua memori yang sudah digunakan
    penunjuk=info.atas;
    while(penunjuk!=0){
        penunjuk=hapus_data(&info);
    }
    return 0;
}

Menambah dan Menghapus Data dalam Circular Doubly Linked List
Data pada linked list yang hanya punya satu pointer akan mudah dihapus awal atau akhirnya sesuai jenis linked listnya. Tapi, saat kita akan menghapus bagian tengahnya, penghapusan akan jadi lebih sulit karena data hanya terhubung ke satu arah. Jika ingin menghapus data dalam linked list dengan lebih mudah, kalian bisa menggunakan doubly linked list. Dengan doubly linked list, kita juga akan lebih mudah memajukan dan memundurkan pointer.

Kalian bisa menyingkirkan data dari rangkaian dengan mengubah data yang ditunjuk oleh data sebelumnya dan data setelahnya. Tapi, menyingkirkan data dari rangkaian tidak sama dengan menghapus data dari memori. Untuk menghapus data dari memori komputer, kalian perlu menggunakan function free.

Awal dan akhir dari linked list tidak hanya ditandai dengan NULL, kalian juga bisa menandai awal dan akhir dari doubly linked list dengan satu "struct yang menghubungkan akhir dan awal linked list". Dengan cara ini, linked list bisa jadi circular linked list sekaligus doubly linked list. Penghapusan data dalam linked list tipe ini akan lebih mudah dibandingkan dengan linked list jenis lain.

Pada contoh berikut ini, saya akan menggunakan satu "struct kosong" sebagai penghubung awal dan akhir dari linked list.

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

typedef char Namaku[100];

struct link{
    Namaku nama;
    int nilai;
    struct link *prev;
    struct link *next;
}structku, *penunjuk, *prev, *batas;

Namaku data_nama[10]={"Geri", "Sani", "Nadia", "Nando", "Tiara", "Anjas", "Puja", "Neliya", "Azka", "Hanifah"};

int hapus_data(link *dataku){
    if(dataku!=NULL && dataku!=batas){
        if(dataku->prev!=NULL)dataku->prev->next=dataku->next;
        if(dataku->next!=NULL)dataku->next->prev=dataku->prev;
        free(dataku);
    }
    return 0;
}

int main(){
int i=0;
int n=10;
    //buat linked list
    penunjuk=&structku;
    prev=&structku;
    batas=&structku;
    batas->prev=batas;
    batas->next=batas;

    while(i<n){
        penunjuk->next=(link*)malloc(sizeof(link));//alokasikan memori
        penunjuk=penunjuk->next;//pindahkan pointer
        //atur isi data
        strcpy(penunjuk->nama, data_nama[i]);
        penunjuk->nilai=i*2;
        penunjuk->prev=prev;
        prev=penunjuk;
        i++;
    }
    penunjuk->next=batas;
    penunjuk->nilai=i*2;

    //tampilkan isi struct dalam linked list
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        printf("%d. %s : %d\n", i, penunjuk->nama, penunjuk->nilai);
        penunjuk=penunjuk->next;
    }

    //pilih data yang akan dihapus
    printf("Hapus data ke-...? ");
    scanf("%d", &n);

    //cari data yang akan dihapus
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        if(i>=n)break;
        penunjuk=penunjuk->next;
    }
    //hapus data
    hapus_data(penunjuk);
    //tampilkan data yang tersisa
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        printf("%d. %s : %d\n", i, penunjuk->nama, penunjuk->nilai);
        penunjuk=penunjuk->next;
    }
    //bebaskan semua memori yang sudah digunakan
    penunjuk=structku.next;
    while(penunjuk!=batas){
        prev=penunjuk;
        penunjuk=penunjuk->next;
        free(prev);
    }
    return 0;
}

Selanjutnya, kita akan mencoba untuk mengubah programnya. Kita akan menambahkan satu function untuk menambah data dalam linked list. Function tersebut bisa diletakkan dalam loop ataupun di bagian lain dari kode program.

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

typedef char Namaku[100];

struct link{
    Namaku nama;
    int nilai;
    struct link *prev;
    struct link *next;
}structku, *penunjuk, *prev, *batas;

Namaku data_nama[10]={"Geri", "Sani", "Nadia", "Nando", "Tiara", "Anjas", "Puja", "Neliya", "Azka", "Hanifah"};

int hapus_data(link *dataku){
    if(dataku!=NULL && dataku!=batas){
        if(dataku->prev!=NULL)dataku->prev->next=dataku->next;
        if(dataku->next!=NULL)dataku->next->prev=dataku->prev;
    }
    return 0;
}

link *tambah_data(link *batas, Namaku nama, int nilai){
link *dataku=NULL;
link *sebelumnya=batas->prev;
int n;
    dataku=(link*)malloc(sizeof(link));
    if(dataku!=NULL){
        dataku->next=batas;
        dataku->prev=sebelumnya;
        //hubungkan batas data dan data sebelumnya
        sebelumnya->next=dataku;
        batas->prev=dataku;
        //isi data
        strcpy(dataku->nama, nama);
        dataku->nilai=nilai;
    }
    return dataku;
}

int main(){
int i=0;
int n=10;
    //buat linked list
    penunjuk=&structku;
    prev=&structku;
    batas=&structku;
    batas->prev=batas;
    batas->next=batas;

    while(i<n){
        penunjuk=tambah_data(batas, data_nama[i], i*2);
        //atur isi data
        i++;
    }
    //tampilkan isi struct dalam linked list
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        printf("%d. %s : %d\n", i, penunjuk->nama, penunjuk->nilai);
        penunjuk=penunjuk->next;
    }

    //pilih data yang akan dihapus
    printf("Hapus data ke-...? ");
    scanf("%d", &n);

    //cari data yang akan dihapus
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        if(i>=n)break;
        penunjuk=penunjuk->next;
    }
    //hapus data
    hapus_data(penunjuk);
    //tampilkan data yang tersisa
    i=0;
    penunjuk=structku.next;
    while(penunjuk!=batas){
        i++;
        printf("%d. %s : %d\n", i, penunjuk->nama, penunjuk->nilai);
        penunjuk=penunjuk->next;
    }
    //bebaskan semua memori yang sudah digunakan
    penunjuk=structku.next;
    while(penunjuk!=batas){
        prev=penunjuk;
        penunjuk=penunjuk->next;
        free(prev);
    }
    return 0;
}