Tutorial Melayu

Linked list dalam C

Introduction

user

Fairuz

System Engineer (Texas Instruments France), Masters in Electronics , Embedded System Engineering,


LATEST POSTS

Nota: git alias yang biasa digunakan 05th December, 2013

Nota: Android .gitignore 23rd February, 2013

C/C++

Linked list dalam C

Posted on .

Salah satu jenis struktur data adalah linked list. Dalam bahasa melayunya, linked list adalah data yang bersambungan antara satu sama lain. Setiap elemen linked list dipanggil node. Manakala setiap node terbahagi kepada dua bahagian iaitu bahagian data yang akan menyimpan data dan bahagian sambungan (link) yang berfungsi sebagai penyambung elemen-elemen di dalam linked list ini.

Di dalam bahagian sambungan, biasanya ia terdiri dari hanya satu pembolehubah pointer yang akan merujuk kepada address (lokasi) node seterusnya. Linked list ini dipanggil single-linked linked list. Untuk double-linked linked list, terdapat dua pointer, di mana satu merujuk kepada address node seterusnya dan satu lagi merujuk kepada address node sebelumnya. Rujuk artikel ini untuk pemahaman berkenaan pointer.

Node biasanya adalah struktur C untuk menyimpan lebih daripada satu jenis pemboleh ubah (rujuk artikel ini). Salah satu contoh mudah sebuah node adalah:

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

Di mana data merujuk kepada bahagian data dan next merujuk kepada bahagian link. Jadi dengan ini kita boleh bayangkan yang kita membuat satu linked list dengan 3 node seperti contoh di bawah.

#include 
#include 

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

int main(int argc, char *argv[])
{
  struct tnode *node = (struct tnode *)malloc(sizeof(struct tnode));
  
  // menyambung node
  node->data = 100;
  node->next = (struct tnode *)malloc(sizeof(struct tnode));
  
  printf("Data node1 %d \n", node->data);
  printf("Link node1 %p \n", node->next);
  printf("Lokasi node1 %p \n\n", node);
  
  node->next->data = 200;
  node->next->next = (struct tnode *)malloc(sizeof(struct tnode));
  
  printf("Data node2 %d \n", node->next->data);
  printf("Link node2 %p \n", node->next->next);
  printf("Lokasi node2 %p \n\n", node->next);
  
  node->next->next->data = 300;
  node->next->next->next = NULL;
  
  printf("Data node3 %d \n", node->next->next->data);
  printf("Link node3 %p \n", node->next->next->next);
  printf("Lokasi node3 %p \n\n", node->next->next);
  
  system("PAUSE");	
  return 0;
}

Seperti yang boleh digambarkan seperti di bawah.

Berikut adalah hasil output kod di atas setelah dijalankan menggunakan Dev-C++.

Jadi setelah melihat bagaimana linked list berfungsi, mari kita lihat bagaimana membina satu program linked list yang lengkap. Dalam program linked list, saya membayangkan beberapa fungsi yang boleh membantu kita memanipulasi linked list yang dihasilkan.

Membina node baru
Fungsi ini bertujuan untuk memperuntukkan (allocate) ruang memori untuk node baru dan memasukkan data ke dalamnya.

struct tnode * createnode(int data){
    struct tnode * node;
    node = (struct tnode *)malloc(sizeof(struct tnode));
    node->next = NULL;
    node->data = data;
    return node;       
}

Menambah node
Fungsi ini akan menggunakan fungsi createnode di atas dan kemudiannya memasukkan node tersebut ke dalam linked list yang sedia ada di posisi yang diberi.

void tambahnode(int data, int pos)
{
    int i;
    struct tnode *temp, *prev, *current;

    current = head;

    if(pos > (length()+1) || pos <= 0){
           printf("Posisi tidak sah.\n ");
    }
    else {
         if (pos == 1){
            temp = createnode(data);
            temp->next = head;
            head = temp;
         }
         else{
            for(i=1;inext;
            }

            temp = createnode(data);
            prev->next = temp;
            temp->next = current;
        }
    }
}

Memaparkan data node
Fungsi ini digunakan untuk memaparkan kesemua data yang terkandung di dalam node-node yang ada.

