Blog information

  • Category: Kuliah

  • Posted By: AglaBridgeMedia

  • Post date: 21 Oct 2020

  • Keywords: circular linked list, circular linked list bahasa c, contoh program circular linked list bahasa c, linked list

  • Views: 3879

Circular Linked List dan Contoh Penerapannya dengan Bahasa C

Assalamualaikum Wr. Wb.

Setelah kita mempelajari Single Linked List dan Double Linked List, sekarang kita masuk pada pembahasan Circular Linked List. Perbedaan dari linked list yang lain adalah terletak pada ujung akhir list, di mana node terakhir pada list akan menunjuk pada node pertama. Sehingga akan terbentuk seperti lingkaran yang saling terhubung.

Node (elemen) circular linked list saling berkait melalui pointer. Bagian next sebuah node menunjuk alamat node selanjutnya. pList: pointer yang menunjuk salah satu node pada list. Node terakhir menunjuk node pertama. Setiap node terdiri atas:

  • Isi data
  • Next, yaitu pointer ke node selanjutnya pada list


Struktur sebuah node dapat dilihat pada kode

struct node { 
	//bagian data 
	tipedata data 1; 
	tipedata data 2; 
	… 
	tipedata data n; 
	//pointer ke node selanjutnya 
	struct node *next; 
}; typedef struct node node;

Deklarasi pList diperlukan sebelum membuat circular linked list, yaitu pointer yang menunjuk salah satu node dari circular linked list.

node *pList = NULL;


Operasi dasar linked list:

  1. Menambah sebuah node.
  2. Menghapus sebuah node.
  3. Mencari sebuah node.
  4. List tranversal.


Menambahkan Sebuah Node

Terdapat empat tahap untuk menambah node linked list:

  1. Membuat node baru.
  2. Mendapatkan node yang terletak sebelum node baru disisipkan (pPre).
  3. Atur next node baru agar menunjuk node sesudah posisi penyisipan.
  4. Atur next pPre agar menunjuk node baru.

            



Menambahkan node di tengah list. Untuk menambah data pada linked list, harus diketahui pList, pointer yang menunjuk node sebelum tempat penyisipan (pPre) dan data yang akan disisipkan (item).




Menghapus node dari linked list

Untuk menghapus sebuah node:

  • Cari node yang akan dihapus (pCur) dan node pendahulunya (pPre).
  • Ubah pPre->next agar menunjuk pCur->next.
  • Hapus pCur menggunakan fungsi free

Untuk menghapus node dari linked list, harus diketahui pList, node yang akan dihapus (pCur), serta pendahulunya (pPre).


Mencari node yang mengandung data tertentu dari linked list

Operasi insert dan delete membutuhkan pencarian pada list untuk menentukan posisi penyisipan atau pointer yang menunjuk data yang akan dihapus.


Traversing Linked List: mengunjungi semua node yang ada pada linked list mulai dari head sampai tail/node terakhir.


Baik, berikut ini akan saya berikan contoh program circular linked list.

#include 
#include 
//#include  //jika memakai windows, aktifkan header ini
#include  //jika memakai linux, aktifkan header ini

//ini dipakai jika menggunakan linux, jika menggunakan windows tanpa fungsi getch() ini.
char getch() {
    char buf = 0;
    struct termios old = { 0 };
    fflush(stdout);
    if (tcgetattr(0, &old) < 0) perror("tcsetattr()");
    old.c_lflag    &= ~ICANON;   // local modes = Non Canonical mode
    old.c_lflag    &= ~ECHO;     // local modes = Disable echo.
    old.c_cc[VMIN]  = 1;         // control chars (MIN value) = 1
    old.c_cc[VTIME] = 0;         // control chars (TIME value) = 0 (No time)
    if (tcsetattr(0, TCSANOW, &old) < 0) perror("tcsetattr ICANON");
    if (read(0, &buf, 1) < 0) perror("read()");
    old.c_lflag    |= ICANON;    // local modes = Canonical mode
    old.c_lflag    |= ECHO;      // local modes = Enable echo.
    if (tcsetattr(0, TCSADRAIN, &old) < 0) perror ("tcsetattr ~ICANON");
    return buf;
 }

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

typedef struct node node;

node *pList = NULL;

node *alokasiNodeBaru(){
  node *pNew = NULL;
  pNew = (node *) malloc(sizeof(node));
  return(pNew);
}


void tambahAwal(node *pNew){
     node *temp;
     if(pList == NULL){
              pNew->next = pNew;
              pList = pNew;
     }
     else{
              //cari node yang menunjuk ke pList
              temp = pList;
              while(temp->next != pList){
                    temp = temp->next;
              }

              temp->next = pNew;
              pNew->next = pList;
              pList = pNew;
     }
}



void cetak(){
     node *pWalker = pList;
     node *pNext = NULL;
     while(pNext != pList){
         printf("pWalker = %d, ", pWalker->data);
         pNext = pWalker->next;
         pWalker = pNext;
         printf("pWalker->next = %d \n", pWalker->data);
     }

}


