Pada sesi kelas besar minggu ini kami membahas Singly Linked List. Yang dibahas adalah cara membuat Singly Linked List, lalu memasukkan node baru ke list tersebut dan juga menghapus node yang sudah ada. Berikut adalah rangkuman saya untuk pembahasan materi minggu ini dan mohon maaf jika kodingan saya ada yang salah.
Untuk membantu membaca, code akan saya beri warna merah dan comment penjelasan akan saya berikan warna hijau.
Membuat Singly Linked List
Source Codenya:
struct data
{
int value;
struct data *next; // Pada single linked list hanya ada penunjuk untuk node berikutnya.
}*head,*curr,*tail; //head adalah node paling depan
//tail adalah node paling belakang
//curr adalah penunjuk yang akan gerak antar node untuk operasi insert dan
deletenya nanti.
Operasi Insert atau push adalah operasi untuk memasukkan node atau data baru pada linked list. Terdapat dua macam insert yaitu insert(head) dan insert(tail)
1. Insert(head) adalah memasuki node barunya di depan linked listnya yaitu sebelum head, sehingga node baru tersebut menjadi head.
2. Insert(tail) adalah memasuki node barunya di belakang linked list yaitu setelah tail, sehingga node baru tersebut menjadi tailnya/
Insert (tail) :
Source Codenya:
void insert_after_tail(int nilai)
{
curr=(struct data*)malloc(sizeof(struct data)); // mengalokasikan memori untuk node barunya
curr->value = nilai;
if(head==NULL) //jika head kosong maka list baru tersebut adalah head, tail dan juga currnya
{
head=tail=curr;
}
else{
tail->next=curr; //next dari tail akan menunjukkan node baru yaitu curr.
tail=curr; //Lalu tailnya pindah ke node baru tersebut.
}
tail->next=NULL;
}
Insert(head):
Source Codenya:
void insert_before_head(int nilai)
{
curr=(struct data*)malloc(sizeof(struct data)); //alokasi memori untuk node baru
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else
{
curr->next=head; //next dari node baru akan menunjuk pada head dr linked list
head=curr; //Kemudian head akan pindah ke curr atau node baru tadi.
}
}
Operasi delete atau pop adalah operasi untuk menghapus sebuah node atau data dalam linked list. Terdapat 2 macam delete yaitu delete(head) dan delete(tail):
1. delete(head) adalah menghapus node paling depan linked list atau head dari linked list tersebut.
2. delete(tail) adalah menghapus node paling belakang linked list atau tail dari linked list tersebut.
delete(head)
Source Codenya:
void delete_head()
{
if(tail==head)
{
free(curr);
tail=head=curr=NULL;
}
else
{
curr=head; //currnya akan memulai di head.
head=head->next; //kemudian head akan berpindah ke node nextnya/berikutnya.
free(curr); //kemudian curr yang di paling depan tadi akan dihapus
curr=NULL;
}
}
delete(tail)
Source Codenya:
void delete_tail()
{
curr=head; //karena single linked list hanya memiliki ponter pada node berikutnya maka kita
memulai dari node paling awal yaitu head.
if(tail==head)
{
free(curr);
tail = head = curr = NULL;
}
else
{
while(curr->next!=tail)
{
curr=curr->next; //pada looping ini curr akan berpindah sampai pointer nextnya adalah tail
}
free(tail); //lalu tail dihapus
tail=curr; //kemudian curr sebelum tail tadi akan menjadi tail baru linked list tersebut.
tail->next=NULL;
}
}
print:
Kemudian ada operasi print untuk mencetak linked list kita.
Source Codenya:
void print()
{
curr=head; //curr akan memulai dari paling depan karena kita akan mencetak dari depan.
while(curr!=NULL)
{
printf("%d->", curr->value); //di looping ini value yg ditunjuk curr akan di print lalu
curr=curr->next; //curr akan berpindah ke node berikutnya lalu cetak lagi sampai ia ketemu
NULL
}
printf("NULL"); //ini cuma untuk bantu saja bahwa di ujungnya itu NULL
}
Setelah kelas besar, kelas kecil saya mempelajari tentang doubly linked list juga. Berikut adalah rangkuman saya tentang doubly linked list.
Membuat doubly linked list
Doubly Linked List adalah linked list yang mempunyai pointer ke node sesudah dan sebelumnya.
Source Codenya:
struct data
{
int value;
struct data *next,*prev; //pada doubly linked list terdapat penunjuk pada node sebelum dan
berikutnya
}*head,*curr,*tail;
Insert (tail)
void insert_after_tail(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else {
tail->next=curr; //next pada tail akan menunjuk curr atau node baru.
curr->prev=tail; //prev pada curr/node baru akan menunjuk pada tail
tail=curr; //lalu tail akan pindah ke curr atau node baru tadi.
}
head->prev=NULL;
tail->next=NULL;
}
Insert(head)
void insert_before_head(int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(head==NULL)
{
head=tail=curr;
}
else
{
head->prev=curr; //prev pada head akan menunjuk pada curr/node baru
curr->next=head; //lalu next pada node baru/curr akan menunjuk pada head
head=curr; //kemudian head akan pindah ke node baru/curr.
}
head->prev=NULL;
tail->next=NULL;
}
Insert(after)
Memasukkan data sesudah node yang dipilih
Source Codenya:
void insert_after_node(struct data* prev_node, int nilai) //disini akan menerima node yg mau
dimasukkan node baru sesudahnya
dan data/nilainya juga.
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(prev_node==NULL)
{
printf("prev_nodenya tidak boleh NULL\n");
}
else
{
curr->next=prev_node->next; //next pada node baru akan menunjuk next pada prev_node
prev_node->next=curr; //next pada prev_node akan menunjuk pada curr
curr->prev=prev_node; //kemudian prev pada node baru/curr akan menunjuk prev_node.
if(curr->next!=NULL)
{
curr->next->prev=curr;
}
}
}
Insert(before)
Memasukkan data sebelum node yang dipilih
Source Codenya:
void insert_before_node(struct data* next_node, int nilai)
{
curr = (struct data*)malloc(sizeof(struct data));
curr->value = nilai;
if(next_node==NULL)
{
printf("next_nodenya tidak boleh NULL\n");
}
else
{
curr->prev=next_node->prev; //prev pada node baru akan menunjuk prev pada next_node
next_node->prev=curr; //prev pada next_node akan menunjuk pada curr
curr->next=next_node; //kemudian next pada node baru/curr akan menunjuk next_node.
if(curr->prev!=NULL)
{
curr->prev->next=curr;
}
else
{
head=curr;
}
}
}
Delete(tail)
Source Codenya:
void delete_tail()
{
curr=tail; //karena doubly linked list memiliki pointer ke node sebelumnya kita dpt memulai dr tail
if(tail==head)
{
free(curr);
tail = head = curr = NULL;
}
else
{
tail=curr->prev; //tail akan pindah ke prev dari curr
free(curr); //lalu curr akan di hapus
tail->next=NULL;
}
}
Delete(head)
Source Codenya: void delete_head()
{
curr=head;
if(tail==head)
{
free(curr);
tail=head=curr=NULL;
}
else
{
head=curr->next; //head akan pindah ke next dari curr
free(curr); //lalu curr akan di hapus
head->prev=NULL;
}
}
Sekian rangkuman saya untuk data structure minggu ini. Terima kasih dan mohon maaf jika kodingan yang saya buat mungkin ada kesalahan atau sulit dipahami.
No comments:
Post a Comment