Linked List Review and Operation of Single Linked List
Linked List Review and Operation of Single Linked List
Pada hari ini saya mempelajari operasi pada linked list
yaitu single linked list yang sudah kita ketahui pertemuan sebelumnya bahwa
single linked list hanya mempunya satu pointer yaiut *next yang menunjuk ke
node selanjutnya. Operasi pada linked list yang saya pelajari hari ini adalah
push, pop, dan display.
Hal pertama yang kita lakukan adalah mendeclare struct,
struct Data{
int
num;
Data
*next;
}*head, *tail;
Dapat dibayangkan seperti gerbong yang saling terhubung dan
memiliki isi berupa integer, karena single linked list jadi hanya memiliki
pointer *next. *head dan *tail disini berfungsi untuk menandakan data pertama
dan data terakhir.
Berikut penjelasan mengenai operasi-operasi tersebut beserta
kodingannya:
- . Push Belakang
Yaitu operasi insert dari belakang data,
sehingga tail akan terus bergerak selagi data di insert sedangkan head akan
tetap pada data pertama.
void pushTail(int value){
Data
*curr = (Data *) malloc(sizeof(Data));
curr->num
= value;
if(head
== NULL){
head
= tail = curr;
}
else{
tail->next
= curr;
tail
= curr;
}
tail->next
= NULL;
}
Dalam push ada kondisi yang harus diingat
yaitu jika data kosong alias NULL. Jika data tidak kosong maka kita harus
mengarahkan tail untuk menunjuk alamat selanjutnya yaitu curr.
- . Push Depan
Yaitu operasi insert dari depan data, sama
seperti push belakang hanya saja pada push depan pointer yang kita mainkan
adalah head.
void pushHead(int value){
Data
*curr = (Data *) malloc(sizeof(Data));
curr->num
= value;
if(head
== NULL){
head
= tail = curr;
}
else{
curr->next
= head;
head
= curr;
}
tail->next
= NULL;
}
- . Push Tengah
Yaitu insert dari tengah suatu data, yang
berbeda dari push tengah yaitu ada pointer tambahan selain curr. Push tengah
juga melakuan sorting agar tau data
tersebut akan diletakkan pada gerbong ke berapa.
void pushMid(int value){
Data
*curr = (Data *) malloc(sizeof(Data));
curr->num
= value;
if(head
== NULL){
head
= tail = curr;
}
else{
Data
*temp = head;
while(temp->next->num
< value){
temp
= temp->next;
}
curr->next
= temp->next;
temp->next
= curr;
}
}
void push(int value){
if(head
== NULL){
pushHead(value);
}
else{
if(value
<= head->num){
pushHead(value);
}
else
if(value >= tail->num){
pushTail(value);
}
else{
pushMid(value);
}
}
}
Saya membuat function push untuk menentukan
apakah data tersebut berada di depan head atau dibelakang tail jika else maka
saya akan memanggil pushMid nya. Pada pushMid saya menambahkan *temp dimana
akan di looping hingga nilainya lebih besar dari value.
- . Pop Depan
Yaitu operasi untuk delete data dari depan.
void popHead(){
Data
*temp = head;
if(head
== NULL){
return;
}
if(head
== tail){
head
= tail = NULL;
}
else{
head
= head->next;
}
free(temp);
}
Ada kondisi yang harus diingat pada pop
yaitu: jika data kosong, jika data hanya satu, dan data lebih dari satu.
- . Pop Belakang
Yaitu operasi untuk delete data dari
belakang.
void popTail(){
Data
*temp = head;
if(head
== NULL){
return;
}
if(head
== tail){
head
= tail = NULL;
}
else{
while(temp->next
!= tail){
temp
= temp->next;
}
free(tail);
tail
= temp;
tail->next
= NULL;
}
}
Pop belakang berbeda dengan pop depan
karena single linked list hanya punya *next jadi tidak bisa langsung menunjuk
data sebelumnya., untuk mengatasi ini kita perlu memindahkan temp ke head lalu
looping hingga data selanjutnya bukan tail.
- . Pop Tengah
Yaitu operasi untuk delete data dari tengah
atau sesuai value yang diberikan.
void pop(int value){
Data
*temp = head;
if(head
== NULL){
return;
}
while(temp->num
!= value){
temp
= temp->next;
if(temp
== NULL){
return;
}
}
if(temp
== head){
popHead();
}
else
if(temp == tail){
popTail();
}
else{
Data
*key = head;
while(key->next
!= temp){
key
= key->next;
}
key->next
= temp->next;
free(temp);
}
}
Pada pop tengah kita perlu temp untuk di
looping hingga ketemu value yang diberikan, untuk mempermudah jika valuenya
terletak di head atau tail maka langsung memanggil function popHead atau
popTail jika tidak ditemukan valuenya maka di return.
Perlu diketahui function free digunakan
untuk mengalokasikan memori yang sudah di pesan.
- . Pop All
Yaitu operasi untuk delete semua data atau
membersihkan memori. Biasanya dilakukan setelah melakukan function display atau
menampilkan data.
void
popAll(){
while(head != NULL){
popHead();
}
}
Selama head
nya bukan NULL maka saya memanggil function popHead.
- . Display
Yaitu operasi untuk menampilkan semua data
yang di insert.
void display(){
Data
*temp = head;
while(temp
!= NULL){
printf("%d\n",
temp->num);
temp
= temp->next;
}
}
Jadi selama temp nya bukan NULL akan terus
mencetak karena pada data terakhir yaitu tail pasti akan menunjuk ke NULL yang
berarti akhir dari data.
Kesimpulannya adalah single linked list
digunakan jika data tidak dapat menunjuk ke data sebelumnya contoh
implementasinya adalah stack. Sedangkan, double linked list dapat menunjuk ke
data sebelumnya yang membuat berbeda adalah pada double linked list jika kita
insert data atau delete data maka kita harus mengubah next dan prev,
keuntungannya pada pop belakang kita bisa langsung menunjuk ke data sebelum
tail tanpa harus looping lagi.
Comments
Post a Comment