Pengertian dan Contoh dari Linked List (Beserta Program dalam C++)

Assalamu‘alaikum wr. wb.

Hello guys, Kembali lagi bersama Inzaghi's Blog! Jika sebelumnya di Algoritma kita sudah membahas tentang Searching dan Sorting. Kali ini kita akan membahas tentang Linked List. Kali ini saya akan membahasnya lebih lanjut pada Artikel ini.

Sumber Artikel/Materi : Rumahit.id, Pintarkom.com (Singly Linked List), Pintarkom.com (Doubly Linked List), dan Pintarkom.com (Circular Linked List)

Linked List adalah suatu cara untuk menyimpan data dengan struktur sehingga programmer dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data kapan saja diperlukan. Secara rinci, programmer dapat menulis suatu struct atau definisi kelas yang berisi variabel yang memegang informasi yang ada di di dalamnya, dan mempunyai suatu pointer yang menunjukan ke suatu struct sesuai dengan tipe datanya.

Struktur dinamis ini mempunyai beberapa keuntungan dibandingkan struktur array yang bersifat statis. Struktur linked list lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan Array b yang ukuranya bersifat tetap. Disamping itu, manipulasi terhadap setiap elemen seperti menyisipkan, menghapus, maupun menambah dapat dilakukan dengan lebih mudah.

Untuk lebih memahami konsep linked list perhatikan permasalahan berikut ini:

Misalkan anda diminta untuk membuat sebuah algoritma dan program untuk memasukan 2 buah daftar ke dalam suatu daftar atau senarai (linked list), dimana senarai tersebut masih kosong, sehingga setelah anda masukan 2 buah data tersebut, senarai tersebut berisi 2 buah data.

SINGLY LINKED LIST

Sumber : Pintarkom.com

Penyimpanan dan pengolahan data dari sekelompok data yang telah terorganisir dalam sebuah urutan tertentu dapat dilakukan dengan menggunakan array seperti yang telah dibahas pada bab sebelumnya. Cara lain untuk menyimpan dan mengolah sekumpulan data seperti di atas juga dapat dilakukan dengan tipe pointer.

Penggunaan pointer sangat mendukung dalam pembentukan struktur data dinamis. Salah satu struktur data dinamis adalah linked list. Berarti Linked List merupakan kumpulan komponen yang saling berkaitan satu dengan yang lain melalui pointer. Masing-masing komponen sering disebut dengan simpul atau node atau verteks. Setiap simpul pada dasarnya dibagi atas 2 (Dua) bagian. Bagian pertama disebut bagian Isi atau Informasi atau Data yaitu bagian yang berisi nilai yang disimpan oleh simpul. Bagian kedua disebut bagian Pointer, yaitu berisi alamat dari simpul berikutnya dan atau sebelumnya.

Linked List dapat disajikan dengan 2 Bagian besar yaitu Singly List dan Doubly List. Baik Singly List maupun Doubly List dapat juga disajikan secara melingkar (circular).

A. Definisi Singly Linked List

Single Linked List merupakan Linked List yang paling sederhana. Setiap simpul dibagi menjadi dua bagian yaitu bagian Isi dan bagian Pointer. Bagian Isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian Pointer merupakan bagian yang berisi alamat dari simpul berikutnya. Sebagai ilustrasi, setiap simpul dari Singly List dapat dilihat pada gambar dibawah ini.

Gambar diatas terlihat bahwa simpul pertama dihubungkan ke simpul kedua melalui bagian Pointer simpul pertama. Bagian Pointer simpul kedua dihubungkan ke simpul ketiga. Demikian seterusnya hingga simpul terakhir. Bagian Pointer simpul terakhir tidak dihubungkan ke simpul lain yang disebut sebagai NULL.

B. Deklarasi Single Linked List

Dari Gambar di atas kita lihat bahwa masing-masing simpul terbagi atas dua bagian, yaitu bagian Isi dan bagian Pointer, maka dengan demikian dapat dibuat dalam struct yang terdiri dari 2 Field, seperti berikut ini.

typedef struct
struct node
{

   type_data Isi;
   simpul->next;
}

Atau seperti ini :

typedef struct
struct node
{

   type_data Isi;
   node->next;
}

C. Operasi pada Singly Linked List

Ada sejumlah operasi yang dapat dilakukan pada sebuah Singly Linked List, seperti menambah simpul, menghapus simpul, membaca isi Linked List, atau pencarian informasi pada suatu Linked List. Dalam buku ini Linked List ditunjuk oleh Pointer L.

1. Menambah Simpul

Operasi yang digunakan untuk menyisipkan simpul di posisi tertentu. Penyisipan simpul dapat dilakukan di posisi depan, penyisipan simpul di belakang, penyisipan simpul di antara dua simpul (simpul tengah).

a. Menambah Simpul Depan

Operasi ini akan menyisipkan simpul baru selalu berada pada posisi pertama atau depan dari Linked list. Langkah-langkah penyisipan simpul depan dapat dilakukan dengan :

• Ciptakan simpul Baru yang akan disisipkan.
• Jika Linked List belum ada maka simpul Baru menjadi Linked List (L = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan cara:
• Pointer Next simpul Baru menunjuk L (Baru->Next = L).
• Pointer L dipindahkan ke Baru (L = Baru).

Skema penyisipan simpul Depan dapat dilihat pada Gambar-gamar berikut ini.

Fungsi yang digunakan untuk menyisipkan simpul Depan dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Sisip_Depan(simpul &L, char elemen){
     simpul baru;
     baru = (simpul) malloc(sizeof(simpul));
     baru->Isi = elemen;
     baru->Next = NULL;
     if(L == NULL)
           L=baru;
     else{
           baru->Next;
           L=baru;
     }
}

b. Menambah Simpul Belakang

Operasi ini akan menyisipkan simpul Baru selalu berada pada posisi terakhir atau belakang dari Linked List. Langkah-langkah penyisipan simpul Belakang dapat dilakukan dengan :

• Ciptakan simpul Baru yang akan disisipkan.
• Jika Linked List belum ada maka simpul baru menjadi Linked List (L = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan cara:
• Buat suatu Pointer yang dapat digerakkan, misalkan Pointer Bantu yang menunjuk simpul pertama dari Linked List (Bantu = L). Hal ini dilakukan karena Pointer L tidak boleh digerakkan dari simpul Depan. Karena jika Pointer L digerakkan maka informasi dari simpul yang ditinggalkan oleh Pointer L tidak dapat lagi diakses.
• Gerakkan Pointer Bantu hingga ke simpul paling Belakang dari Linked List (while(Bantu->Next != NULL) Bantu=Bantu->Next;).
• Sambungkan Linked List dengan simpul Baru (Bantu->Next = Baru).

Skema penyisipan simpul Belakang dapat dilihat pada Gambar diatas. (Linked List belum ada) dan Gambar dibawah ini.

Fungsi yang digunakan untuk menyisipkan simpul Belakang dengan mengikuti langkah-langkah dan Gambar atas adalah seperti berikut ini.

c. Menambah Simpul Tengah

Operasi ini akan menyisipkan simpul Baru selalu berada di antara dua simpul dari Linked List. Simpul dapat diletakkan sebelum simpul tertentu atau setelah simpul tertentu. Penyisipan simpul Tengah hanya dapat dilakukan jika Linked List tidak kosong.

    1.) Menambah Simpul Sebelum Simpul Tertentu

Maksudnya adalah operasi penyisipan simpul sebelum simpul tertentu. Sebelum kita menyisipkan simpul maka terlebih dahulu kita ketahui simpul yang dimaksud, yaitu simpul yang berisi informasi di mana simpul akan disisipkan. Misalkan kita mempunyai Linked List dengan 4 simpul yang masing-masing berisi informasi C, B, A, dan D, kemudian kita mempunyai simpul Baru yang berisi informasi E. Simpul Baru akan disisipkan sebelum simpul yang berisi informasi A. Adapun langkah-langkah yang dapat dilakukan adalah sebagai berikut :

• Ciptakan simpul Baru yang akan disisipkan.
• Buat suatu Pointer yang dapat digerakkan, misalnya Pointer Bantu yang menunjuk simpul pertama dari Linked List (Bantu = L). Hal ini dilakukan karena Pointer L tidak boleh digerakkan dari simpul Depan. Karena jika Pointer L digerakkan maka informasi dari simpul yang ditinggalkan oleh pointer L tidak dapat lagi diakses.
• Gerakkan Pointer Bantu hingga satu simpul sebelum simpul yang berisi Informasi A. (while(Bantu->Next->Isi != ‘A’) Bantu=Bantu->Next;).
• Sambung simpul Baru dengan simpul berikutnya (Baru->Next = Bantu->Next).
• Sambungkan simpul Bantu dengan simpul Baru (Bantu->Next = Baru).

Skema penyisipan simpul sebelum simpul tertentu dapat dilihat pada Gambar berikut ini.

Fungsi untuk menyisipkan simpul sebelum simpul tertentu dengan mengikuti langkah-langkah dan gambar 7.5. di atas dapat dilihat berikut ini.

void Sisip_Sebelum(simpul &L, char elemen1, char elemen2){
     simpul bantu, baru;
     baru = (simpul) malloc(sizeof(simpul));
     baru->Isi = elemen1;
     baru->Next = NULL;
     if(L == NULL)
           cout<<"List Kosong";
     else{
           bantu = L;
           while (bantu->Next->Isi != elemen2)
                bantu=bantu->Next
           baru->Next = bantu->Next;
           bantu->Next = baru;
     }
}

    2.) Menambah Simpul Setelah Simpul Tertentu

