Materi dan Contoh Program Single Linked List pada C++

Modul Single Linked List C++ - Apa itu Single Linked List ? Linked List atau Single Linked List merupakan suatu bentuk struktur data yang berisi kumpulan data yang disebut sebagai node yang tersusun secara sekuensial, saling sambung menyambung, dinamis, dan terbatas.

Linked list sering juga disebut dengan sebagai sebutan senarai brantai. Cara untuk menghubungkan satu node dengan node lainnya maka Linked List menggunakan pointer sebagai penunjuk node selanjutnya atau bisa disebut next.

Node merupakan sebuah struct atau tipe data bentukkan yang menempati suatu lokasi memori secara dinamis yang terdiri dari beberapa field, minimal 2 buah field. Field tersebut adalah field untuk isi struct datanya sendiri dan 1 field arbitari bertipe pointer sebagai penunjuk node selanjutnya.

Kenapa menggunakan Linked List? Kenapa tidak menggunakan Array? Apa Perbedaan dari Array dan Linked List? Nah, mari kita bahas.

Array adalah merupakan salah satu variabel yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai oleh array tersebut tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah tersebut kita dapat menggunakan sebuah variabel pointer. Tipe data pointer adalah bersifat dinamis, variabel akan hanya dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat di relokasikan kembali. Setiap ingin menambahkan data, anda akan selalu menggunakan variabel pointer yang baru, maka akibatnya dari itu anda akan sangat banyak membutuhkan sebuah variabel pointer. Maka dari itu, ada baiknya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan menggunakan metode yang kita sebut dengan Single Linked List atau Linked List.

Perbedaan tersebut dari Array dan Linked List dapat dilihat pada tabel dibawah ini :

Array	Linked List
Statis	Dinamis
Penambahan dan penghapusan data terbatas	Penambahan dan penghapusan data tidak terbatas
Random Access	Sequential Access
Penghapusan array tidak mungkin	Penghapusan mudah

Salah satu tipe linked list yang sederhana yaitu Single Linked List. Single linked list merupakan linked list yang memiliki hanya satu pointer penunjuk dengan arah data hanya satu arah.

Langkah membuat dan operasi pada sebuah Linked List adalah sebagai berikut :

1. Mendeklarasikan struct node
2. Membuat node head
3. Menginisialiasi node head
4. Menambahkan node baru baik di depan maupun di belakang
5. Menghapus node tertentu

Pembuatan Single Linked List 

1. Mendeklarasikan dan Membuat Struct Node

Penjelasan :

- Pembuatan struct bernama TNode yang berisi 2 field, yaitu pada field pertama dengan variabel data dengna tipe data integer dan field kedua yaitu next yang bertipe pointer dari TNode.

- Setelah selesai pembuatan struct, selanjutnya buat variabel head yang bertipe pointer dari TNode yang berguna untuk sebagai kepala dari linked list.

2. Pembentukan Node Baru

Untuk pembentukan atau pembuatan node baru dapat menggunakan keyword new yang berarti untuk mempersiapkan sebuah node baru beserta alokasi memorinya, yang kemudian node tersebut akan diisi data dan kemudian pointer nextnya akan ditunjuk ke NULL.

3. Menginisialisasikan dan Menggunakan Node Head
Selanjutnya yaitu :
- Dibutuhkan satu buah variabel pointer yang telah dibuat tadi yaitu : head
- head tersebut akan selalu menunjuk pada node pertama

Deklarasi Pointer penunjuk kepala Single Linked List manipulasi Linked List tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk terlebih dahulu ke node pertama di dalam linked list (dalam hal kasus ini adalah head). Deklarasinya sebagai berikut :

TNode *head;

Function untuk mengetahui kosong atau tidaknya didalam Single Linked List jika pointer head tidak menunjuk pada suatu node maka kosong.

4. Penambahan Data

- Penambahan Data di Depan Single Linked List

Penambahan node baru akan dikaitkan di node paling depan, namun pada saat pertama kali atau data masing kosong bener, maka penambahan data dilakukan dengan cara head ditunjukkan ke node baru tersebut. Pada prinsipnya adalah untuk mengkaitkan node baru dengan pointer atau head, yang kemudian head tersebut akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.

Ilustrasi dari Penambahan Data di depan :

Penghapusan Data pada Single Linked List

Berikut yaitu adalah sebuah Function untuk menghapus suatu data di Linked List terdepan atau hapus data depan di Linked List :

