Dengan menggunakan linked list maka programmer dapat menyimpan 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). Secara umum linked list tersusun atas
sejumlah bagian
bagian data yang lebih kecil yang terhubung dan tiap - tiap rantai terhubung dengan 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.
Linked list memiliki beberapa jenis, di antaranya :
A. Singly linked list
B. Double linked list
C. Multiply linked list
D. Linear linked list
E. Circular Linked List
Namun di sini, hanya akan dijelaskan hanya Singly linked list dan
Double linked listkarena itu sudah menyeluruh dalam linked list itu.
A. Single linked list non circular
Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul.
Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian,dengan demikian hanya
diperlukan sebuah variabel pointer.Susunan berupa untaian semacam ini disebut Single Linked Lis
(NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana.Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Dalam pembuatan single linked list dapat menggunakan dua metoda:
a. LIFO (Last In First Out) aplikasinya : Stack (Tumpukan)Adalah suatu metoda pembuatan linked list dimana data yang masuk paling akhir adalah data yang keluar paling awal.
b. FIFO (First In First Out) aplikasinya : Queue (Antrian)Adala suatu metoda pembuatan linked list dimana data yang masuk paling awal adalah data yang keluar paling awal juga.
Ada beberapa proses dalam pembuatan linked list yaitu :
· Pembuatan simpul baru
Contoh algoritmanya :
struct TNode
{
int data;
TNode *next;
};
Pembuatan struct bernama TNode yang berisi 2 field,
yaitu field data bertipe integer dan field next
yang bertipe pointer dari Tnode. Setelah pembuatan
struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai
kepala linked list.
TNode *head;
elanjutnya digunakan keyword new
yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya
kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL. Contohnya :
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Dalam pembuatan simpul baru jangan lupa untuk menggunakan fungsi malloc() sebagai pointer.
Fungsi ini dideklarasikan di dalam header
stdlib.h. Dengan demikian, jangan lupa
untuk meng-include header tersebut.
Contoh instruksinya :
P = (simpul*) malloc(sizeof(simpul));
Algoritmanya :
Void Buat_Simpul(int x)
{
P = (simpul*) malloc(sizeof(simpul));
If (P != NULL)
{ P - > Info = x; }
Else
Cout<<”Simpul gagal dibuat”;
}
Selanjutnya terdapat fungsi Inisialisasi dalam single linked list yaitu suatu proses awal yang menyatakan linked list belum ada.
Potongan algoritmanya :
void init()
{
head = NULL;
}
Di mana jika pointer head tidak menunjuk pada suatu node maka kosong.
int isEmpty()
{
if(head == NULL) return 1;
else return 0;
}
· Penambahan Node Linked List
Bila setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat dengan head) maka
kompleksitas yang diperlukan untuk menambah node baru dalam linked list konstan atau O(1).
Untuk menu memasukkan data baru , digunakan bentuk algoritma seperti ini :
void insertDepan(int databaru)
{
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1)
{
head=baru;
head->next = NULL;
}
else
{
baru->next = head;
head = baru;
}
cout<<endl;
cout<<” Data masuk…\n”;
getch();
}
Penelusuran Node Linked List
Kompleksitas penelusuran (pencarian) node dalam linked list adalah linier atau O(n). Hal ini disebabkan karena node -
node dalam linked list disusun secara acak (tidak berurut). Seandainya pun simpul-simpul dalam linked list disusun
secara berurut, metode pencarian biner (binary search) tetap tidak dapat dipergunakan. Ada 2 alasan mengapa
pencarian biner tidak dapat digunakan:
1.
Linked list tidak memiliki indeks seperti array, sehingga akses langsung ke node tertentu tidak dapat dilakukan. Untuk
menuju ke node tertentu, proses pemeriksaan tetap dimulai dari node head (node terdepan). Oleh karena itu proses
pencarian selalu berjalan secara linier.
2.
Tidak dapat membagi linked list menjadi 2 bagian yang sama besar seperti saat membagi array menjadi 2 bagian bila
metode pencarian biner diaplikasikan pada array terurut.
Contoh programnya :
void search(int caridata)
{
TNode *bantu;
bantu = head;
int ketemu = 0;
int index=0;
if(isEmpty()==0)
{
while(bantu!=NULL)
{
bantu->data;
if (caridata == bantu->data)
{
cout<<endl;
cout<<” Data Ditemukan…”<<endl;
cout<<” Index Ke - ”<<index;
ketemu = 1;
break;
}
bantu=bantu->next;
index++;
}
cout<<endl;
if (ketemu == 0)
cout<<” Data Tidak Ditemukan…”<<endl;
cout<<endl;
} else cout<<” Linked List Masih kosong…\n”;
getch();
}
· Penghapusan Node Linked List
Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node
yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut
dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam
linked list adalah O(n). Contoh programnya :
void hapusDepan()
{
TNode *hapus;
int d;
if (isEmpty()==0)
{
if(head->next != NULL)
{
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
}
else
{
d = head->data;
head = NULL;
}
cout<<endl;
cout<<” Data ”<<d<<” terhapus…\n”;
}
else
{
cout<<endl;
cout<<endl;
cout<<” Linked List Masih kosong…\n”;
}
getch();
}
B. Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Tidak jauh berbeda dengan materi sebelumnya yakni Single Linked List. Materi ini hanya menambahkan satu pointer (yang nantinya dapat dikembangkan dengan banyak pointer). Bila kita lihat lagi penggambaran dari Single Linked List :
typedef struct TNode {
int data;
TNode *next;
};
Sedangkan pada materi yang ada sekarang, kita akan menambahkan satu lagi pointernya. Sehingga bila kita lihat ilustrasinya :
typedef struct TNode{
TNode *next;
TNode *prev;
};
Untuk setiap pembuatan node yang baru kita mempergunakan keyword new.
TNode *baru;
baru = new TNode;
baru ->data = databaru;
baru ->next = NULL;
baru-> prev = NULL;
Dalam hal ini, akan membagi materi dalam dua jenis, yakni :
a. Non Circular
b. Circular
Dimana tiap-tiap juga akan terdiri dari linked list yang terdiri dari Head saja dan Head dengan Tail.
A. Non Circular
1. Dengan Head
- Menggunakan 1 pointer head
- Head selalu menunjuk node pertama
Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju.
Sehingga pointer head harus dibuat bernilai null terlebih dahulu :
head = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak,
kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.
Int isEmpty()
{
If (tail == NULL)
Return 1;
Else
Return 0;
}
Contoh program :
· Penambahan didepan
void tambahdata (int databaru){
TNode *baru;
baru = new TNode;
baru -> data = databaru;
baru -> next = NULL;
baru -> prev = NULL;
if (isEmpty()==1) {
head=baru;
head->next=NULL;
head->prev=NULL;
}
else {
baru->next=head;
head->prev=baru;
head=baru;
}
printf(”data masuk”);
}
· Penambahan di belakang
void insertBelakang (int databaru){
TNode *baru,*bantu;
//digunakan untuk mengetahui data terbelakang
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
baru->prev = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
head->prev = NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
baru->prev = bantu;
}
printf(”data masuk”);
}
· Tampil
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
printf(“%i “,bantu->data);
bantu=bantu->next;
}
printf(“\n”);
}
else printf(“Masih Kosong”);
}
· Hapus di depan
void hapusDepan (){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
head->prev = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
prinf(“%i terhapus”,d);
} else printf(“Masih Kosong”);
}
· Hapus di belakang
void hapusBelakang(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
while(hapus->next!=NULL){
hapus = hapus->next;
}
d = hapus->data;
hapus->prev->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%i terhapus”,d);
} else printf(“Masih Kosong”);
}
2. Dengan Head dan tail
- Menggunakan 2 pointer, head dan tail.
- Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir
Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head, *tail;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai
null terlebih dahulu :
head = NULL;
tail = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.
int isEmpty() {
if(tail==NULL) return 1;
else return 0;
}
Contoh program :
· Penambahan di depan
void tambahdata (int databaru){
TNode *baru;
baru = new TNode;
baru -> data = databaru;
baru -> next = NULL;
baru -> prev = NULL;
if (isEmpty()==1) {
head=baru;
tail=head;
head->next=NULL;
head->prev=NULL;
tail->next=NULL;
tail->prev=NULL;
}
else {
baru->next=head;
head->prev=baru;
head=baru;
}
printf(”data masuk”);
}
· Penambahan di belakang
void insertBelakang(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
baru->prev = NULL;
if(isEmpty()==1){
head=baru;
tail=head;
head->next = NULL;
head->prev = NULL;
tail->prev = NULL;
tail->next = NULL;
}
else {
tail->next = baru;
baru->prev = tail;
tail = baru;
tail->next = NULL;
}
printf(“Data sudah masuk\n”);
}
· Tampil
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=tail->next){
prinrf(“%i ”,bantu->data);
bantu=bantu->next;
}
cout<<endl;
} else printf(“masih kosong\n”); }
· Hapus di depan
void hapusDepan(){
TNode *hapus;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
head->prev = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
printf(“%i terhapus\n”,d);
} else printf(“masih kosong\n”);
}
· Hapus di belakang
void hapusBelakang(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = tail;
d = tail->data;
tail = tail->prev;
tail->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
printf(“%i terhapus”,d);
} else printf(“Masih Kosong”);
}
B. Non Circular dengan Head, head & tail
1. Dengan Head
- Menggunakan 1 pointer head
- Head selalu menunjuk node pertama
Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai
null terlebih dahulu :
head = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.
int isEmpty() {
if(head==NULL) return 1;
else return 0;
}
Contoh program :
· Penambahan di depan
void tambahdata (int databaru){
TNode *baru,*bantu;
//pointer bantu digunakan untuk menunjuk node terakhir (head->prev)
baru = new TNode;
baru -> data = databaru;
baru -> next = baru;
baru -> prev = baru;
if (isEmpty()==1) {
head=baru;
head->next=head;
head->prev=head;
}
else {
bantu=head->prev;
baru->next=head;
head->prev=baru;
head=baru;
head->prev=bantu;
bantu->next=head;
}
printf(”data masuk”);
}
· Penambahan di belakang
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next = head;
head->prev = head;
}
else {
bantu=head->prev;
bantu->next = baru;
baru->prev = bantu;
baru->next = head;
head->prev = baru;
}
printf(”data masuk”);
}
· Tampil
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
do{
printf(“%i ”,Bantu->data);
bantu=bantu->next;
}while(bantu!=head);
printf(“\n”);
} else printf(“masih Kosong”);cout<<”Masih kosong\n”;
}
· Hapus di depan
void hapusDepan (){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != head){
hapus = head;
d = hapus->data;
bantu = head->prev;
head = head->next;
bantu->next = head;
head->prev = bantu;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%i terhapus”,d);
} else printf(“Masih kosong\n”);
}
· Hapus di belakang
void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != head){
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = head;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%i terhapus\n”,d);
} else printf(“Masih Kosong”);
}
2. Dengan Head dan tail
- Menggunakan 2 pointer, head dan tail.
- Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir
Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head, *tail;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai
null terlebih dahulu :
head = NULL;
tail = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.
Int isEmpty()
{
If (tail == NULL)
Return 1;
Else
Return 0;
}
Contoh program :
· Penambahan di depan
void tambahdata (int databaru){
TNode *baru;
baru = new TNode;
baru -> data = databaru;
baru -> next = NULL;
baru -> prev = NULL;
if (isEmpty()==1) {
head=baru;
tail=head;
head->next=head;
head->prev=head;
tail->next=tail;
tail->prev=tail;
}
else {
baru->next=head;
head->prev=baru;
head=baru;
head->prev=tail;
tail->next=head;
}
printf(”data masuk”);
}
· Penambahan di belakang
void insertBelakang(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
tail=baru;
head->next = head;
head->prev = head;
tail->next = tail;
tail->prev = tail;
}
else {
tail->next = baru;
baru->prev = tail;
tail = baru;
tail->next = head;
head->prev = tail;
}
printf(“Data masuk\n”);
}
· Tampil
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
do{
cout<<bantu->data<<” ”;
bantu=bantu->next;
}while(bantu!=tail->next);
printf(“\n”);
} else printf(“masih kosong\n”);
}
· Hapus di depan
void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head != tail){
hapus = head;
d = hapus->data;
head = head->next;
tail->next = head;
head->prev = tail;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
printf(“%i terhapus\n”,d);
} else printf(“Masih Kosong”);
}
· Hapus di belakang
void hapusBelakang(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head != tail){
hapus = tail;
d = hapus->data;
tail = tail->prev;
tail->next = head;
head->prev = tail;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
cout<<d<<” terhapus\n”;
} else cout<<”Masih kosong\n”;
}
Posting Komentar