Maksudnya adalah operasi penyisipan simpul setelah simpul tertentu. Sebelum kita menyisipkan simpul maka terlebih dahulu kita ketahui simpul yang dimaksud yaitu simpul yang berisi informasi di mana simpul akan disisipkan. Misalkan kita mempunyai Linked list dengan 4 simpul yang masing-masing berisi informasi C, B, A, dan D, kemudian kita mempunyai simpul baru yang berisi informasi E. Simpul baru akan disisipkan setelah simpul yang berisi informasi A. Adapun langkah-langkah yang dapat dilakukan adalah sebagai berikut :

• Ciptakan simpul baru yang akan disisipkan.
• Buat suatu pointer yang dapat digerakkan, misalnya pointer bantu yang menunjuk simpul pertama dari Linked List (Bantu = L). Hal ini dilakukan karena pointer L tidak boleh digerakkan dari simpul depan. Karena jika pointer L digerakkan maka informasi dari simpul yang ditinggalkan oleh pointer L tidak dapat lagi diakses.
• Gerakkan pointer bantu hingga simpul yang berisi informasi A. (while(Bantu->Isi != ‘A’) Bantu=Bantu->Next;).
• Sambung simpul baru dengan simpul setelah simpul yang ditunjuk oleh Bantu (Baru->Next = Bantu->Next)
• Sambungkan simpul bantu dengan simpul baru (Bantu->Next = Baru).

Skema penyisipan simpul sebelum simpul tertentu dapat dilihat pada Gambar berikut ini.

Fungsi untuk menyisipkan simpul setelah simpul tertentu dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Sisip_Tengah1(simpul &L, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->Next = NULL;
    if(L == NULL)
        cout<<"List Kosong .........."<<endl;
    else{
        bantu = L;
        while(bantu->Isi != elemen2)
        bantu=bantu->Next;
        baru->Next = bantu->Next;
        bantu->Next = baru;
  }
}

2. Menghapus Simpul

Maksudnya adalah operasi menghapus suatu simpul dari suatu Linked List. Dalam melakukan penghapusan simpul, ada yang perlu diperhatikan, bahwa Linked List tidak boleh kosong dan Linked List tidak boleh terputus. Sama halnya dengan penyisipan, penghapusan simpul juga dapat dilakukan terhadap simpul depan, simpul belakang, dan simpul tengah.

a. Menghapus Simpul Depan

Selalu menghapus simpul dengan dari Linked List. Linked List tidak boleh kosong. Langkah-langkah penghapusan simpul dengan dapat dilakukan dengan cara sebagai berikut :

• Buat suatu pointer misalnya pointer hapus untuk menunjuk simpul yang akan dihapus dan L untuk menunjuk Linked List.
• Simpul pertama ditunjuk oleh pointer hapus (Hapus = L).
• Pointer L digerakkan satu simpul berikutnya (L = L->Next).
• Putuskan simpul pertama dari L (Hapus->Next = NULL).

Skema penghapusan simpul depan dapat dilihat pada Gambar berikut ini.

Fungsi penghapusan simpul depan dengan mengikuti langkah-langkah dan gambar 7.7. di atas dapat dilihat berikut ini.

void Hapus_Depan(simpul &L){
  simpul Hapus;
  if(L == NULL)
    cout<<"Linked List Kosong .....";
  else{
    Hapus = L;
    L = L->N;
    Hapus->Next = NULL;
    free(Hapus);
  }
}

b. Menghapus Simpul Belakang

Selalu menghapus simpul terakhir atau belakang dari Linked List. Linked List tidak boleh kosong. Perlu diingat bahwa pointer L tidak boleh digerakkan, maka buat suatu pointer misalnya pointer bantu yang dapat digerakkan dalam Linked List. Dengan menggunakan pointer bantu maka memungkinkan tidak adanya simpul yang hilang atau terputus. Di samping itu juga buatlah pointer hapus yang digunakan untuk menunjuk simpul yang akan dihapus. Langkah-langkah penghapusan simpul belakang dapat dilakukan sebagai berikut :

• Letakkan pointer bantu pada simpul pertama (Bantu = L).
• Gerakkan pointer bantu hingga pada satu simpul sebelum siimpul terakhir (while(Bantu->Next->Next != NULL) Bantu=Bantu->Next;).
• Simpul terakhir ditunjuk oleh pointer hapus (Hapus = Bantu->Next).
• Putuskan simpul terakhir dari L (Bantu->Next = NULL).

Skema penghapusan simpul belakang dapat dilihat pada Gambar di bawah ini.

Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan gambar 7.8. di atas dapat dilihat berikut ini.

void Hapus_Belakang(simpul &L){
  simpul bantu, hapus;
  if(L==NULL)
    cout<<"Linked List Kosong .....";
  else{
    bantu = L;
    while(bantu->Next->Next != NULL)
      bantu=bantu->Next;
    hapus = bantu->Next;
    bantu->Next = NULL;
    free(hapus);
  }
}

c. Menghapus Simpul Tengah

Menghapus simpul tertentu yang ada di posisi tengah dari Linked List. Linked List tidak boleh kosong. Perlu diingat bahwa pointer L tidak boleh digerakkan, maka buat suatu pointer misalnya pointer bantu yang dapat digerakkan dalam Linked List. Dengan menggunakan pointer bantu maka memungkinkan tidak adanya simpul yang hilang atau terputus. Di samping itu juga buatlah pointer hapus yang digunakan untuk menunjuk simpul yang akan dihapus. Langkah-langkah penghapusan simpul belakang dapat dilakukan sebgai berikut :

• Letakkan pointer bantu pada simpul pertama (Bantu=L).
• Gerakkan pointer bantu hingga satu simpul sebelum simpul yang akan dihapus (while(Bantu->Next->Isi != “info”) Bantu=Bantu->Next;)
• Letakkan pointer hapus pada simpul yang akan dihapus (Hapus = Bantu->Next).
• Pointer bantu menunjuk simpul setelah simpul yang ditunjuk oleh hapus (Bantu->Next=Hapus->Next atau Bantu->Next = Bantu->Next->Next).
• Putuskan simpul yang ditunjuk hapus dari Linked List (Hapus->Next = NULL).

Skema penghapusan simpul belakang dapat dilihat pada Gambar di bawah ini.

Fungsi untuk menghapus simpul tertentu di tengah dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Hapus_Tengah(simpul &L, char elemen){
  simpul bantu, hapus;
  if(L==NULL)
    cout<<"Linked List Kosong ......";
  else{
    bantu = L;
    while(bantu->Next->Isi != elemen)
      bantu=bantu->Next;
    hapus = bantu->Next;
    bantu->Next = bantu->Next->Next;
    hapus->Next = NULL;
    free(hapus);
  }
}

3. Mencetak Isi Simpul

Nilai masing-masing simpul dapat dicetak mulai dari isi simpul pertama atau simpul depan hingga simpul belakang dengan fungsi berikut ini.

void Cetak(simpul L){
  simpul bantu;
  if(L==NULL)
    cout<<"Linked List Kosong ......"<<endl;
  else{
    bantu=L;
    cout<<"Isi Linked List : ";
    while (bantu->Next != NULL){
      cout<<bantu->Isi<<"-->";
      bantu=bantu->Next;
    }
    cout<<bantu->Isi;
  }
}

D. Program C++ Singly Linked List