Function atau Fungsi diatas akan menghapus data teratas (pertama) didepan yang ditunjuk oleh head pada linked list.

Catatan :

- Penghapusan node tidak boleh dilakukan jika atau saat keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunaan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus tersebut, misalnya contoh saja dengan membuat pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete di C++.

- Sebelum data terdepan akan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tersebut tidak terputus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru).

- Jika head tersebut masih NULL maka berarti data masih kosong.

Macam - Macam Bentuk Single Linked List

1. Single Linked List Non Circular

Single Linked List Non Circular ini merupakan linked list dimana antara kepala dan node terakhir tidak memiliki hubungan. Pada Linked List ini maka pointer terakhir selalu menunjuk NULL sebagai pertanda data terakhir dalam list-nya. Single Linked  List Non Circular (SLLNC) dapat digambarkan sebagai berikut :

Bentuk dan Contoh Program dari Single Linked List Non Circular pada C++ :

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

using namespace std;

typedef struct Data
{
    int nilai;
    Data *next;
};

Data *head;
Data *tail;

void awal ()
{
    head=NULL;
}

bool isEmpty()
{
    if (head==NULL)
        return true;
    return false;
}

void tambahDataDepan (int DataBaru)
{
    Data *baru;
    baru = new Data;
    baru -> nilai = DataBaru;
    baru -> next = NULL;
    if (isEmpty())
    {
        head = baru;
        head->next=NULL;
    }
    else
    {
        baru->next = head;
        head = baru;
    }
    cout << "Data Depan" << DataBaru << " Masuk" << endl;
}

void tambahDataBelakang (int DataBaru)
{
    Data *baru, *bantu;
    baru = new Data;
    baru->nilai=DataBaru;
    baru->next = NULL;
    if (isEmpty())
    {
        head=baru;
        head->next=NULL;
    }
    else
    {
        bantu=head;
        while(bantu->next!=NULL)
        {
            bantu=bantu->next;
        }
        bantu->next=baru;
    }
    cout << "Data Belakang " << DataBaru << " Masuk"  << endl;
}

void hapusDepan ()
{
    Data *hapus;
    int d;
    if (!isEmpty())
    {
        if(head->next !=NULL)
        {
            hapus = head;
            d = hapus->nilai;
            head = hapus->next;
            delete hapus;
        }
        else
        {
            d = head->nilai;
            head = NULL;
        }
        cout << d << " Terhapus" << endl;
    }
    else cout << "Masih Kosong" << endl;
}

void hapusBelakang ()
{
    Data *hapus, *bantu;
    int tmp;
    if (!isEmpty())
    {
        if (head->next!=NULL)
        {
            bantu = head;
            while (bantu->next->next!=NULL)
            {
                bantu = bantu->next;
            }
            hapus = bantu->next;
            tmp = hapus->nilai;
            bantu->next=NULL;
            delete hapus;
        }
        else
        {
            tmp=head->nilai;
            head=NULL;
        }
        cout <<  tmp << " Terhapus" << endl;
    }
    else cout << "Masih Kosong" << endl;
}

void Cetak ()
{
    if (!isEmpty())
    {
        Data *bantu;
        bantu=head;
        do
        {
            cout << bantu->nilai<< " ";
            bantu=bantu->next;
        }
        while (bantu!=NULL);
        cout << endl;
    }
}

int panjang ()
{
    int count=0;
    if (!isEmpty())
    {
        count=1;
        Data *bantu;
        bantu=head;
        if (bantu->next==NULL)
        {
            count=1;
        }
        else
        {
            do
            {
                count++;
                bantu=bantu->next;
            }
            while (bantu->next!=NULL);
        }
    }
    else
    {
        count=0;
    }
    return count;
}


int main()
{
    awal();
    tambahDataBelakang(5);
    tambahDataDepan(7);
    tambahDataBelakang(17);
    tambahDataBelakang(1);
    tambahDataBelakang(27);
    tambahDataBelakang(10);
    cout << "Data pada single linked list non circular:" << endl;
    Cetak();
    cout << "Data paling depan dihapus:" << endl;
    hapusDepan();
    cout << "Data pada single linked list non circular:" << endl;
    Cetak();
    cout << "Data paling belakang dihapus:" << endl;
    hapusBelakang();
    cout << "Data pada single linked list non circlar:" << endl;
    Cetak();
    cout << "Panjang linked list :" << endl;
    cout << panjang();
    getch();
    return 0;
}

Hasil Program Diatas :

