LINKED LIST

Mengapa Linked Lists?

Linked list dan array memiliki mirip karena mereka berdua berfungsi untuk menyimpan kumpulan data. Terminologinya adalah bahwa array dan linked list menyimpan "elemen" atas nama kode "klien". Jenis spesifik dari elemen tidak penting karena pada dasarnya struktur yang sama mampu  enyimpan elemen dari jenis apa pun. Salah satu cara untuk memahami linked list adalah dengan melihat bagaimana array bekerja dan berpikir tentang pendekatan alternatif untuk melakukan hal yang sama.

Linked list memiliki kelebihan dan kelemahan mereka sendiri, dimana kelebihan dari linked list merupakan kekurangan dari array. Fitur dari array mengikuti strategi pengalokasian memorinya untuk semua elemen dalam satu blok memori. Linked list menggunakan strategi yang sangat berbeda. Seperti yang akan kita lihat, linked list mengalokasikan memori untuk setiap elemen secara terpisah dan hanya bila diperlukan.

Seperti Apa Linked List

Sebuah array mengalokasikan memori untuk semua elemennya dalam sebuah blok besar dari memori. Sebaliknya, linked list mengalokasikan ruang memori secara terpisah untuk masing masing elemennya pada blok memorinya masing-masing yang disebut "linked list element" atau "node". Linked list akan terbentuk dengan menghubungkan semua elemen dengan menggunakan pointer yang menghubungkan satu node dengan node yang lain seperti sebuah rangkaian rantai.

Masing-masing node terdiri dari 2 bagian: bagian "data" untuk menyimpan elemen dengan tipe apapun untuk clientnya, dan bagian "next" yang merupakan sebuah pointer berfungsi untuk menghubungkan node ini dengan node berikutnya. Masing-masing node di alokasikan di heap dengan memanggil fungsi malloc(), sehingga node akan tetap tersimpan di memori sampai dilakukan pemanggilan terhadap fungsi free(). Di depan linked list terdapat pointer yang menunjuk elemen pertama. Berikut contoh sebuah linked list.

Tipe Linked List: 

Node dan Pointer Sebelum menulis kode untuk membuat linked list di atas, kita memerlukan 2 tipe, yaitu node dan dan pointer. 

• Node Tipe untuk node yang akan memuat bagian tubuh dari list. Ini dialokasikan di heap. Setiap node berisi elemen data klien tunggal dan pointer ke node berikutnya dalam list. Tipe: struct node
  
  struct node {
     int data;
     struct node* next;
  };
  
• Node Pointer Tipe untuk pointer ke node. Ini akan menjadi kepala pointer dan bagian berikutnya dalam setiap node. Dalam C dan C ++, tidak ada deklarasi tipe terpisah diperlukan karena jenis pointer adalah tipe node diikuti oleh '*'. Tipe: struct node*

fungsi BuildOneTwoThree()

Berikut adalah fungsi sederhana dimana pointer digunakan untuk membangun list {1, 2, 3}. Penggunaan memori yang digambarkan di atas sesuai dengan keadaan memori pada akhir fungsi ini. Fungsi ini menunjukkan bagaimana memanggil fungsi malloc() dan mengisi sebuag pointer untuk membangun struktur linked list di dalam memori. 

/* Build the list {1, 2, 3} in the heap and store

its head pointer in a local stack variable. 

Returns the head pointer to the caller. */ 

struct node* BuildOneTwoThree() { 

   struct node* head = NULL; 

   struct node* second = NULL; 

   struct node* third = NULL; 

   // allocate 3 nodes in the heap 

   head = malloc(sizeof(struct node)); 

   second = malloc(sizeof(struct node));

   third = malloc(sizeof(struct node)); 

   head.data = 1; // setup first node 

   head.next = second; // note: pointer assignment rule 

   second.data = 2; // setup second node 

   second.next = third; 

   third.data = 3; // setup third link 

   third.next = NULL; 

   // At this point, the linked list referenced by "head" 

   // matches the list in the drawing. 