Berikut ini merupakan program lengkap untuk operasi Singly Linked List.

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;
typedef struct node *simpul;
struct node {
    char Isi;
    simpul Next;
};
//======================
//==Prototype Function==
//======================
void Sisip_Depan(simpul &L, char elemen);
void Sisip_Belakang(simpul &L, char elemen);
void Sisip_Tengah1(simpul &L, char elemen1, char elemen2);
void Sisip_Tengah2(simpul &L, char elemen1, char elemen2);
void Hapus_Depan(simpul &L);
void Hapus_Belakang(simpul &L);
void Hapus_Tengah(simpul &L, char elemen);
void Cetak(simpul L);
//=================
//==Function Main==
//=================
int main(){
    char huruf, huruf2;
    simpul L = NULL;  //Pastikan bahwa L kosong
    cout<<"==OPERASI PADA SINGLE LINKED LIST=="<<endl<<endl;
    //===============
    //==Sisip Depan==
    //===============
    cout<<"Penyisipan Simpul Di Depan"<<endl<<endl;
    cout<<"Masukkan Huruf : "; cin>>huruf;
    Sisip_Depan(L, huruf);
    cout<<"Masukkan Huruf : "; cin>>huruf;
    Sisip_Depan(L, huruf);
    cout<<"Masukkan Huruf : "; cin>>huruf;
    Sisip_Depan(L, huruf);
    cout<<"Masukkan Huruf : "; cin>>huruf;
    Sisip_Depan(L, huruf);
    Cetak(L);
    //======================
    //====Sisip Belakang====
    //======================
    //==Hapus Simpul Depan==
    //======================
    cout<<endl<<endl<<"Setelah Hapus Simpul Depan "<<endl;
    Hapus_Depan(L);
    Cetak(L);
    //=========================
    //==Hapus Simpul Belakang==
    //=========================
    cout<<endl<<endl<<"Setelah Hapus Simpul Belakang "<<endl;
    Hapus_Belakang(L);
    Cetak(L);
    //=======================
    //==Hapus Simpul TENGAH==
    //=======================
    cout<<"\n\nMasukkan Huruf Tengah Yang Akan Dihapus : ";
    cin>>huruf;
    Hapus_Tengah(L,huruf);
    Cetak(L);
    getch();
}
//**********************************
//**FUNCTION SISIP SIMPUL DI DEPAN**
//**********************************
void Sisip_Depan(simpul &L, char elemen){
    simpul baru;  // = new simpul;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->Next = NULL;
    if(L == NULL)
        L=baru;
    else{
        baru->Next = L;
        L=baru;
    }
}
//*************************************************
//**FUNCTION SISIP SIMPUL SETELAH SIMPUL TERTENTU**
//*************************************************
void Sisip_Tengah1(simpul &L, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->Next = NULL;
    if(L == NULL)
        cout<<"List Kosong............"<<endl;
    else{
        bantu = L;
        while(bantu->Isi != elemen2) bantu=bantu->Next;
        baru->Next = bantu->Next;
        bantu->Next = baru;
    }
}
//*************************************************
//**FUNCTION SISIP SIMPUL SEBELUM SIMPUL TERTENTU**
//*************************************************
void Sisip_Tengah2(simpul &L, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->Next = NULL;
    if(L == NULL)
        cout<<"List Kosong .........."<<endl;
    else{
        bantu = L;
        while(bantu->Next->Isi != elemen2) bantu-bantu->Next;
        baru->Next = bantu->Next;
        bantu->Next = baru;
    }
}
//*************************************
//**FUNCTION SISIP SIMPUL DI BELAKANG**
//*************************************
void Sisip_Belakang(simpul &L, char elemen){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->Next = NULL;
    if(L == NULL)
        L=baru;
    else{
        bantu=L;
        while(bantu->Next != NULL)
        bantu=bantu->Next;
        bantu->Next=baru;
    }
}
//*************************************
//**FUNCTION MENCETAK ISI LINKED LIST**
//*************************************
void Cetak(simpul L){
    simpul bantu;
    if(L=NULL)
        cout<<"Linked List Kosong ......"<<endl;
    else{
        bantu=L;
        cout<<"Isi Linked List : ";
        while (bantu->Next != NULL){
        cout<<bantu->Isi<<"-->";
        bantu=bantu->Next;
        }
        cout<<bantu->Isi;
    }
}
//*******************************
//**FUNCTION HAPUS SIMPUL DEPAN**
//*******************************
void Hapus_Depan(simpul &L){
    simpul Hapus;
    if(L==NULL)
        cout<<"Linked List Kosong ...........";
    else{
        Hapus = L;
        L = L->Next;
        Hapus->Next = NULL;
        free(Hapus);
    }
}
//**********************************
//**FUNCTION HAPUS SIMPUL BELAKANG**
//**********************************
void Hapus_Belakang(simpul &L){
    simpul bantu, hapus;
    if(L==NULL)
        cout<<"Linked List Kosong ............";
    else{
        bantu = L;
        while(bantu->Next->Next != NULL) bantu=bantu->Next;
        hapus = bantu->Next;
        bantu->Next = NULL;
        free(hapus);
    }
}
//***********************************
//**FUNCTION HAPUS SIMPUL DI TENGAH**
//***********************************
void Hapus_Tengah(simpul &L, char elemen){
    simpul bantu, hapus;
    if(L==NULL)
        cout<<"Linked List Kosong ............";
    else{
        bantu = L;
        while(bantu->Next->Isi != elemen) bantu=bantu->Next;
        hapus = bantu->Next;
        bantu->Next = bantu->Next->Next;
        hapus->Next = NULL;
        free(hapus);
    }
}

DOUBLY LINKED LIST

Sumber : Pintarkom.com

Salah satu kelemahan dari Singly Linked List adalah masing-masing simpul hanya memiliki satu pointer saja sehingga hanya dapat bergerak satu arah saja, yaitu: maju atau ke kanan. Untuk mengatasi kelemahan ini maka dibuat dengan Doubly Linked List.

Doubly Linked List merupakan Linked List dimana setiap simpul dibagi menjadi tiga bagian yaitu bagian isi, bagian pointer kiri, dan bagian pointer kanan. Bagian isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian pointer kiri merupakan bagian yang berisi alamat dari simpul sebelumnya dan bagian pointer kanan merupakan bagian yang berisi alamat dari simpul berikutnya.

Dari gambar di atas dapat kita lihat bahwa pointer kanan suatu simpul menunjuk ke simpul berikutnya dan pointere kiri menunjuk simpul sebelumnya. Tetapi untuk pointer kiri simpul pertama tidak menunjuk ke simpul yang lain (NULL) dan pointer kanan dari simpul terakhir juga tidak menunjuk simpul yang lain (NULL).

1. Deklarasi Doubly Linked List

Berikut, inilah Kode Deklarasi untuk Doubly Linked List :

typedef struct node *simpul;
struct node
     {
           char Isi;
           simpul kanan;
           simpul kiri;
     };

Atau seperti ini :

typedef struct node *node;
struct node
     {
           char Isi;
           node kanan;
           node kiri;
     };

2. Operasi Pada Doubly Linked List

Semua operasi pada Singly Linked List juga terdapat pada operasi Doubly Linked List, yaitu Penyisipan, Penghapusan, dan Pencetakan.

1. Penyisipan Simpul

Penyisipa simpul adalah operasi penyisipan suatu simpul baru ke dalam suatu Doubly Linked List. Penyisipan dapat dilakukan di posisi depan, tengah, dan belakang.

a. Penyisipan Simpul Depan

Penyisipan simpul baru selalu berada di posisi paling depan. Penyisipan simpul depan dapat dilakukan dengan langkah berikut :

• Ciptakan simpul baru.
• Jika Linked List (DL) belum ada maka simpul baru menjadi Linked List (DL=Baru).
• Tetapi jika Linked List (DL) sudah ada maka penyisipan dilakukan dengan:
• Pointer kanan dari baru menunjuk DL (Baru->Kanan = DL).
• Pointer kiri dari DL menunjuk baru (DL->Kiri = Baru).
• Pointer DL dipindahkan menunjuk simpul baru (DL = Baru).

Fungsi penyisipan simpul depan dengan mengikuti langkah-langkah dan gambar 3 di atas dapat dilihat berikut ini.

void Sisip_Depan(simpul &DL, char elemen){
    simpul baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        DL=baru;
    else{
        baru->kanan = DL;
        DL->kiri = baru;
        DL=baru;
    }
}

b. Penyisipan Simpul Belakang

Penyisipan simpul baru selalu berada di posisi paling belakang. Penyisipan simpul belakang dapat dilakukan dengan dua cara, yaitu dengan menggunakan pointer bantu dan tanpa pointer bantu. Penyisipan simpul pada Doubly Linked List tidak mengharuskan menggunakan pointer bantu karena walaupun menggerakkan DL tidak mengakibatkan adanya simpul yang hilang. Hal ini dapat terjadi karena semua simpul saling menunjuk atau saling berhubungan.

    1.) Penyisipan dengan Pointer bantu

• Ciptakan simpul baru.
• Jika Linked List (DL) belum ada maka simpul baru menjadi Linked List (DL=Baru).
• Tetapi jika Linked Lis (DL) sudah ada maka penyisipan dilakukan dengan:
• Buat pointer bantu yang dapat digerakkan (Bantu=DL).
• Gerakkan pointer bantu hingga simpul terakhir (while(Bantu->Kanan != NULL) Bantu=Bantu->Kanan).
• Pointer kanan simpul bantu menunjuk baru (Bantu->Kanan = Baru).
• Pointer kiri baru menunjuk bantu (Baru->Kiri = Bantu).

Penyisipan simpul belakang dengan DL kosong sama seperti penyisipan simpul depan dengan DL kosong (Gambar diatas), tetapi operasi penyisipan simpul belakang untuk kasus DL tidak kosong dapat dilihat pada Gambar di bawah ini.

Fungsi penyisipan simpul belakang dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Sisip_Belakang(simpul &DL, char elemen){
    simpul baru, Bantu;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        DL=baru;
    else{
        Bantu = DL;
        while (Bantu->kanan!=NULL) Bantu=Bantu->kanan
        Bantu->kanan = baru;
        baru->kiri = Bantu;
    }
}

    2.) Penyisipan dengan Pointer bantu

• Ciptakan simpul baru.
• Jika Linked List (DL) belum ada maka simpul baru menjadi Linked List (DL=Baru).
• Tetapi jika Linked List (DL) sudah ada maka penyisipan dilakukan dengan:
• Gerakkan Pointer DL hingga simpul terakhir (while(DL->Kanan != NULL) DL=DL->Kanan).
• Pointer kanan DL menunjuk baru (DL->Kanan = Baru).
• Pointer kiri b aru menunjuk DL(Baru->Kiri = DL).
• Gerakkan Pointer DL hingga simpul pertama (while(DL->Kiri != NULL) DL=DL->Kiri).

Fungsi penyisipan simpul belakang dengan mengikuti langkah-langkah dan gambar 5 di atas dapat dilihat berikut ini.