2. Single Linked List Circular
Single Linked List yang kedua adalah yaitu Single Linked List Circular (SLLC). Perbedaan Circular Linked List dan Non Circular Linked List adalah next node terakhir pada Circular Linked List akan selalu merujuk ke node pertama. Ilustrasi untuk Linked List Circular dapat dilihat pada gambar dibawah ini :

Bentuk dan Contoh Program Single Linked List Circular pada C++ :

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

using namespace std;

struct Data
{
    int nilai;
    Data *next;
};

Data *head;

void awal ()
{
    head=NULL;
}

bool isEmpty()
{
    if (head==NULL)
        return true;
    return false;
}

void tambahDataDepan (int DataBaru)
{
    Data *baru;
    baru = (Data*) malloc (sizeof (Data));
    baru -> nilai = DataBaru;
    baru -> next = baru;
    if (isEmpty())
    {
        head = baru;
        head->next=head;
    }
    else
    {
        Data *bantu;
        bantu=head;
        while (bantu->next!=head)
        {
            bantu=bantu->next;
        }
        baru->next=head;
        head=baru;
        bantu->next=head;
    }
}

void tambahDataBelakang (int DataBaru)
{
    Data *baru;
    baru=(Data*) malloc(sizeof (Data));
    baru->nilai=DataBaru;
    baru->next=baru;
    if (isEmpty())
    {
        head=baru;
        head->next=head;
    }
    else
    {
        Data *bantu;
        bantu=head;
        while (bantu->next!=head)
        {
            bantu=bantu->next;
        }
        bantu->next=baru;
        baru->next=head;
    }
}

void hapusDepan ()
{
    if (!isEmpty())
    {
        int tmp;
        if (head->next!=head)
        {
            Data *hapus;
            hapus=head;
            tmp=head->nilai;
            Data *bantu;
            bantu=head;
            while (bantu->next!=head)
            {
                bantu=bantu->next;
            }
            bantu->next=head->next;
            head=head->next;
            delete hapus;
        }
        else
        {
            tmp=head->nilai;
            awal();
        }
        cout << tmp << " Dihapus" << endl;
    }
    else
    {
        cout << "Data kosong\n";
    }
}

void hapusBelakang ()
{
    Data *hapus, *bantu;
    int tmp;
    if (!isEmpty())
    {
        hapus=head;
        if (head->next==head)
        {
            tmp=head->nilai;
            head=NULL;
        }
        else
        {
        bantu=head;
        while (bantu->next->next!=head)
        {
            bantu=bantu->next;
        }
        hapus=bantu->next;
        bantu->next=head;
        tmp=hapus->nilai;
        delete hapus;
    }
    cout << tmp << " Dihapus" << endl;
    }
    else cout << "Data kosong\n ";
}

void Cetak ()
{
    if (!isEmpty())
    {
        Data *bantu;
        bantu=head;
        do
        {
            cout << bantu->nilai<< " ";
            bantu=bantu->next;
        }
        while (bantu!=head);
        cout << endl;
    }
}

int panjang ()
{
    int count=0;
    if (!isEmpty())
    {
        count=1;
        Data *bantu;
        bantu=head;
        if (bantu->next==head)
        {
            count=1;
        }
        else
        {
            do
            {
                count++;
                bantu=bantu->next;
            }
            while (bantu->next!=head);
        }
    }
    else
    {
        count=0;
    }
    return count;
}


int main()
{
    awal();
    tambahDataBelakang(5);
    tambahDataDepan(7);
    tambahDataBelakang(17);
    tambahDataBelakang(1);
    tambahDataBelakang(27);
    tambahDataBelakang(10);
    cout << "Data pada single linked list circular:" << endl;
    Cetak();
    cout << "Data paling depan dihapus:" << endl;
    hapusDepan();
    cout << "Data paling belakang dihapus:" << endl;
    hapusBelakang();
    cout << "Data pada single linked list circlar:" << endl;
    Cetak();
    cout << "Panjang linked list :" << endl;
    cout << panjang();
    getch();
    return 0;
}

Tampilan Program Diatas :

Nah itulah beberapa materi atau modul tentang Single Linked List pada C++. Jika anda masih bingung dengan materi diatas, silahkan bertanya melalui kolom komentar dibawah ini. Semoga artikel ini bermanfaat untuk anda yang ingin belajar bahasa pemrograman sederhana C++. Sekian, terimakasih.

sumber:https:https://www.forumkomputer.com/2019/04/program-linked-list.htmll