Linked List

Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).

Linked List sering disebut juga Senarai Berantai
Linked List saling terhubung dengan bantuan variabel pointer

Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

Gambar tersebut menunjukkan Linked List tunggal atau ’singly-linked list’ dimana tiap simpul hanya memiliki satu taut (link) yang merujuk ke simpul berikutnya atau nilai null pada akhir simpul. Seranai berantai ini hanya bisa diakses maju dari awal simpul ke akhir simpul.

Operasi-Operasi yang ada pada Linked List
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
Find First
Fungsi ini mencari elemen pertama dari linked list
Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Operasi-operasi untuk Stack dengan Linked List
IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
Clear
Fungsi ini akan menghapus stack yang ada.
Operasi-operasi Queue dengan Double Linked List
IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

Single Linked List Circular
Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
Node : rangkaian beberapa simpul
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi SLLC
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.

Deklarasi:
Deklarasi node dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};
Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
Dibutuhkan satu buah variabel pointer: head
Head akan selalu menunjuk pada node pertama

Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.

HEAD Single Linked List Circular
Penambahan data di depan


Penambahan data di depan
void insertDepan(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
printf(”Data masuk\n“);
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

Penambahan data di belakang
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
printf(”Data masuk\n“);
}

Operasi Penghapusan
Penghapusan node dilakukan dengan memutus rantai node kemudian menghapus node. Jika node berada di tengah rangkaian, rangkaian yang terputus perlu disambung kembali. Untuk memudahkan penghapusan simpul dibutuhkan dua cursor sebagai simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai acuan awal simpul dalam rangkaian.

Berikut langkah langkah untuk menghapus simpul dalam rangkaian:

• Buat cursor bantu yang menunjuk ke awal node(simpul).
• Pindahkan cursor ke node berikutnya
• Putus sambungan awal node dengan node berikutnya.
• Hapus rangkaian
• Jika berada di akhir rangkaian, putuskan dari rangkaian sebelumnya
• Jika di tengah rangkaian, pindahkan penunjukan node berikutnya, atau di akhir, atau setelah node yang akan dihapus

Ilustrasi Hapus Depan

Ilustrasi Hapus Depan
void hapusDepan (){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}
Ilustrasi Hapus Belakang

Ilustrasi Hapus Belakang
void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
if(head->next == head){
head = NULL;
}else{
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}

Contoh Coding Stack Dengan Linked List

#include
#include
/* membuat linked list */
typedef struct myLinkedList {
char nim[10];
char nama[35];
int nilai;
myLinkedList *next;
};
myLinkedList *head;
/* keadaan awal */
void init() {
head = NULL;
}
/* fungsi untuk mengecek linked list
* apakah kosong atau tidak
* jika kosong maka bernilai 1
* jika tidak kosong maka bernilai 0
*/
int paKosong() {
if (head == NULL) return 1;
else return 0;
}
/**
* fungsi untuk menambahkan data dari depan node
*/
void tambahDepan() {
myLinkedList *baru;
baru = new myLinkedList;
cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;
baru->next = NULL;
if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
baru->next = head;
head = baru;
}
}
/**
* fungsu untuk menambahkan data dari depan node
*/
void tambahBelakang() {
myLinkedList *baru, *bantu;
baru = new myLinkedList;
cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;
baru->next = NULL;
if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
bantu = head;
while (bantu->next != NULL) {
bantu = bantu->next;
}
bantu->next = baru;
}
}
/**
* fungsi untuk menghapus dari depan node
*/
void hapusDepan() {
myLinkedList *hapus;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
hapus = head;
data = hapus->nim;
head = head->next;
delete hapus;
} else {
data = head->nim;
head = NULL;
}
cout <<>
/**
* fungsi untuk menghapus dari belakang node
*/
void hapusBelakang() {
myLinkedList *hapus, *bantu;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
bantu = head;
while(bantu->next->next != NULL) {
bantu = bantu->next;
}
hapus = bantu->next;
data = hapus->nim;
bantu->next = NULL;
delete hapus;
} else {
data = head->nim;
head = NULL;
}
cout <<>
cout << “Tekan Enter untuk kembali ke Menu!”; getch(); }
/**
* fungsi untuk menampilkan data linked list
*/
void tampilData() {
int no = 1;
myLinkedList *bantu;
bantu = head;
if (paKosong() == 0) {
while (bantu != NULL) {
cout << “No. : ” <<>nim <<>nama <<>nilai <<>
no++;
bantu = bantu->next;
}
cout <<>
} else {
cout << “Data masih kosong ” <<>
/**
* fungsi Menu, Untuk menentukan linked list mana
* yang dipilih
*/
int menu() {
int pilihan;
cout << “+———————-+\n”; cout << “| MENU PILIHAN |\n”; cout << “+———————-+\n”; cout << “| 1. Tambah Depan |\n”; cout << “| 2. Tambah Belakang |\n”; cout << “| 3. Hapus Depan |\n”; cout << “| 4. Hapus Belakang |\n”; cout << “| 5. Tambah Tengah |\n”; cout << “| 6. Hapus Tengah |\n”; cout << “| 7. TampilData |\n”; cout << “| 8. Keluar |\n”; cout << “+———————-+\n”; cout << “| PILIHAN ANDA ? [ ] |\n”; cout << “+———————-+\n”;
cin >> pilihan;
return pilihan;
}
/**
* fungsi operasi data
*/
void operasiData() {
int pilih;
do {
pilih = menu();
switch (pilih) {
case 1 :
tambahDepan();
break;
case 2 :
tambahBelakang();
break;
case 3 :
hapusDepan();
break;
case 4 :
hapusBelakang();
break;
case 5 :
tampilData();
break;
case 6:
cout << “Terima kasih coy!!!”; break; } } while (pilih != 6); }
/**
* PROGRAM UTAMA
*/
void main() {
init();
operasiData();
}

 

 

Share this post