void Sisip_Belakang(simpul &DL, char elemen){
    simpul baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        DL=baru;
    else{
        while (DL->kanan!=NULL) DL=DL->kanan;
        DL->kanan = baru;
        baru->kiri = DL;
        while (DL->kiri!=NULL) DL=DL->kiri;
    }
}

c. Penyisipan Simpul Tengah

Menyisipkan suatu simpul Baru diantara dua simpul. Penyisipan simpul tengah hanya dapat dilakukan jika linked list (DL) tidak kosong. Misalkan kita mempunyai dobly linked list (DL) dengan 3 simpul yang masing-masing berisi informasi C, B dan A serta simpul Baru yang akan disisipkan ditengah yang berisi informasi D (karakter). Simpul Baru akan disisipkan setelah simpul yang berisi informasi B (elemen).

    1.) Penyisipan Simpul Tengah dengan Pointer Bantu

• Ciptakan simpul baru.
• Buat pointer bantu yang dapat digerakkan (Bantu=DL).
• Gerakkan pointer bantu hingga simpl yang berisi informasi karakter.
• Kanan simpul baru menunjuk kanan bantu (Baru->Kanan = Bantu->Kanan).
• Pointer kiri dari kanan bantu menunjuk baru (Bantu->Kanan->Kiri = Baru).
• Pointer kanan bantu menunjuk baru (bantu->Kanan = Baru).
• Pointer kiri baru menunjuk bantu (Baru->Kiri = Bantu).

Fungsi penyisipan simpul tengah dengan mengikuti langkah-langkah dan gambar 6 di atas dapat dilihat berikut ini.

void Sisip_Tengah(simpul &DL, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        cout<<"List Kosong ............"<<endl;
    else{
        bantu = DL;
        while(bantu->kanan->Isi != elemen2)
        bantu=bantu->kanan;
        baru->kanan = bantu->kanan;
        baru->kiri = bantu;
        bantu->kanan->kiri = baru;
        bantu->kanan = baru;
    }
}

    2.) Penyisipan Simpul Tengah tanpa Pointer Bantu

• Ciptakan simpul baru.
• Gerakkan pointer DL hingga simpul yang berisi informasi karakter.
• Kanan simpul baru menunjuk kanan DL (Baru->Kanan = DL->Kanan).
• Pointer kiri dari kanan DL menunjuk baru (DL->Kanan->Kiri = Baru).
• Pointer kiri baru menunjuk DL (Baru->Kiri = DL).
• Gerakkan pointer DL hingga simpul pertama.

Fungsi penyisipan simpul tengah dengan mengikuti langkah-langkah dan gambar 7 di atas dapat dilihat berikut ini.

void Sisip_Tengah2(simpul &DL, char elemen1, char elemen2){
    simpul baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        cout<<"List Kosong ..........."<<endl;
    else{
        while(DL->kanan->Isi != elemen2) DL = DL->kanan;
        baru->kanan = DL->kanan;
        baru->kiri = DL;
        DL->kanan->kiri = baru;
        DL->kanan = baru;
    }
    while(DL->kiri != NULL) DL = DL->kiri;
}

2. Penghapusan Simpul

Operasi menghapus suatu simpul dari suatu Linked List pada Doubly Linked List hampir sama dengan penghapusan simpul pada Singly Linked List, yaitu Linked List (DL) tidak boleh dalam keadaan kosong. Penghapusan simpul juga dapat dilakukan terhadap Simpul Depan, Simpul Belakang, dan Simpul Tengah.

a. Penghapusan Simpul Depan

Simpul yang dihapus selalu yang berada pada posisi depan. Misalkan kita memiliki Linked List DL, akan dilakukan penghapusan simpul depan yaitu simpul yang berisi informasi C. Langkah-langkah penghapusan simpul depan adalah sebagai berikut :

• Simpul depan ditunjuk oleh pointer hapus (Hapus = DL).
• Pointer DL digerakkan satu simpul ke kanan (DL = DL->Kanan).
• Putuskan pointer Kiri DL dari hapus (DL->Kiri = NULL).
• Putuskan pointer kanan hapus dari Linked List DL (Hapus->Kanan=NULL).

Fungsi penghapusan simpul depan dengan mengikuti langkah-langkah dan gambar 8 di atas dapat dilihat berikut ini.

void Hapus_Depan(simpul &DL){
    simpul Hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ...............";
    else{
        Hapus = DL;
        DL = DL->kanan;
        DL->kiri = NULL;
        Hapus->kanan = NULL;
        free(Hapus);
    }
}

b. Penghapusan Simpul Belakang

Simpul yang dihapus selalu yang berada pada posisi belakang. Misalkan kita memiliki Linked List DL terdiri dari 4 simpul dengan masing-masing berisi informasi C, B, D, dan A, akan dilakukan penghapusan simpul belakang yaitu simpul yang berisi informasi A. Dalam menghapus simpul belakang, kita dapat lakukan dengan dua cara, yaitu dengan menggunakan pointer atau tanpa menggunakan pointer bantu. Langkah-langkah penghapusan simpul belakang dengan dan tanpa bantu dapat dilakukan seperti berikut.

    1.) Penghapusan Simpul Belakang dengan Pointer Bantu

• Buatlah pointer bantu yang menunjuk simpul pertama yang ditunjuk oleh pointer DL (Bantu = DL).
• Gerakkan pointer bantu hingga satu simpul sebelum simpul belakang (while(Bantu->Kanan->Kanan != NULL) Bantu = Bantu->Kanan).
• Simpul belakang yang ditunjuk pointer kanan bantuk ditunjuk juga oleh pointer hapus(Hapus = Bantu->Kanan).
• Putuskan pointer kanan bantu dari simpul yang ditunjuk pointer hapus (Bantu->Kanan=NULL).
• Putuskan pointer kiri hapus dari Linked List (Hapus->Kiri = NULL).

Skema penghapusan simpul belakang dapat dilihat pada Gambar dibawah ini.

Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan gambar 9 di atas dapat dilihat berikut ini.

void Hapus_Belakang(simpul &DL){
    simpul bantu, hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ..............";
    else{
        bantu = DL;
        while(bantu->kanan->kanan != NULL)
        bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
    }
}

    2.) Penghapusan Simpul Belakang Tanpa Pointer Bantu (Versi 1)

Menghapus simpul belakang tanpa pointer bantu, dengan demikian kita cukup menggerakkan pointer DL hingga ke satu simpul sebelum simpul belakang. Setelah selesai menghapus simpul belakang kemudian pointer DL dipindahkan kembali hingga ke simpul depan.

• Gerakkan pointer DL hingga simpul sebelum simpul belakang (while(DL->Kanan->Kanan != NULL) DL = DL->Kanan).
• Simpul terakhir yang ditunjuk oleh pointer kanan DL ditunjuk juga oleh hapus (Hapus = DL->Kanan).
• Putuskan pointer kanan DL dari simpul yang ditunjuk hapus (DL->Kanan=NULL).
• Putuskan pointer kiri hapus dari simpul yang ditunjuk DL (Hapus->Kiri = NULL).
• Gerakkan pointer DL hingga simpul pertama (while(DL->Kiri != NULL) DL = DL->Kiri).

Skema penghapusan simpul belakang dapat dilihat pada Gambar dibawah.

Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan gambar 10 di atas dapat dilihat berikut ini.

void Hapus_Belakang(simpul &DL){
    simpul hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ...............";
    else{
        while(DL->kanan->kanan != NULL) DL=DL->kanan;
        hapus = DL->kanan;
        DL->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
        while(DL->kiri != NULL) DL=DL->kiri;
    }
}

    3.) Penghapusan Simpul Belakang Tanpa Menggunakan Pointer Bantu (Versi 2)

Menghapus simpul belakang tanpa menggunakan pointer bantu dan tanpa menggerakkan pointer DL. Dalam versi 2 ini kita menggerakkan pointer hapus mulai simpul depan hingga simpul belakang.

• Pointer hapus menunjuk simpul depan (Hapus = DL).
• Gerakkan pointer hapus hingga simpul belaakng (while(Hapus->kanan != NULL) Hapus=Hapus->Kanan;).
• Putuskan pointer kanan dari kiri hapus dari hapus (Hapus->kiri->kanan = NULL).
• Putuskan pointer kiri hapus (Hapus->kiri = NULL).

Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Hapus_Belakang(simpul &DL){
    simpul Hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ..............";
    else{
        Hapus = DL;
        while(Hapus->Kanan != NULL) Hapus=Hapus->Isi;
        Hapus->kiri->kanan = NULL;
        Hapus->kiri = NULL;
        free(Hapus);
    }
}

c. Penghapusan Simpul Tengah

Berbeda dengan penghapusan simpul depan dan penghapusan simpul belakang, simpul yang akan dihapus adalah pasti yang ada di depan atau yang ada di belaakng dan hanya ada masing-masing satu. Tetapi karena simpul tengah mungkin lebih dari satu simpul maka harus diketahui simpul yang mana yang akan dihapus. Misalkan kita memiliki Linked List DL terdiri dari 4 simpul dengan masing-masing berisi informasi C, B, D, dan A, akan dilakukan penghapusan simpul yang ada di posisi tengah (simpul yang berisi informasi B atau D) yaitu simpul yang berisi informasi D (elemen). Dalam menghapus simpul belakang, kita dapat lakukan dengan dua cara juga, yaitu dengan menggunakan pointer bantu atau tanpa menggunakan pointer bantu. Langkah-langkah penghapusan simpul belakang dengan dan tanpa bantu dapat dilakukan seperti berikut.

    1.) Penghapusan Simpul Tengah dengan Pointer Bantu