void tambahTengah(node *pNew){
     node *pWalker;
     pWalker=pList;
     int nilai,sisip;
     printf("masukkan nilai yang ingin ditambahkan: "); scanf("%d",&nilai);
     pNew->data = nilai;
     cetak();
     printf("data disisipkan setelah nilai : "); scanf("%d",&sisip);
     while(pWalker->next!=pList && pWalker->data!=sisip){
                         pWalker=pWalker->next; }

     if(pWalker->next==pList) printf("\ndata tidak ditemukan");
     else {pNew->next=pWalker->next;
           pWalker->next=pNew; }
     cetak();

}

void tambahAkhir(node *pNew){
     node *pPre;
     pPre=pList;
     int nilai;
     printf("masukkan nilai yang ingin ditambahkan: "); scanf("%d",&nilai);
     pNew->data = nilai;
     while(pPre->next!=pList){
                         pPre=pPre->next; }
     pNew->next=pList;
     pPre->next=pNew;

}

void hapusAwal(){
     node *pEnd, *pHapus;
     pEnd=pList;
     pHapus=pList;
     while(pEnd->next!=pList){
                              pEnd=pEnd->next;}
     pEnd->next=pHapus->next;
     pList=pList->next;
     free(pHapus);
}

void hapusTengah(){
     node *pCari,*pPre;int hapus;
     pPre=pList;
     pCari=pList;
     cetak();
     printf("masukkan bilangan yang ingin dihapus: "); scanf("%d",&hapus);
     while(pCari->data!=hapus){
                               pCari=pCari->next; }
     while(pPre->next!=pCari){
                              pPre=pPre->next;}
     pPre->next=pCari->next;
     free(pCari);

}

void hapusAkhir(){
     node *pEnd,*pPre;
     pEnd=pList;
     pPre=pList;
     while(pEnd->next!=pList){
                              pEnd=pEnd->next;}
     while(pPre->next!=pEnd){
                             pPre=pPre->next;}
     pPre->next=pList;
     free(pEnd);
}


int main(int argc, char *argv[])
{
  node *pNew; int pilih,bil;
  do{system("clear");
   printf("----------MENU-----------");
    printf("\n1.tambah awal");
    printf("\n2.tambah tengah");
    printf("\n3.tambah akhir");
    printf("\n4.hapus awal ");
    printf("\n5.hapus tengah");
    printf("\n6.hapus akhir");
    printf("\n7.cetak");
    printf("\n8.exit");
    printf("\npilihan : ");scanf("%d",&pilih);

    if(pilih==1){pNew=alokasiNodeBaru();
                 printf("masukkan bilangan: ");
                 scanf("%d",&bil);
                 pNew->data=bil;
                 tambahAwal(pNew);
                 }
    else if(pilih==2){pNew=alokasiNodeBaru();
                 tambahTengah(pNew);
                 }
    else if(pilih==3){pNew=alokasiNodeBaru();
                 tambahAkhir(pNew);
                 }
    else if(pilih==4){hapusAwal();}
    else if(pilih==5){hapusTengah();}
    else if(pilih==6){hapusAkhir();}
    else if(pilih==7){cetak(); getch();}



}while(pilih!=8);


  printf("\n");
  system("PAUSE");
  return 0;
}
Jika kode program di atas dijalankan, maka akan menghasilkan output seperti berikut.
Pertama saya menambahkan data dengan pilihan 1 dengan nilai 1, kemudian saya tambahkan lagi data dengan pilihan 3 dengan nilai 2, kemudian saya tambahkan lagi dengan pilihan 3 dengan nilai 3. Selanjutnya saya menambahkan data lagi di tengah, setelah nilai 2. Sehingga akan tampil urutan datanya adalah 1 -> 2 -> 0 -> 3.
Adapun cara membaca dari output program di atas adalah, pWalker menunjukkan data sekarang, pWalker->next adalah node selanjutnya. Sehingga data 1, next adalah 2, next adalah 0, next adalah 3, next adalah 1. Nah disini bisa kita lihat akan berbentuk circular/lingkaran, yaitu node terakhir, di mana nilainya adalah 3, akan menunjuk ke node pertama dengan nilai 1.
Sekian dari saya, semoga bermanfaat. Silakan dipahami, dicoba, dan dipraktikkan agar semakin paham dan lancar dalam mengkoding. Happy Coding ^_^.
Wassalamualaikum Wr. Wb.

referensi:
  • linuxquestions.org
  • belajarinformatics.blogspot.com
  • Goodrich Michael T., Tamassia Roberto and Mount David M., Data Structure and Algorithms in C++ Second Edition, John Wiley & Sons, Inc., 2011
  • Kernighan Brian W. and Dennis M. Ritchie, The C Programming Language Second Edition, Percentile Hall, 1988
  • Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ Fourth Edition, Pearson, 2013





blog comments powered by Disqus