Linked List di C

Linked List merupakan struktur data yang konsepnya seperti block block yang saling terhubung. Bisa dibayangkan seperti kereta yang saling terhubung antar gerbong.

Sama seperti Array dinamis di C kita akan membuat Linked List dengan bantuan typedef, struct, dan pointer.

Istilah istilah dalam linked list:

1. Node: tempat menampung niai dan block selanjutnya.
2. Head: merupakan list pertama dari linked list, ini merupakan awal dari linked list.
3. Tail: merupakan list terakhir dari linked list, ini merupakan akhir dari linked list, biasanya memiliki value next sama dengan NULL.

Pertama kita buat struct untuk menampung block

typedef struct Node {
  int value;
  struct Node *next;
} Node;

Kode diatas mungkin terlihat aneh karena kita menuliskan Node setelah struct dan Node setelah tutup kurung kurawal. Sebenarnya dua Node ini memiliki tukuan berbeda, Node setelah struct digunakan untuk mendefinisikan block selanjutnya struct Node *next;, sedangkan Node kedua digunakan sebagai alias.

Selanjutnya kita buat function untuk menambahkan data atau node, langkahnya

1. Kita akan membuat Node baru, yang akan ditambahkan ke list.
2. Cek apakah Node ini merupakan yang pertama? jika iya maka ubah memory address head ke Node yang baru dibuat
3. Jika Node bukan merupakan yang pertama, maka kita cari Node terakhir dengan cek apakah next merupakan NULL
4. Kita akan set value sebagai block berikutnya dengan set next

void add(Node **head, int value){
  Node *n = malloc(sizeof(*n));
  n->value = value;
  n->next = NULL;

  // first init
  if(*head == NULL){
    n->value = value;
    n->next = NULL;
    *head = n;
    return;
  }

  // if its exist, add into the last of list
  Node *tmp = *head;
  while(tmp->next != NULL){
    tmp = tmp->next;
  }
  tmp->next = n;
}

Print Node

Kita akan buat function baru untuk print semua value dari LInked List, dengan cara loop setiap node hingga node tidak sama dengan NULL

void printNode(Node *head){
  while(head != NULL){
    printf("value: %d\n", head->value);
    head = head->next;
  }
}

Free Memory

Sama seperti Array dinamis, semua kode yang menggunakan manual memory allocation kita harus free manual. Cara free memory manual dengan loop semua Node mulai dari head hingga tail, lalu kita free satu satu.

void freeNode(Node **head){
  Node *prev;
  Node *tmp;

  tmp = *head;
  prev = tmp;
  while(tmp != NULL){
    prev = tmp;
    tmp = tmp->next;
    free(prev);
  }
}

Full Code

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

typedef struct Node {
  int value;
  struct Node *next;
} Node;

void add(Node **head, int value){
  Node *n = malloc(sizeof(*n));
  n->value = value;
  n->next = NULL;

  // first init
  if(*head == NULL){
    n->value = value;
    n->next = NULL;
    *head = n;
    return;
  }

  // if its exist, add into the last of list
  Node *tmp = *head;
  while(tmp->next != NULL){
    tmp = tmp->next;
  }
  tmp->next = n;
}

void printNode(Node *head){
  while(head != NULL){
    printf("value: %d\n", head->value);
    head = head->next;
  }
}

void freeNode(Node **head){
  Node *prev;
  Node *tmp;

  tmp = *head;
  prev = tmp;
  while(tmp != NULL){
    prev = tmp;
    tmp = tmp->next;
    free(prev);
  }
}

int main(void){
  Node *x = NULL;
  for(int i = 0; i < 10; i++){
    add(&x, i);
  }

  printNode(x);
  freeNode(&x);
  return 0;
}