• Buatlah pointer bantu yang menunjuk simpul pertama yang ditunjuk DL (Bantu = DL).
• Gerakkan pointer bantu satu simpul sebelum yang akan dihapus yaitu simpul yang berisi informasi “elemen” (while(Bantu->Kanan->Isi != “elemen”) Bantu=Bantu->Kanan).
• Simpul yang akan dihapus yaitu simpul yang ditunjuk pointer kanan bantu ditunjuk oleh pointer hapus (Hapus = Bantu->Kanan).
• Sambungkan pointer kanan bantu terhadap simpul yang ditunjuk pointer kanan hapus (Bantu->Kanan = Hapus->Kanan atau juga Bantu->Kanan = Bantu->Kanan->Kanan).
• Sambungkan pointer kiri dari simpul setelah hapus terhadap bantu (Bantu->Kanan->Kanan->Kiri = Bantu atau Hapus->Kanan->Kiri = Bantu).
• Putuskan pointer kanan hapus dari Linked List (Hapus->Kanan = NULL).
• Putuskan pointer kiri hapus dari Linked List (Hapus->Kiri = NULL).

Skema penghapusan simpul tengah dengan pointer bantu dapat dilihat pada Gambar dibawah ini.

Fungsi penghapusan simpul tengah dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Hapus_Tengah(simpul &DL, char elemen){
    simpul bantu, hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ..............";
    else{
        bantu = DL;
        while(bantu->kanan->Isi != elemen)
        bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan->kanan->kiri = bantu;
        bantu->kanan = bantu->kanan->kanan;
        hapus->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
    }
}

    2.) Penghapusan Simpul Tengah Tanpa Pointer Bantu (Versi 1)

Menghapus simpul tertentu yang ada pada posisi tengah Linked List tanpa menggunakan pointer bantu, tetapi menggerakkan pointer DL ke satu simpul sebelum simpul yang akan dihapus. Simpul yang akan dihapus (simpul berikutnya dari DL) ditunjuk oleh pointer hapus. Setelah selesai proses penghapusan kemudian kembalikan pointer DL ke simpul depan.

• Gerakkan pointer DL satu simpul sebelum simpul yang akan dihapus yaitu simpul yang berisi informasi “ele“en” (while(DL->Kanan->Isi != “elemen”) DL=DL->Kanan).
• Simpul yang akan dihapus yaitu simpul yang ditunjuk pointer kanan DL ditunjuk oleh pointer hapus (Hapus = DL->Kanan).
• Sambungkan pointer Kanan DL terhadap simpul yang ditunjuk pointer kanan hapus (DL->Kanan = Hapus->Kanan atau juga DL->Kanan = DL->Kanan->Kanan).
• Sambungkan pointer kiri dari simpul setelah hapus terhadap DL (DL->Kanan->Kanan->Kiri = DL atau Hapus->Kanan->Kiri = DL).
• Putuskan pointer kiri hapus dari Linked List (Hapus->Kiri = NULL).
• Putuskan pointer kanan hapus dari Linked List (Hapus->Kanan = NULL).
• Gerakkan pointer DL hingga simpul pertama (while(DL->Kiri != NULL) DL=DL->Kiri).

Skema penghapusan simpul tengah tanpa pointer bantu dapat dilihat pada Gambar dibawah.

Fungsi penghapusan simpul tengah dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Hapus_Tengah(simpul &DL, char elemen){
    simpul hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ............";
    else{
        while(DL->kanan->Isi != elemen) DL=DL->kanan;
        hapus = DL->kanan;
        DL->kanan->kanan->kiri = DL;
        DL->kanan = DL->kanan->kanan;
        hapus->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
        while(DL->kiri != NULL) DL=DL->kiri;
    }
}

    3.) Penghapusan Simpul Tengah Tanpa Pointer Bantu (Versi 2)

Menghapus simpul tertentu yang ada di posisi tengah Linked List tanpa menggunakan pointer bantu dan tanpa menggerakkan pointer DL. Kita hanya cukup menggerakkan pointer hapus mulai simpul depan hingga simpul yang akan dihapus, kemudian lakukan operasi penghapusan.

• Pointer hapus menunjuk simpul depan (Hapus = DL).
• Gerakkan pointer hapus hingga simpul yang berisi informasi “elemen” yaitu simpul yang akan dihapus (while(Hapus->Isi != “elemen”) Hapus=Hapus->Kanan;).
• Pointer kanan dari simpul sebelum hapus menunjuk simpul setelah hapus (Hapus->Kiri->Kanan = Hapus->Kanan).
• Pointer kiri dari simpul setelah hapus menunjuk simpul sebelum hapus (Hapus->Kanan->Kiri = Hapus->Kiri).
• Putuskan pointer kanan hapus (Hapus->Kanan = NULL).
• Putuskan pointer kiri hapus (Hapus->Kiri = NULL).

Skema penghapusan simpul tengah tanpa pointer bantu dapat dilihat pada Gambar dibawah.

Fungsi penghapusan simpul tengah dengan mengikuti langkah-langkah dan gambar 14 di atas dapat dilihat berikut ini.

void Hapus_Tengah(simpu &DL, char elemen){
    simpul Hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ..............";
    else{
        Hapus = DL;
        while(Hapus->Isi != elemen) Hapus=Hapus->Isi;
        Hapus->kanan->kiri = Hapus->kiri;
        Hapus->kiri->kanan = Hapus->kanan;
        Hapus->kanan = NULL;
        Hapus->kiri = NULL;
        free(Hapus);
    }
}

3. Pencetakan Simpul

void Ceta(simpul DL){
    if(DL==NULL)
        cout<<"Linked List Kosong ..........."<<endl;
    else{
        cout<<"Isi Linked List : ";
        while (DL != NULL)
        {
        cout<<DL->Isi<<" ";
        DL=DL->kanan;
        }
    }
}

4. Mencetak Linked List Secara Mundur

Mencetak mundur artinya mencetak elemen Linked List mulai dari elemen simpul belakang ke depan.

void Cetak_Mundur(simpul DL){
    if(DL != NULL){
        Cetak_Mundur(DL->kanan);
        cout<<DL->Isi<<" ";
    }
}

C. Program C++ Doubly Linked List

