Linked list
1. Insert
Untuk menambahkan node pada sebuah linked list, terdapat 3 cara yang bisa dilakukan, yaitu:
A. Push Head
Pada metode yang ini seperti namanya, kita akan menambahkan node baru yang akan menjadi head yang baru. Contoh source codenya seperti berikut:
void pushHead(int number){
curr = (struct data*) malloc (sizeof(struct data));
curr->value = number;
if(head == NULL){
tail = head = curr;
tail->next = NULL;
}
else{
curr->next = head;
head = curr;
}
}
pada potongan code tersebut, kita bisa melihat bahwa fungsi tersebut bisa dibagi menjadi 3 fase.
Pertama fase pemesanan memori: curr = (struct data*) malloc (sizeof(struct data));
kedua, fase pengisian nilai/value: curr->value = number;
ketiga, fase koneksi: if(head == NULL){
tail = head = curr;
tail->next = NULL;
}
else{
curr->next = head;
head = curr;
}
Pada fase ketiga kita harus membagi ketika head belum ada ,dan ketika head sudah ada.
Jika head sudah ada, maka alamat next dari curr yang telah kita buat harus kita hubungkan dengan head terlebih dahulu kemudian merubah posisi head ke posisi curr.
B. Push Tail
Pada cara yang ini, kita akan menambahkan node baru setelah tail, kemudian memindahkan tail yang lama ke node yang baru saja dihubungkan agar menjadi tail yang baru. Contoh source codenya seperti berikut:
void pushTail(int number){
curr = (struct data*) malloc(sizeof(struct data));
curr->value = number;
if(tail == NULL){
tail = head = curr;
tail->next = NULL;
}
else{
tail->next=curr;
tail=curr;
tail->next=NULL;
}
}
Pada potongan code ini, cara kerjanya mirip seperti cara kerja fingsi pushHead namun perbedaannya terdapat pada bagian:
else{
tail->next=curr;
tail=curr;
tail->next=NULL;
}
Dimana ketika node baru telah dibuat, maka tail yang lama akan dihubungkan dengan node yang baru dibuat, kemudian memindahkan tail ke node tersebut dan tidak lupa untuk meng-assign NULL sebagai alamat next dari tail agar kita bisa tahu bahwa itu adalah ujung dari linked list tersebut.
C. Push Middle
Untuk cara push yang ini, cara kerjanya agak sedikit berbeda dari 2 cara push sebelumnya.
kita harus meng-validasi posisi dari node yang akan ditambah tersebut. Contohnya, kita akan membuat suatu linked list yang terurut secara ascending(asumsi linked listnya telah jadi dan sudah terurut) kemudian kita akan menambahkan suatu node yang nilainya berada di bagian tengah list tersebut. Maka kita akan membuat fungsinya seperti berikut,
void pushMiddle(int number){
curr = (struct data*) malloc(sizeof(struct data));
curr->value = number;
if(head == NULL){
head = tail = curr;
tail->next = NULL;
}
else if(number < head->value){
curr->next = head;
head = curr;
}
else if(number >= tail->value){
tail->next = curr;
tail = curr;
tail->next = NULL;
}
else{
struct data *tmp = head;
while(number >= tmp->next->value){
tmp = tmp->next;
}
curr->next = tmp->next;
tmp->next = curr;
}
}
Pada tiap tahap validasi yang ada pada potongan kode tersebut menentukan posisi dari node yang baru. Contohnya pada bagian else yang paling terakhir, adalah tahap dimana nilai dalam node diketahui bukan yang terkecil maupun yang terbesar sehingga kita harus melooping untuk mencari posisi node tersebut.
2. Delete
Untuk menghapus sebuah node dari sebuah linked list kita harus menggunakan salah satu dari 3 cara yaitu:
a. Pop depan: menghapus head lalu menjadikan node setelah head, menjadi head yang baru.
b. Pop belakang: menghapus tail lalu menjadikan node sebelum tail, menjadi tail yang baru.
c. Pop tengah: menghapus node yang berada di tengah.
Logika codingan untuk pop ini sangat mirip dengan push namun alih-alih kita memesan suatu blok memori, kita membebaskan memori tersebut dan memutuskan hubungan memori tersebut dengan list yang kita miliki. Kita membebaskan memori tersebut dengan syntax "free(apa yg mau di free);".
Contohnya potongan kode berikut yang merupakan fungsi yang menghapus head/pop depan:
void popHead(struct Data **head, struct Data **tail)
{
if (*head == NULL)
printf ("No Data to Delete!\n");
else if (*head == *tail)
{
free(*head);
*head = *tail = NULL;
}
else
{
struct Data *curr = *head;
*head = (*head)->next;
free(curr);
}
}
Pada potongan program diatas, digunakan passing by reference sehingga variable yang digunakan merupakan double pointer(**).
Tidak ada komentar:
Posting Komentar