Linked List

Linked List
• Linked List adalah salah satu bentuk struktur
data, berisi kumpulan data (disebut node atau
simpul) biasanya dalam bentuk struct, yang
tersusun secara sekuensial dan saling
menyambung.
• Linked List sering disebut juga Senarai Berantai.
• Linked List diimplementasikan menggunakan
variabel pointer, sehingga cacah data yang
disimpan dapat bersifat dinamis.
Array VS Linked List Linked List
(Single Linked List Non-Circular - SLLNC)
Pengertian:
• Single: field pointer-nya hanya satu buah dan satu arah.
• Linked List: node-node tersebut saling terhubung satu sama
lain. Setiap node pada linked list mempunyai field yang berisi
pointer ke node berikutnya, dan juga memiliki field yang berisi
data.
• non Circular: pada akhir node maka pointernya menunjuk NULL,
digunakan sebagai kondisi berhenti saat membaca isi linked list.
Single Linked List non-Circular – deklarasi (1/3)
Contoh deklarasi Node
typedef struct TNode{
int data;
TNode *next;
};
Penjelasan:
• 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.
Single Linked List non-Circular – deklarasi (2/3)
• Menggunakan keyword new untuk
menyiapkan sebuah node baru berserta
alokasi memorinya, kemudian node ini
diisi data dan pointer nextnya menunjuk
ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Single Linked List non-Circular
deklarasi (3/3) - contoh program
SLLNC MENGGUNAKAN HEAD
inisialisasi (1/2)
• Dibutuhkan sebuah variabel pointer yaitu head (kepala)
• Head selalu menunjuk pada node pertama
• Manipulasi linked list tidak bisa dilakukan langsung ke
node yang dituju, harus menggunakan suatu pointer
penunjuk ke node pertama dalam linked list (disini adalah
head). Deklarasinya adalah: TNode *head;
SLLNC MENGGUNAKAN HEAD
inisialisasi (2/2)
Fungsi Inisialisasi Single LinkedList
void init(){
head = NULL;
}
Function untuk mengetahui kosong tidaknya Single LinkedList
Jika pointer head tidak menunjuk pada suatu node, maka data masih kosong
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}
SLLNC MENGGUNAKAN HEAD
menambah data di depan
Menambah data di depan
• Pada saat pertama kali (saat data masih
kosong), maka penambahan data dilakukan
dengan cara node head ditunjukkan ke node
baru tersebut.
• Untuk menambah data selanjutnya dengan cara
menambah node baru yang akan dikaitan di
node paling depan
• Prinsip mengkaitkan node baru dengan head,
kemudian head akan menunjuk pada data baru
tersebut sehingga head tetap menjadi data
terdepan.
SLLNC MENGGUNAKAN HEAD
menambah data di depan - ilustrasi
SLLNC MENGGUNAKAN HEAD
menambah data di depan - contoh program
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;
}
printf(”Data masuk\n”);
}
SLLNC MENGGUNAKAN HEAD
menambah data di belakang
Menambah data di belakang
• Pada saat pertama kali (saat data masih kosong), maka
penambahan data dilakukan dengan cara node head
ditunjukkan ke node baru tersebut.
• Untuk menambah data berikutnya, menambah data di
belakang lebih sulit karena butuh pointer bantu untuk
mengetahui node paling belakang. Selanjutnya pointer
bantu dikaitkan dengan node baru.
• Catatan untuk mengetahui data paling belakang perlu
digunakan proses perulangan.
SLLNC MENGGUNAKAN HEAD
menambah data di belakang – ilustrasi (1/2)
SLLNC MENGGUNAKAN HEAD
menambah data di belakang – ilustrasi (2/2)
SLLNC MENGGUNAKAN HEAD
menambah data di belakang - contoh program
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
printf("Data masuk\n“);
}
SLLNC MENGGUNAKAN HEAD
menampilkan seluruh isi list
• Menampilkan seluruh isi list dengan cara menelusuri
linked list satu-persatu dari awal sampai akhir node
menggunakan pointer bantu.
• Catatan pointer head yang menjadi tanda awal linked
list tidak boleh berubah atau berganti posisi.
• Penelusuran dilakukan terus sampai dengan node
terakhir menunjuk ke nilai NULL. Jika tidak NULL, maka
node bantu akan berpindah ke node selanjutnya dan
membaca isi data menggunakan field next.
• Catatan jika head masih NULL berarti data masih
kosong.
SLLNC MENGGUNAKAN HEAD
menampilkan seluruh isi list - contoh program - ilustrasi
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<data<<" ";
bantu=bantu->next;
}
printf(“\n”);
} else printf(“Masih kosong\n“);
}
SLLNC MENGGUNAKAN HEAD
menghapus data pertama (terdepan)
• Menghapus node/data pertama (terdepan) yang
ditunjuk oleh head pada linked list.
• Menghapus node terdepan tidak boleh dilakukan jika
node sedang ditunjuk oleh pointer, sehingga harus
menggunakan pointer lain untuk menunjuk node yang
akan dihapus, contoh pointer hapus, kemudian
menghapus pointer hapus menggunakan perintah
delete.
• Catatan sebelum data terdepan dihapus, head harus
menunjuk ke node sesudahnya agar list tidak putus.
Head akan menunjuk ke node data terdepan yang baru.
• Jika head NULL maka berarti data telah kosong.
SLLNC MENGGUNAKAN HEAD
menghapus data pertama (terdepan) - contoh program - ilustrasi
Function untuk menghapus data terdepan
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;
}
printf(“%d terhapus\n“,d);
} else cout<<"Masih kosong\n";
}
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang)
• Membutuhkan 2 pointer tambahan yaitu: pointer bantu
dan pointer hapus.
• Pointer hapus untuk menunjuk node yang akan dihapus.
• Pointer bantu untuk menunjuk node sebelum node yang
dihapus yang kemudian menjadi node terakhir.
• Pointer bantu selalu bergerak sampai sebelum node yang
akan dihapus, kemudian pointer hapus diletakkan setelah
pointer bantu. Selanjutnya pointer hapus akan dihapus,
sedangkan pointer bantu menunjuk ke NULL.
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang) - ilustrasi
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang) – contoh program
Function untuk menghapus data paling belakang
void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%d terhapus\n“,d);
} else printf(“Masih kosong\n“);
}
SLLNC MENGGUNAKAN HEAD
menghapus semua data (semua elemen linked list) – contoh program
Function untuk menghapus semua elemen Linked List
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
}

