Linked List (Week 3)
Review Linked List
Hari ini saya mempelajari codingan dari linked list (push dan pop).
Untuk push, berarti membuat list baru, yang dipelajari kali ini adalah push belakang, baik untuk single linked list maupun double linked list.
struct node{
int value;
struct node *next, *prev;
}*head, *curr, *tail;
void pushBelakangSingle(int value){
curr = (struct node *) malloc(sizeof(struct node));
curr->value = value;
if(head == NULL){
head = tail = curr;
}
else{
tail->next = curr;
tail = curr;
}
curr->next = NULL;
}
Penjelasan (Push Belakang Single Linked List)
Untuk membuat list baru, kita harus memesan memori terlebih dahulu dan memberikan nilai pada node curr. Kemudian, untuk menentukan apakah list ini merupakan list pertama atau bukan, maka kita mengecek apakah head merupakan NULL, jika iya, maka kita tinggal head = tail = curr, karena merupakan list pertama, sehingga secara otomatis, list tersebut merupakan list awal dan list akhir.
Untuk kasus dimana list tersebut bukan list pertama, maka kita cuma perlu membuat tail ke next menunjuk ke nilai curr sekarang, kemudian pindahkan tail ke curr, dan curr (tail yang sekarang) -> next menunjuk NULL.
void pushBelakangDouble(int value){
curr = (struct node *) malloc(sizeof(struct node));
curr->value = value;
if(head == NULL){
head = tail = curr;
head->prev = NULL;
}
else{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
curr->next = NULL;
}
Penjelasan (Push Belakang Double Linked List)
Untuk Double Linked List, sama kita harus memesan memori terlebih dahulu, kasih nilai untuk node curr. Kita juga mengecek apakah head merupakan NULL, untuk melihat apakah ini merupakan list pertama, jika iya, maka head = tail = curr, dan head->prev = NULL, dikarenakan sekarang kita menggunakan double linked list, yang dimana memiliki dua tangan, yaitu next dan prev.
Untuk kasus bukan list pertama, maka kita kasih tail->next menunjuk ke curr, dan curr->prev menunjuk ke tail, kemudian pindahkan tail ke curr, dan curr->next dikasih NULL.
void popBelakang(){
curr = head;
if(head == tail){
head = tail = NULL;
free(head);
}
else{
while(curr->next != tail){
curr = curr->next;
}
free(tail);
tail = curr;
tail->next = NULL;
}
}
Penjelasan (Pop Belakang Single Linked List)
Untuk pop (deletion), kita harus menghapus list-list, yang dimana untuk kali ini merupakan pop belakang. Ketika kita membuat list baru (push), maka posisi curr dan tail biasanya berada pada list paling belakang. Sehingga ketika kita langsung menghapus list paling belakang, maka kita tidak bisa mengembalikan tail ke list paling belakang. Maka dari itu, kita harus memindahkan salah satu (curr atau tail) ke list sebelumnya. Berhubung kasus ini merupakan single linked list, maka kita tidak bisa menggunakan prev untuk mundur. Maka kita harus memindahkan curr ke head, kemudian cari sampai curr berada pada list sebelum tail. Jadi jika curr->next bukan tail, maka kita pindahkan curr ke depan dan dilakukan berulang kali hingga kondisinya salah (curr berada pada list sebelum tail). Setelah itu, kita free memori tailnya, tail nya kita kembalikan ke posisi curr sekarang, yang dimana merupakan list terakhir, dan untuk tail->next nya dikasih NULL, karena sebelumnya tail->next menunjuk pada memori yang telah kita free.
void cetak(){
curr = head;
while(curr!=NULL){
printf("%d\n", curr->value);
curr = curr->next;
}
}
Penjelasan (Mencetak semua single linked list dari head ke tail dengan menggunakan looping)
Untuk mencetak linked list bisa kita gunakan dengan cara manual, namun cara tersebut tidaklah efektif. Maka dari itu, kita memanfaatkan looping untuk mencetak list-listnya. Pertama, kita pindahkan dulu curr ke head. Kemudian, kita cek apakah nilainya NULL, jika bukan kita print. Setelah itu, kita pindahkan curr ke list setelahnya, kemudian kita cek lagi kondisinya, dan dilakukan berulang kali hingga curr berada pada posisi NULL.
Komentar
Posting Komentar