Berikut ini merupakan program lengkap untuk operasi Doubly Linked List, yaitu menyisipkan simpul depan, simpul tengah, simpul belakang, menghapus simpul depan, menghapus simpul tengah dan menghapus simpul belakang.

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;
typedef struct node *simpul;
struct node{
    char Isi;
    simpul kanan;
    simpul kiri;
};
//======================
//==Prototype Function==
//======================
void Sisip_Depan(simpul &DL, char elemen);
void Sisip_Belakang(simpul &DL, char elemen);
void Sisip_Tengah1(simpul &DL, char elemen1, char elemen2);
void Sisip_Tengah2(simpul &DL, char elemen1, char elemen2);
void Hapus_Depan(simpul &DL);
void Hapus_Belakang(simpul &DL);
void Hapus_Tengah(simpul &DL, char elemen);
void Cetak(simpul DL);
//==================
//==Function Matin==
//==================
int main(){
    char huruf, huruf2;
    simpul DL = NULL;  //Pastikan bahwa DL kosong
    int i;
    cout<<"\t\t=OPERASI PADA DOUBLE LINKED LIST==\n\n";
    //===============
    //==Sisip Depan==
    //===============
    cout<<"Penyisipan Simpul Di Deppan"<<endl<<endl;
    for(i=1; i<=4; i++){
        cout<<"Masukkan Huruf : "; cin>>huruf;
        Sisip_Depan(DL, huruf);
    }
    Cetak(DL);
    //==================
    //==Sisip Belakang==
    //==================
    cout<<"\n\nPenyisipan Simpul Di Belakang \n\n";
    for(i=1; i<=4; i++){
        cout<<"Masukkan Huruf : "; cin>>huruf;
        Sisip_Belakang(DL, huruf);
    }
    Cetak(DL);
    //========================================
    //==Sisip Simpul Setelah Simpul Tertentu==
    //========================================
    cout<<endl<<endl<<"Masukkan Huruf : ";
    cin>>huruf;
    cout<<"Disisip Setelah Huruf : "; 
    cin>>huruf2;
    cout<<huruf<<" Disisip Setelah "<<huruf2<<endl;
    Sisip_Tengah1(DL, huruf, huruf2);
    Cetak(DL);
    //========================================
    //==Sisip Simpul Sebelum Simpul Tertentu==
    //========================================
    cout<<"\n\nMasukkan Huruf : ";
    cin>>huruf;
    cout<<"Disisip Sebelum Huruf : ";
    cin>>huruf2;
    cout<<huruf<<" Disisip Sebelum "<<huruf2<<endl;
    Sisip_Tengah2(DL, huruf, huruf2);
    Cetak(DL);
    //======================
    //==Hapus Simpul Depan==
    //======================
    cout<<"\n\nSetelah Hapus Simpul Depan \n";
    Hapus_Depan(DL);
    Cetak(DL);
    //=========================
    //==Hapus Simpul Belakang==
    //=========================
    cout<<"\n\nSetelah Hapus Simpul Belakang "<<endl;
    Hapus_Belakang(DL);
    Cetak(DL);
    //=======================
    //==Hapus Simpul Tengah==
    //=======================
    cout<<"\n\nMasukkan Huruf Tengah Yang Akan Dihapus : ";
    cin>>huruf;
    Hapus_Tengah(DL,huruf);
    Cetak(DL);
    getch();
}
//**********************************
//**FUNCTION SISIP SIMPUL DI DEPAN**
//**********************************
void Sisip_Depan(simpul &DL, char elemen){
    simpul baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        DL=baru;
    else{
        baru->kanan = DL;
        DL->kiri = baru;
        DL=baru;
    }
}
//*************************************************
//**FUNCTION SISIP SIMPUL SETELAH SIMPUL TERTENTU**
//*************************************************
void Sisip_Tengah1(simpul &DL, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        cout<<"List Kosong ................"<<endl;
    else{
        bantu = DL;
        while(bantu->Isi != elemen2) bantu=bantu->kanan;
        baru->kanan = bantu->kanan;
        baru->kiri = baru;
        baru->kiri = bantu;
        bantu->kanan->kiri = baru;
        bantu->kanan = baru;
    }
}
//*************************************************
//**FUNCTION SISIP SIMPUL SEBELUM SIMPUL TERTENTU**
//*************************************************
void Sisip_Tengah2(simpul &DL, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        cout<<"List Kosong ............."<<endl;
    else{
        bantu = DL;
        while(bantu->kanan->Isi != elemen2) bantu=bantu->kanan;
        baru->kanan = bantu->kanan;
        baru->kiri = bantu;
        bantu->kanan->kiri = baru;
        bantu->kanan = baru;
    }
}
//*************************************
//**FUNCTION SISIP SIMPUL DI BELAKANG**
//*************************************
void Sisip_Belakang(simpul &DL, char elemen){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = NULL;
    baru->kiri = NULL;
    if(DL == NULL)
        DL=baru;
    else{
        bantu=DL;
        while(bantu->kanan != NULL)
        bantu=bantu->kanan;
        bantu->kanan=baru;
        baru->kiri = bantu;
    }
}
//*************************************
//**FUNCTION MENCETAK ISI LINKED LIST**
//*************************************
void Cetak(simpul DL){
    simpul bantu;
    if(DL==NULL)
        cout<<"Linked List Kosong ........."<<endl;
    else{
        bantu=DL;
        cout<<"Isi Linked List : ";
        while (bantu->kanan != NULL){
        cout<<bantu->Isi<<"<= =>";
        bantu=bantu->kanan;
        }
        cout<<bantu->Isi;
    }
}
//*******************************
//**FUNCTION HAPUS SIMPUL DEPAN**
//*******************************
void Hapus_Depan(simpul &DL){
    simpul Hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ............";
    else{
        Hapus = DL;
        DL = DL->kanan;
        DL->kiri = NULL;
        Hapus->kanan = NULL;
        free(Hapus);
    }
}
//**********************************
//**FUNCTION HAPUS SIMPUL BELAKANG**
//**********************************
void Hapus_Belakang(simpul &DL){
    simpul bantu, hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ...............";
    else{
        bantu = DL;
        while(bantu->kanan->kanan != NULL)
        bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
    }
}
//***********************************
//**FUNCTION HAPUS SIMPUL DI TENGAH**
//***********************************
void Hapus_Tengah(simpul &DL, char elemen){
    simpul bantu, hapus;
    if(DL==NULL)
        cout<<"Linked List Kosong ................";
    else{
        bantu = DL;
        while(bantu->kanan->Isi != elemen)
        bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan->kanan->kiri=bantu;
        bantu->kanan = bantu->kanan->kanan;
        hapus->kanan = NULL;
        hapus->kiri = NULL;
        free(hapus);
    }
}

Berikut ini program pembentukan suatu Doubly Linked List yang nilainya selalu terurut secara Menaik/Ascending.

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;
typedef struct node *simpul;
struct node{
    char Isi;
    simpul kanan;
    simpul kiri;
};
//======================
//==Prototype Function==
//======================
void Sisip_Urut(simpul &DL, char elemen);
void Cetak(simpul DL);
//======================
int main(){
    char huruf;
    simpul DL = NULL;  //Pastikan bahwa DL kosong
    int i;
    cout<<"\t\t==DOUBLE LINKED LIST SELALU TERURUT==\n\n";
    //================
    //==Sisip Elemen==
    //================
    for(i=1; i<=10; i++){
        cout<<"Masukkan Huruf :";
        cin>>huruf;
        Sisip_Urut(DL, huruf);
        Cetak(DL);
    }
    Cetak(DL);
    getch();
}
//*********************************************
//**FUNCTION PENYISIPAN SIMPUL SECARA TERURUT**
//*********************************************
void Sisip_Urut(simpul &DL, char elemen){
    simpul Bantu, Baru;
    bool Ketemu;
    Baru = (simpul) malloc(sizeof(simpul));
    Baru->Isi = elemen;
    Baru->kanan = NULL;
    Baru->kiri = NULL;
    if(DL == NULL)
        DL=Baru;
    else{
        if(DL->Isi > elemen){
        Baru->kanan = DL;
        DL->kiri = Baru;
        DL=Baru;
        }
        else{
        Bantu = DL;
        Ketemu = false;
        while((Bantu->kanan != NULL) && (!Ketemu)){
            if(elemen < Bantu->kanan->Isi){
            Baru->kanan = Bantu->kanan;
            Baru->kiri = Bantu;
            Bantu->kanan->kiri = Baru;
            Bantu->kanan = Baru;
            Ketemu = true;
            }
            Bantu=Bantu->kanan;
        }
        if(!(Ketemu))
            Bantu->kanan = Baru;
        }
    }
}
//*************************************
//**FUNCTION MENCETAK ISI LINKED LIST**
//*************************************
void Cetak(simpul DL){
    if(DL==NULL)
        cout<<"Linked List Kosong ........."<<endl;
    else{
        cout<<"\nIsi Linked List : ";
        while (DL != NULL){
        cout<<DL->Isi<<" ";
        DL=DL->kanan;
        }
    }
}

CIRCULAR LINKED LIST

Sumber : Pintarkom.com

Semua Linked List baik Singly maupun Doubly selalu berisi pointer NULL yaitu pointer Next simpul terakhir dari Singly Linked List dan pointer kiri simpul pertama dan pointer kanan simpul terakhir Doubly Linked List. Dengan demikian untuk membaca isi Linked List selalu dilakukan dari simpul pertama ke kanan. Ada kalanya kita membaca isi Linked List mulai dari posisi tertentu tanpa harus mundur dan kembali ke posisi semula. Maka untuk itu kita buat dengan Linked List Melingkar (Circular Linked List).

Circular Linked List dapat dilakukan terhadap Singly Linked List maupun Doubly Linked List. Dalam Circular Linked List tidak terdapat suatu simpul yang bernilai NULL. Hal ini terjadi karena simpul terakhir dihubungkan terhadap simpul pertama untuk Singly Linked List dan simpul pertama dengan simpul terakhir saling terhubung untuk Doubly Linked List. Semua simpul berhak diperlakukan sebagai simpul depan.

A. Circular Singly Linked List

Hampir sama dengan Singly Linked List, hanya saja simpul terakhir akan dihubungkan ke simpul pertama sehingga berbentuk melingkar. Pendeklarasian dan operasi yang ada di Singly Linked List juga berlaku di Circular Singly Linked List, yang perlu dijaga adalah bahwa simpul terakhir harus selalu terhubung ke simpul pertama yang ditunjuk oleh CL seperti pada Gambar dibawah ini.

1. Penyisipan Simpul

Penyisipan simpul adalah operasi menyisipkan suatu simpul baru ke dalam suatu Linked List. Operasi penyisipan dapat dilakukan di posisi depan, posisi belakang, atau di posisi tengah.

a. Penyisipan Simpul Depan

Simpul yang disisipkan selalu berada di posisi depan dari Linked List (CL). Misalkan kita memiliki suatu Linked List CL dengan empat simpul di mana masing-masing berisi informasi A, B, C, dan D, dan kita juga memiliki suatu simpul baru yang berisi informasi E yang akan disisipkan di posisi depan dari Linked List CL. Langkah-langkah penyisipan simpul baru dapat dilakukan sebagai berikut :

• Jika Linked List CL belum ada maka simpul baru menjadi awal Linked List CL (CL = Baru).
• Jika Linked List CL sudah ada maka penyisipan dilakukan:
• Pointer bantu menunjuk CL (Bantu = CL).
• Gerakkan bantu hingga ke simpul belakang (while(Bantu->Kanan != CL) Bantu = Bantu->Kanan).
• Kanan baru menunjuk CL (Baru->Kanan = CL).
• Kanan bantu menunjuk baru (Bantu->Kanan = Baru).
• Pindahkan CL ke simpul yang ditunjuk oleh baru (CL = Baru).

Skema penyisipan simpul depan dapat dilihat pada Gambar dibawah.

Fungsi penyisipan simpul depan dengan mengikuti langkah-langkah dan gambar 2 di atas dapat dilihat berikut ini.

void Sisip_Depan(simpul &CL, char elemen){
    simpul bantu, baru;
    
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = baru;
    if(CL == NULL)
        CL=baru;
    else{
        bantu = CL;
        while(bantu->kanan != CL) bantu=bantu->kanan;
        baru->kanan = CL;
        bantu->kanan = baru;
        CL = baru;
    }
}

b. Penyisipan Simpul Belakang