ini adalah contoh yang berhasil aku buat.. mohon maaf bila syntax setelah diposting berubah:hehehehe

#include <conio.h>

#include <iostream.h>



struct TNode //deklarasi awal LINKED LIST

{

int data;

TNode *next;

};



TNode *head;



void init()

{

head = NULL;

}



int isEmpty()

{

if(head == NULL) return 1;

else return 0;

}



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();

}



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();

}



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();

}



void tampil()

{

TNode *bantu;

bantu = head;

if(isEmpty()==0)

{



cout<<" Data Linked List"<<endl;

cout<<"================================="<<endl;



while(bantu!=NULL)

{

cout<<" --> "<<bantu->data<<" ";

bantu=bantu->next;

}

cout<<" --> NULL";

cout<<endl;

} else cout<<" Linked List Masih kosong...\n";

getch();

}



void main()

{

int pil,dataku,cari;

init(); //inisialisasi awal

do

{

clrscr();

cout<<" SINGLE LINKED LIST"<<endl;

cout<<"=========================="<<endl;

cout<<" 1. Insert List"<<endl;

cout<<" 2. Delete Front"<<endl;

cout<<" 3. Show Linked List"<<endl;

cout<<" 4. Search Data"<<endl;

cout<<" 5. Exit"<<endl;

cout<<"=========================="<<endl;

cout<<endl;

cout<<"Pilihan Anda = "; cin>>pil;



switch (pil)

{

case 1 :

cout<<endl;

cout<<" Insert Data --> "; cin>>dataku;

insertDepan(dataku);

break;

case 2 :

hapusDepan();

break;

case 3 :

cout<<endl;

cout<<endl;

tampil();

break;

case 4 :

cout<<endl;

cout<<" Data yg Dicari --> "; cin>>cari;

search(cari);

break;

};

}

while (pil != 5);

}
Sumber Referensi
• James Roberge, Stefan Brandle, dan David
Whittington, 2003, C++ Data Structures 2nd
Edition, Jones and Bartlett Publishers, Inc.,
Sudbury, Massachusetts.
• Antonius Rachmat Chrismanto – UKDW
Yogyakarta.
• P. Insap Santosa, 1992, Struktur Data
Menggunakan Turbo Pascal 6.0, Penerbit
Andi, Yogyakarta.
• Berbagai sumber dari Internet.