KONSEP POINTER DAN LINKED LIST
Untuk mengolah data yang banyaknya tidak bisa ditentukan sebelumnya, maka disediakan satu fasilitas yang memungkinan untuk menggunakan suatu perubah yang disebut dengan perubah dinamis (Dinamic variable)
Perubah Dinamis (Dinamic variable)
Suatu perubah yang akan dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
Perbedaan Perubah Statis & Dinamis
Pada perubah statis, isi Memory pada lokasi tertentu (nilai perubah) adalah data sesungguhnya yang akan diolah. Pada perubah dinamis, nilai perubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya dapat dimasukkan secara langsung.
Dalam hal cara pemasukkan data dapat diilustrasikan seperti dibawah ini.
DEKLARASI POINTER
Pointer digunakan sebagai penunjuk ke suatu alamat memori
Dalam pemrograman C++, Type Data Pointer
dideklarasikan dengan bentuk umum :
Type Data * Nama Variabel;
Type Data dapat berupa sembarang type data, misalnya char, int atau float. Sedangkan Nama veriabel merupakan nama variabel pointer.
Contoh penggunaan pointer dalam program C++:
Void main()
{
int x,y,*z;
x = 75; //nilai x = 75
y = x; //nilai y diambil dari nilai x
z = &x; //nilai z menunjuk kealamat pointer dari nilai x
getch();
}
LINKED LIST (LINKED LIST)
Salah satu Struktur Data Dinamis yang paling sederhana adalah Linked List atau Struktur Berkait atau Senarai Berantai, yaitu suatu kumpulan komponen yang disusun secara berurutan dengan bantuan Pointer.
Linked List (Senarai Berantai) disebut juga dengan Senarai Satu Arah (One-Way List). Masing-masing komponen dinamakan dengan Simpul (Node)
LINKED LIST (LINKED LIST)
Linked List juga mengandung sebuah variable petunjuk list, yang biasanya diberi nama
Start (Awal), yang berisi alamat dari simpul pertama dalam list.
PENYAJIAN LINKED LIST DALAM MEMORI
Bentuk Node Single Linked List non Circular
Single : field pointer-nya hanya satu dan satu arah,pada akhir node pointernya menunjuk NULL
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.
Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Pembuatan Single Linked List non Circular
Deklarasi Node :
typedef struct TNode{
int data;
TNode *next;
};
Keterangan :Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode.
Fungsi Inisialisasi Single Linked List
void init()
{
head = NULL;
}
Function untuk mengetahui kondisi Single Linked List
Jika pointer head tidak menunjuk pada suatu node maka kosong
int isEmpty()
{
if (head == NULL) return 1;
else return 0;
}
Menambah Node di Depan
- Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara: node head ditunjukkan ke node baru tersebut.
- Prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.
Menambah Node di Depan dengan C++
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”);
}
Menambah Node di Belakang
- Penambahan data dilakukan di belakang, namun pada saat pertama kali, node langsung ditunjuk oleh head.
- Penambahan di belakang membutuhkan pointer bantu untuk mengetahui node terbelakang. Kemudian, dikaitkan dengan node baru.
- Untuk mengetahui data terbelakang perlu digunakan perulangan.
Menambahan node dibelakang dengan C++
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“);
}
Menghapus Node di Depan
- Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain (hapus) yang digunakan untuk menunjuk node yang akan dihapus, barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete.
- Sebelum data terdepan dihapus, terlebih dahulu head harus menunjuk ke node berikutnya agar list tidak putus, sehingga node setelah head lama akan menjadi head baru
- Jika head masih NULL maka berarti data masih kosong!
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";
}
Menghapus Node di Belakang
- Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, pointer bantu untuk menunjuk node sebelum node yang dihapus yang akan menjadi node terakhir.
- Pointer bantu digunakan untuk menunjuk ke nilai NULL. Pointer bantu selalu bergerak sampai sebelum node yang akan dihapus, kemudian pointer hapus diletakkan setelah pointer bantu. Selanjutnya pointer hapus akan dihapus, pointer bantu akan menunjuk ke NULL.
Menghapus node dibelakang dengan C++
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“);
}
Single Linked List non Circular Menggunakan Head dan Tail
- Dibutuhkan dua variabel pointer : head dan tail
- Head selalu menunjuk pada node pertama, sedangkan tail selalu menunjuk pada node terakhir.
- Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.
Menggunakan Head dan Tail
Inisialisasi Linked List
TNode *head, *tail;
Fungsi Inisialisasi Linked List
void init(){
head = NULL;
tail = NULL;
}
Function untuk mengetahui kondisi LinkedList kosong / tidak
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
Menambah Node di Depan Dengan Head dan Tail
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=tail=baru;
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}
Menambah Node di Belakang Dengan Head dan Tail
void tambahBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
printf("Data masuk\n“);
}
Menghapus Node di Depan (Dengan Head dan Tail)
void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head!=tail){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = tail->data;
head=tail=NULL;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
Menghapus Node di Belakang (Dengan Head dan Tail)
void hapusBelakang(){
TNode *bantu,*hapus;
int d;
if (isEmpty()==0){
bantu = head;
if(head!=tail){
while(bantu->next!=tail){
bantu = bantu->next;
}
hapus = tail;
tail=bantu;
d = hapus->data;
delete hapus;
tail->next = NULL;
}else {
d = tail->data;
head=tail=NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
Penggambaran untuk menambah dan menghapus node di posisi tengah pada :
- Single Linked List dengan Head
- Single Linked List dengan Head & Trail
SINGLE LINKED DENGAN HEAD
# include <iostream.h>
# include <iostream.h>
# include <conio.h>
struct TNode{
char data[15];
TNode *next;
};
TNode *head;
int opsi = 0;
void init(){
head = NULL;
}
bool isEmpty(){
if (head ==NULL) return true;
else return false;
}
void tambahdepan(){
TNode *baru;
baru = new TNode;
cout << "Masukkan DATA: ";
cin >> baru-> data;
baru->next = NULL;
clrscr();
if(isEmpty()==true){
head=baru;
head->next = NULL;
}else {
baru->next = head;
head = baru;
}
}
void tambahbelakang(){
TNode *baru,*bantu;
baru = new TNode;
cout << "Masukkan DATA: ";
cin >> baru-> data;
baru->next = NULL;
clrscr();
if(isEmpty()== true){
head=baru;
head->next = NULL;
} else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
}
void tambahtengah(){
TNode *baru, *bantu;
int posisiSisip;
if(isEmpty()== false){
cout<<"Akan disisip setelah Data Ke ? : "; cin>>posisiSisip;
bantu=head;
baru=new TNode;
for(int i=1;i<posisiSisip;i++){
if(bantu->next!=NULL)
bantu=bantu->next;
else break;
}
cout << "Masukkan DATA: ";
cin >> baru-> data;
baru->next=bantu->next;
bantu->next=baru;
clrscr();
}
else cout<<"Mau sisip tengah Belum ada data !! …silahkan masukkan Data dula aja…..";
}
void hapusdepan() {
TNode *hapus;
if (isEmpty() == false){
if(head->next !=NULL){
hapus = head;
head = head->next;
delete hapus;
clrscr();
} else {
head = NULL;
}
}else {
cout<<"Data anda masih kosong !!!!\n";
}
}
void hapusbelakang(){
TNode *hapus, *bantu;
if (isEmpty()==false){
if(head->next !=NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
bantu->next = NULL;
delete hapus;
clrscr();
} else {
head = NULL;
}
} else {
cout<<"Data anda masih kosong !!!!\n";
}
}
void hapustengah(){
int banyakdata,posisiSisip,poshapus;
TNode *hapus, *bantu;
if(isEmpty()== false){
cout<<" Akan dihapus pada data ke : "; cin>>posisiSisip;
banyakdata=1;
bantu=head;
while(bantu->next!=NULL)
{
bantu=bantu->next;
banyakdata++;
}
if((posisiSisip<1)||(posisiSisip>banyakdata)){
cout<<"Belum ada data !! …silahkan masukkan Data dula aja…..\n";
}else {
bantu=head;
poshapus=1;
while(poshapus<(posisiSisip-1))
{
bantu=bantu->next;
poshapus++;
}
hapus=bantu->next;
bantu->next=hapus->next;
delete hapus;
clrscr();
}
}
else cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";
}
void display(){
clrscr();
TNode *bantu;
bantu = head;
if(isEmpty()==true){
cout<<"Data masih kosong\n";
} else {
cout<<endl<<"DATA LINKED LIST\n";
while(bantu!=NULL){
cout<<"--------------- "<<endl;
cout<<"DATA: " << bantu->data << " ";
cout<<endl;
bantu=bantu->next;
cout<<"--------------- "<<endl;
}
cout<<endl;
}
}
void main(){
int();
do{
cout<<endl;
cout<<endl;
cout<<endl;
cout<<"-:: MENU PILIHAN::-"<<endl;
cout<<endl;
cout<<"1. Tambah Simpul dari Depan."<<endl;
cout<<"2. Tambah Simpul dari Belakang."<<endl;
cout<<"3. Tambah Simpul dari Tengah."<<endl;
cout<<"4. Hapus Simpul dari Depan."<<endl;
cout<<"5. Hapus Simpul dari Belakang."<<endl;
cout<<"6. Hapus Simpul dari Tengah."<<endl;
cout<<"7. Tampil Data."<<endl;
cout<<"8. Keluar."<<endl;
cout<<endl;
cout<< "Pilihan Menu : ";
cin >> opsi;
switch(opsi){
case 1 : tambahdepan();break;
case 2 : tambahbelakang();break;
case 3 : tambahtengah();break;
case 4 : hapusdepan();break;
case 5 : hapusbelakang();break;
case 6 : hapustengah();break;
case 7 : display();break;
}
}while (opsi != 8);
}
Tampilan menu setelah di Run :
Pilih menu no 1 untuk menambah node depan :
Pilih menu no 2 untuk menambah node belakang :
Pilih menu no 3 untuk menambah node di tengah :
Tampilan setelah penambahan node di tengah :
Pilih no 6 untuk menghapus node di tengah :
Tampilan setelah di hapus node di tengah :
Single linked list merupakan suatu linked list yang hanya memiliki suatu variable pointer saja. Dimana
pointer tersebut menujukan ke kode selanjutnya. Biasanya field pada tail menuju ke null.
//drive.google.com/uc?export=download&id=0B_lb_P3Nsd8SaUZqeDR5a0o5dFU
Contoh gambar menambah node dengan hide di posisi tengah ://drive.google.com/uc?export=download&id=0B_lb_P3Nsd8SZFFDaVoyei05YkU
Contoh gambar menghapus node dengan head di posisi tengah ://drive.google.com/uc?export=download&id=0B_lb_P3Nsd8SNDE2cW15NG4xZGM
Contoh gambar menambah node head dan tail di posisi tengah ://drive.google.com/uc?export=download&id=0B_lb_P3Nsd8SSHhZRkZaVkpYd1U
Contoh gambar menambah node head dan tail di posisi tengah 2 ://drive.google.com/uc?export=download&id=0B_lb_P3Nsd8SVG5rVVJLOHJ6SEU
Contoh gambar menghapus node head dan tail di posisi tengah ://drive.google.com/uc?export=download&id=0B_lb_P3Nsd8STmFjTUxlVUhuOEU