Penyisipan belakang sebenarnya hampir sama dengan penyisipan depan. Yang membedakan hanyalah pemindahan CL ke simpul yang ditunjuk oleh baru untuk penyisipan belakang tidak ada. Walaupun dalam penyisipan depan juga tidak harus dilakukan pemindahan CL, karena dalam Circular semua simpul berhak menjadi depan.

Misalkan kita memiliki suatu Linked List CL dengan empat simpul dimana masing-masing berisi informasi A, B, C, dan D, dan kita juga memiliki suatu simpul baru yang berisi informasi E yang akan disisipkan di posisi belakang dari Linked List CL. Langkah-langkah penyisipan simpul baru dapat dilakukan sebagai berikut :

• Jika Linked List CL belum ada maka simpul baru menjadi awal Linked List CL (CL = Baru).
• Jika Linked List CL sudah ada maka penyisipan dilakukan.
• Pointer bantu menunjuk CL (Bantu = CL).
• Gerakkan bantu hingga ke simpul belakang (while(Bantu->Kanan != CL) Bantu = Bantu->Kanan).
• Pointer kanan bantu menunjuk baru (Bantu->Kanan = Baru).
• Pointer kanan baru menunjuk CL (Baru->Kanan = CL).

Skema penyisipan simpul belakang dapat dilihat pada Gambar dibawah.

Fungsi penyisipan simpul belakang dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Sisip_Belakang(simpul &CL, char elemen){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = baru;
    if(CL == NULL)
        CL=baru;
    else{
        bantu = CL;
        while(bantu->kanan != CL) bantu=bantu->kanan;
        baru->kanan = CL;
        bantu->kanan = baru;
    }
}

c. Penyisipan Simpul Tengah

Dalam melakukan penyisipan simpul tengah, maka Linked List harus dijamin tidak boleh kosong. Penyisipan tengah dapat dilakukan pada sebelum atau setelah simpul tertentu. Yang akan dilakukan di sini adalah hanya penyisipan simpul setelah simpul tertentu. Penyisipan tengah dapat dilakukan dengan menggunakan pointer bantu atau tanpa menggunakan pointer bantu. Jika tidak menggunakan pointer bantu maka, yang harus digerakkan adalah CL dan CL dapat dikembalikan ke simpul semula ataupun tidak dikembalikan (karena prinsip semua simpul berhak menjadi simpul depan). Yang dilakukan di sini adalah juga dengan menggunakan pointer bantu.

Misalkan kita memiliki suatu Circular Linked List yang terdiri dari 4 simpul dan masing-masing simpul berisi informasi A, B, C, dan D. Kita juga memiliki simpul baru yang berisi informasi ‘X’. Simpul baru akan disisipkan setelah simpul yang berisi informasi ‘C’. Adapun langkah-langkah penyisipan tengah tersebut adalah sebagai berikut :

• Pointer bantu menunjuk simpul depan (Bantu = CL).
• Gerakkan pointer bantu hingga simpul yang berisi informasi ‘C’ (while(Bantu->Isi !=’C’) Bantu = Bantu->Kanan).
• Pointer kanan baru menunjuk kanan bantu (Baru->Kanan = Bantu->Kanan).
• Pointer kanan bantu menunjuk baru (Bantu->Kanan = Baru).

Skema penyisipan simpul tengah dapat dilihat pada Gambar dibawah ini.

Fungsi penyisipan simpul tengah dengan mengikuti langkah-langkah dan gambar 4 di atas dapat dilihat berikut ini.

void Sisip_Tengah(simpul &CL, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = baru;
    if(CL == NULL)
        cout<<"List Kosong ............."<<endl;
    else{
        bantu = CL;
        while(bantu->Isi != elemen2) bantu=bantu->kanan;
        baru->kanan = bantu->kanan;
        bantu->kanan = baru;
    }
}

2. Penghapusan Simpul

Yang dimaksud dengan penghapusan simpul adalah operasi penghapusan simpul dari Linked List. Jika kita akan melakukan penghapusan simpul maka pastikan bahwa Linked List tidak boleh kosong. Penghapusan pada Circular Singly Linked List juga dapat dilakukan pada simpul yang berada di posisi depan, posisi tengah, maupun yang berada pada posisi belakang.

a. Penghapusan Simpul Depan

Menghapus simpul yang ada pada posisi depan. Langkah-langkah penghapusan simpul pada posisi depan adalah sebagai berikut :

• Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu (Bantu = CL).
• Gerakkan pointer bantu hingga simpul belakang (while(Bantu->Kanan != CL) Bantu = Bantu->Kanan).
• Simpul depan yang ditunjuk oleh CL juga ditunjuk oleh hapus (Hapus = CL).
• Pindahkan pointer CL ke simpul berikutnya (CL = CL->Kanan).
• Pointer kanan dari bantu menunjuk CL (Bantu->Kanan = CL).
• Pointer kanan hapus menunjuk hapus (Hapus->Kanan = Hapus).

Fungsi penghapusan simpul depan dengan mengikuti langkah-langkah dan gambar 5 di atas dapat dilihat berikut ini.

void Hapus_Depan(simpul &CL){
    simpul bantu, Hapus;
    if(CL == NULL)
        cout<<"Linked List Kosong ............";
    else{
        bantu = CL;
        while(bantu->kanan != CL) bantu=bantu->kanan;
        Hapus = CL;
        CL = CL->kanan;
        bantu->kanan = CL;
        Hapus->kanan = Hapus;
        free(Hapus);
    }
}

b. Penghapusan Simpul Belakang

Menghapus simpul yang ada pada posisi belakang. Langkah-langkah penghapusan simpul pada posisi belakang adalah sebagai berikut :

• Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu (Bantu = CL).
• Gerakkan pointer bantu hingga satu simpul sebelum simpul belakang (while(Bantu->Kanan->Kanan != CL) Bantu = Bantu->Kanan).
• Simpul belakang ditunjuk oleh pointer hapus (Hapus = Bantu->Kanan).
• Pointer kanan dari bantu menunjuk CL (Bantu->Kanan = CL).
• Pointer kanan hapus menunjuk hapus (Hapus->Kanan = Hapus).

Skema penghapusan simpul belakang dapat dilihat pada Gambar dibawah ini.

Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan Gambar di atas dapat dilihat berikut ini.

void Hapus_Belakang(simpul &CL){
    simpul hapus, bantu;
    if(CL==NULL)
        cout<<"Linked List Kosong ..............";
    else{
        bantu = CL;
        while(bantu->kanan->kanan != CL) bantu= bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = CL;
        hapus->kanan = hapus;
        free(hapus);
    }
}

c. Penghapusan Simpul Tengah

Yang dimaksud dengan penghapusan simpul tengah adalah menghapus simpul tertentu yang ada pada posisi tengah. Misalkan kita memiliki suatu Circular Singly Linked List yang terdiri dari 5 Simpul dan masing-masing simpul berisi informasi A, B, C, D, dan E. Kita akan menghapus simpul yang berada di posisi tengah, yaitu simpul yang berisi informasi D. Adapun langkah-langkah penghapusan tengah tersebut adalah sebagai berikut :

• Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu (Bantu = CL).
• Gerakan pointer bantu hingga satu simpul sebelum simpul yang akan dihapus (while(Bantu->Kanan->Isi != ‘D’) Bantu = Bantu->Kanan).
• Simpul berikutnya ditunjuk pointer hapus (Hapus = Bantu->Kanan).
• Pointer kanan dari bantu menunjuk kanan hapus (Bantu->Kanan = Hapus->Kanan).
• Pointer kanan hapus menunjuk hapus (Hapus->Kanan = Hapus).

Skema penghapusan simpul tengah dapat dilihat pada Gambar dibawah ini.

Fungsi penghapusan simpul tengah dengan mengikuti langkah-langkah dan gambar 7 di atas dapat dilihat berikut ini.

void Hapus_Tengah(simpul &CL, char elemen){
    simpul hapus, bantu;
    if(CL == NULL)
        cout<<"Linked List Kosong ...............";
    else{
        bantu = CL;
        while(bantu->kanan->Isi != elemen)bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = hapus->kanan;
        hapus->kanan = hapus;
        free(hapus);
    }
}