   return head; 

} 

fungsi length() 

Fungsi length() mengambil sebuah linked list dan menghitung jumlah elemen pada list tersebut. length() fungsi sederhana pada list, namun menunjukkan beberapa konsep penting dari linked list yang akan sering kita gunakan pada fungsi list yang lebih kompleks.

/* 
Given a linked list head pointer, compute and return the number of nodes in the list. 
*/ 
int length(struct node* head) { 
   struct node* current = head; 
   int count = 0; 
   while (current != NULL) { 
      count++; 
      current = current.next; 
   } 
   return count; 
}

fungsi isEmpty()

Fungsi isEmpty() digunakan untuk mengetahui apakah sebuah list ada isinya atau tidak.

/* 
Given a linked list head pointer, compute 
and return the number of nodes in the list. 
*/ 
bool isEmpty(struct node* head) { 
   return (head == null); 
}

kode insertFirst() 

Berikut adalah kode insertFirst(). List di lewatkan melalui sebuah pointer yang mengarah pada head pointer dari list. Pada kode menggunakan '&' dan '*' pada parameter pemanggilan. Mengapa?

/* 
Takes a list and a data value. 
Creates a new link with the given data and pushes
it onto the front of the list. 
The list is not passed in by its head pointer. 
Instead the list is passed in as a "reference" pointer 
to the head pointer -- this allows us
to modify the caller's memory. 
*/ 
void insertFirst(struct node*& head, int data) { 
   struct node* newNode = malloc(sizeof(struct node));
   newNode.data = data; 
   newNode.next = head; 
   head = newNode; 
}

kode insertAfter() 

Berikut adalah kode insertAfter(). Sebenarnya, isi dari fungsi ini kurang lebih sama dengan fungsi sebelumnya.

/*
insert new node after one node 
*/ 
void insertAfter(struct node*& nodeBefore, int data) { 
   struct node* newNode = malloc(sizeof(struct node)); 
   newNode.data = data; 
   newNode.next = nodeBefore.next; 
   nodeBefore.next = newNode; 
}

kode insertBefore() dan insertLast() 

Silahkan buat sendiri kode untuk fungsi insertBefore() dan insertLast() sebagai latihan.

kode deleteFirst() 

Berikut adalah kode deleteFirst(). Kode ini berfungsi untuk menghapus elemen pertama dari linked list.

/* 
delete first node. It is just move the pointer that point to the head node, to the next one 
*/ 
void deleteFirst(struct node*& head) { 
   head = head.next; 
} 

kode deleteAfter() 

Kode deleteAfter() memiliki bentuk yang sama dengan kode sebelumnya. Fungsinya untuk menghapus sebuah elemen setelah elemen tertentu.

/* 
delete one node after specific node. It is just move the pointer that point to the next node to next of the next 
*/ 
void deleteAfter(struct node*& nodeBefore) { 
   nodeBefore.next = nodeBefore.next.next; 
} 

deleteBefore() and deleteLast() Code 

Silahkan buat sendiri kode untuk fungsi deleteBefore() dan deleteLast() sebagai latihan.

Fungsi find() 

Fungsi find() digunakan untuk melakukan pencarian sebuah kunci/data pada linked list. Berikut adalah contohnya

/* 
Iterate through the list to find a key 
*/ 
bool find(struct node* head, int key) { 
   struct node* current = head; 
   while (current != NULL) { 
      if (key == current.data) { 
         return true; 
      }
      current = current.next; 
   } 
   return false; 
} 

LATIHAN

1. Tulislah sebuah fungsi Count() yang akan menghitung berapa kali sebuah angka yang dilewatkan muncul dalam keseluruhan list. Kode ini akan memiliki bentuk yang mirip dengan fungsi length() yang pernah kita bahas. 
2. Tuliskan sebuah fungsi RemoveDuplicates() yang mengambil list terurut sebagai inputannya dan menghapus elemen-elemen yang muncul lebih dari 1 kali. Idealnya, semua node hanya dikunjungi 1 kali.