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

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;
}

• 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