Berikut ini program lengkap untuk operasi pada Circular Singly Linked List yaitu operasi untuk penyisipan depan, penyisipan belakang, penyisipan tengah, penghapusan simpul depan, penghapusan simpul tengah, dan penghapusan simpul belakang, serta pencetakan elemen simpul.

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;
typedef struct node *simpul;
struct node{
  char Isi;
  simpul kanan;
};
//======================
//==Prototype Function==
//======================
void Sisip_Depan(simpul &CL, char elemen);
void Sisip_Belakang(simpul &CL, char elemen);
void Sisip_Tengah(simpul &&CL, char elemen1, char elemen2);
void Hapus_Depan(simpul &CL);
void Hapus_Belakang(simpul &CL);
void Hapus_Tengah(simpul &CL, char elemen);
void Cetak(simpul CL);
//=================
//==Function Main==
//=================
int main(){
    char huruf, huruf2;
    simpul CL = NULL;  //Pastikan bahwa DL kosong
    int i;
    cout<<"\t\t==OPERASI PADA CIRCULAR SINGLE LINKED LIST==\n\n";
    //===============
    //==Sisip Depan==
    //===============
    cout<<"Penyisipan Simpul Di Depan\n\n";
    for(i=1; i<=4; i++){
        cout<<"Masukkan Huruf :"; cin>>huruf;
        Sisip_Depan(CL, huruf);
    }
    Cetak(CL);
    //==================
    //==Sisip Belakang==
    //==================
    cout<<"\nPenyisipan Simpul Di Belakang \n\n";
    for(i=1; i<=4; i++){
        cout<<"Masukkan Huruf :"; cin>>huruf;
        Sisip_Belakang(CL, huruf);
    }
    Cetak(CL);
    //========================================
    //==Sisip Simpul Setelah Simpul Tertentu==
    //========================================
    cout<<"\nMasukkan Huruf     :"; cin>>huruf;
    cout<<"Disisip Setelah Huruf :"; cin>>huruf2;
    cout<<huruf<<" Disisip Setelah "<<huruf2<<endl;
    Sisip_Tengah(CL, huruf, huruf2);
    Cetak(CL);
    //=========================
    //==Hapus Simpul Belakang==
    //=========================
    cout<<"\nSetelah Hapus Simpul Belakang \n";
    Hapus_Belakang(CL);
    Cetak(CL);
    //=======================
    //==Hapus Simpul TENGAH==
    //=======================
    cout<<"\nMasukkan Huruf Tengah Yang Akan Dihapus :"; cin>>huruf;
    Hapus_Tengah(CL,huruf);
    Cetak(CL);
    getch;
}
//**********************************
//**FUNCTION SISIP SIMPUL DI DEPAN**
//**********************************
void Sisip_Depan(simpul &CL, char elemen){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = baru;
    if(CL == NULL)
        CL=baru;
    else{
        bantu = CL;
        while(bantu->kanan != CL) bantu=bantu->kanan;
        baru->kanan = CL;
        bantu->kanan = baru;
        CL = baru;
    }
}
//*************************************************
//**FUNCTION SISIP SIMPUL SETELAH SIMPUL TERTENTU**
//*************************************************
void Sisip_Tengah(simpul &CL, char elemen1, char elemen2){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen1;
    baru->kanan = baru;
    if(CL == NULL)
        cout<<"List Kosong .............."<<endl;
    else{
        bantu = CL;
        while(bantu->Isi != elemen2) bantu=bantu->kanan;
        baru->kanan = bantu->kanan;
        bantu->kanan = baru;
    }
}
//*************************************
//**FUNCTION SISIP SIMPUL DI BELAKANG**
//*************************************
void Sisip_Belakang(simpul &CL, char elemen){
    simpul bantu, baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = baru;
    if(CL == NULL)
        CL=baru;
    else{
        bantu = CL;
        while(bantu-> != CL) bantu=bantu->kanan;
        baru->kanan = CL;
        bantu->kanan = baru;
    }
}
//*************************************
//**FUNCTION MENCETAK ISI LINKED LIST**
//*************************************
void Cetak(simpul CL){
    simpul bantu;
    if(CL==NULL)
        cout<<"Linked List Kosong ........"<<endl;
    else{
        bantu = CL;
        cout<<"Isi Linked List : ";
        while (bantu->kanan != CL){
        cout<<bantu->Isi<<"-->";
        bantu=bantu->kanan;
        }
        cout<<bantu->Isi;
    }
}
//*******************************
//**FUNCTION HAPUS SIMPUL DEPAN**
//*******************************
void Hapus_Depan(simpul &CL){
    simpul bantu, Hapus;
    if(CL == NULL)
        cout<<"Linked List Kosong ..............";
    else{
        bantu = CL;
        while(bantu->kanan != CL) bantu=bantu->kanan;
        Hapus = CL;
        CL = CL->kanan;
        bantu->kanan = CL;
        Hapus->kanan = Hapus;
        free(Hapus);
    }
}
//**********************************
//**FUNCTION HAPUS SIMPUL BELAKANG**
//**********************************
void Hapus_Belakang(simpul &CL){
    simpul hapus, bantu;
    if(CL==NULL)
        cout<<"Linked List Kosong ...............";
    else{
        bantu = CL;
        while(bantu->kanan->kanan != CL) bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = CL;
        hapus->kanan = hapus;
        free(hapus);
    }
}
//***********************************
//**FUNCTION HAPUS SIMPUL DI TENGAH**
//***********************************
void Hapus_Tengah(simpul &CL, char elemen){
    simpul hapus, bantu;
    if(CL == NULL)
        cout<<"Linked List Kosong ..............";
    else{
        bantu = CL;
        while(bantu->kanan->Isi != elemen) bantu=bantu->kanan;
        hapus = bantu->kanan;
        bantu->kanan = hapus->kanan;
        hapus->kanan = hapus;
        free(hapus);
    }
}

B. Circular Doubly Linked List [Bonus]

Circular Doubly Linked List adalah sederetan elemen yang saling berhubungan satu dengan yang lain, dimana pointer kiri simpul pertama menunjuk simpul terakhir dan pointer kanan simpul terakhi menunjuk simpul pertama. Semua simpul berhak menjadi simpul pertama. Jika suatu simpul dibuat menjadi simpul depan maka simpul yang ada di sebelah kiri merupakan simpul belakang.

Pendeklarasian simpul untuk Circular Doubly Linked List sama dengan pendeklarasian pada Doubly Linked List. Operasi yang ada pada Doubly Linked List juga berlaku pada Circular Doubly Linked List, hanya saja pada Circular tidak mengandung NULL, perhatikan pada Gambar dibawah.

1. Operasi pada Circular Doubly Linked List

Operasi pada Circular Doubly Linked List juga dapat dilakukan penyisipan dan penghapusan simpul.

a. Operasi Penyisipan Simpul

Operasi penyisipan simpul ke suatu Linked List juga ada tiga, yaitu penyisipan simpul di depan, penyisipan simpul di belakang, dan penyisipan simpul di tengah. Karena semua simpul berhak menjadi simpul depan maka pointer penunjuk Linked List (CDL) dapat digerakkan ke seluruh simpul pada Linked List. Tetapi supaya kita tetap mempertahankan simpul yang ditunjuk CDL merupakan simpul depan maka kita dapat menggunakan suatu pointer bantu. Pointer bantu dapat digerakkan ke semua simpul pada Linked List. Di sini, simpul yang ditunjuk oleh CDL pertama sekali akan tetap dipertahankan sebagai simpul pertama atau simpul depan.

    1.) Penyisipan Simpul Depan

Langkah-langkah penyisipan simpul depan dapat dilakukan seperti berikut ini :

• Jika Linked List belum ada (NULL) maka simpul baru menjadi awal Linked List (CDL = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan:
• Pointer kanan simpul baru menunjuk CDL (Baru->Kanan = CDL).
• Pointer kiri simpul baru menunjuk yang ditunjuk pointer kiri CDL (Baru->Kiri = CDL->Kiri).
• Pointer kanan dari simpul yang ditunjuk pointer kiri CDL menunjuk simpul baru (CDL->Kiri->Kanan = Baru).
• Pointer kiri CDL menunjuk simpul baru (CDL->Kiri = Baru).
• Pointer CDL menunjuk simpul baru (CDL = Baru).

Misalkan kita memiliki Linked List yang terdiri dari tiga simpul dengan berisi masing-masing informasi A, B, dan C. Juga memiliki suatu simpul baru yang berisi informasi D. Simpul baru yang akan disisipkan di bagian depan Linked List. Skema penyisipan simpul depan dapat dilihat pada Gambar dibawah ini.

Fungsi penyisipan simpul depan dengan mengikuti langkah-langkah dan gambar 9 di atas dapat dilihat berikut ini.

void Sisip_Depan(simpul &CDL, char elemen){
    simpul baru;
    baru = (simpul) malloc(sizeof(simpul));
    baru->Isi = elemen;
    baru->kanan = baru;
    baru->kiri = baru;
    if(CDL == NULL) CDL=baru;
    else{
        baru->kanan = CDL;
        baru->kiri = CDL->kiri;
        CDL->kiri->kanan = baru;
        CDL->kiri = baru;
    }
}

    2.) Penyisipan Simpul Belakang

Langkah-langkah penyisipan simpul baru pada Linked List di posisi belakang dapat dilakukan seperti berikut ini :

• Jika Linked List belum ada (NULL) maka simpul baru menjadi awal Linked List (CDL = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan:
• Pointer kanan simpul baru menunjuk CDL (Baru->Kanan =CDL).
• Pointer kiri simpul baru menunjuk yang ditunjuk pointer kiri CDL (Baru->Kiri = CDL->Kiri).
• Pointer kanan dari simpul yang ditunjuk pointer Kiri CDL menunjuk simpul baru (CDL->Kiri->Kanan = Baru).
• Pointer kiri CDL menunjuk simpul baru (CDL->Kiri = Baru).

Misalkan kita memiliki Linked List yang terdiri dari tiga simpul dengan berisi masing-masing informasi A, B, dan C, juga memiliki suatu simpul baru yang berisi informasi D. Simpul Baru akan disisipkan di bagian belakang Linked List. Skema penyisipan simpul belakang dapat dilihat pada Gambar diatas.

Dan, inilah Poster Infografik yang telah saya buat tentang Singly, Dubly, dan Circular Linked List :

Itulah Materi tentang Linked List yang telah saya sampaikan. Mohon maaf apabila ada kesalahan sedikitpun baik itu Penulisan Kata ataupun kesalahan dalam Program.

Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.