void paparnode(void){
     struct tnode * current = head;

     while(current != NULL) {
          printf("Data node %d \n", current->data);
          printf("Link node %p \n", current->next);
          printf("Lokasi node %p \n\n", current);
          current = current->next;
     }     
}

Mengira jumlah node
Fungsi ini bertujuan untuk memberikan jumlah node yang berada di dalam linked list.

int length(void) {
    struct tnode* current = head;
    int count = 0;

    while (current != NULL) {
          count++;
          current = current->next;
    }
    return count;
}

Membuang node
Fungsi ini bertujuan untuk membuang node di posisi yang ditetapkan.

void deletenode(int pos){
     struct tnode * current = head;
     struct tnode * prev;
     int i;
  
     if(pos > (length()) || pos <= 0){
            printf("Posisi tidak sah.\n");
     } 
     else {
          if(pos == 1){
              head = current->next;
              free(current);     
          } 
          else{
               for(i=1; inext;
               }      
               prev->next = current->next;
               free(current);
          }
     }    
}

Jika kita gabungkan kesemua fungsi-fungsi di atas, kita sudahpun mempunyai satu program linked list yang lengkap.

#include 
#include 

struct tnode { 
    int data; 
    struct tnode *next; 
} *head;
 
struct tnode * createnode(int data){
    struct tnode * node;
    node = (struct tnode *)malloc(sizeof(struct tnode));
    node->next = NULL;
    node->data = data;
    return node;       
}

void tambahnode(int data, int pos)
{
    int i;
    struct tnode *temp, *prev, *current;

    current = head;

    if(pos > (length()+1) || pos <= 0){
           printf("Posisi tidak sah.\n ");
    }
    else {
         if (pos == 1){
            temp = createnode(data);
            temp->next = head;
            head = temp;
         }
         else{
            for(i=1;inext;
            }

            temp = createnode(data);
            prev->next = temp;
            temp->next = current;
        }
    }
 }

void paparnode(void){
     struct tnode * current = head;
     printf("*****************************\n");
     while(current != NULL) {
          printf("Data node %d \n", current->data);
          printf("Link node %p \n", current->next);
          printf("Lokasi node %p \n\n", current);
          current = current->next;
     }     
}

int length(void) {
    struct tnode* current = head;
    int count = 0;
    while (current != NULL) {
          count++;
          current = current->next;
    }
    return count;
}

void deletenode(int pos){
     struct tnode * current = head;
     struct tnode * prev;
     int i;
  
     if(pos > (length()) || pos <= 0){
            printf("Posisi tidak sah.\n");
     } 
     else {
          if(pos == 1){
              head = current->next;
              free(current);     
          } 
          else{
               for(i=1; inext;
               }      
               prev->next = current->next;
               free(current);
          }
     }    
}
 
int main(int argc, char *argv[])
{
    head = NULL;   
    
    tambahnode(100, 1);
    tambahnode(200, 1);
    tambahnode(300, 1);
    tambahnode(400, length() + 1);
 
    paparnode();
    deletenode(3);
    paparnode();
 
    system("PAUSE");	
    return 0;
}
profile

Fairuz

http://www.tutorialmelayu.com

System Engineer (Texas Instruments France), Masters in Electronics , Embedded System Engineering,

Comments
user

Author angga

Posted at 11:38 am May 5, 2012.

wahhh,, sip tutorialnya mas..
trimakasih uda share…

btw,, pake themes apa mas wordpress nya..? elegan banget…

Reply
user

Author santi

Posted at 12:34 am September 12, 2012.

tutorialnya bagus bgt mas , tapi mas tlg dong program untuk penggabungan dua buah list pada singly linked list gmn ya??? trima kasih mas…………….

Reply
user

Author mdpai

Posted at 2:09 pm September 12, 2012.

@angga tidak ingat theme apa kerana sudah lama, tapi sudah diubah sendiri. 🙂

Reply
user

Author mdpai

Posted at 2:15 pm September 12, 2012.

@santi maksudnya mahu gabung dua list macam ni?

list 1 : A -> B -> C
list 3 : D -> E -> F

setelah gabung:
A -> B -> C -> D -> E -> F

senang saja tu. Hanya perlu tuka C.next dari NULL kepada &D

Jika masih tidak faham, boleh tanya lagi

Reply

Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

View Comments (4) ...
Navigation