25 Juli 2009

Linked List

25 Juli 2009
Dasar Teori
Array merupakan variable yang bersifat statis (ukuran dan urutannya sudah pasti).
Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut
sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah
di atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis,
variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan
dapat direlokasikan kembali. Setiap ingin menambahkan data, Anda selalu menggunakan
variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer.
Oleh karena itu, ada baiknya jika Anda hanya menggunakan satu variabel pointer saja
untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list
adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang
setiap elemennya terdiri dari dua bagian.
Linked adalah koleksi obyek heterogen dengan sifat setiap obyek (kecuali obyek
terakhir) mempunyai penerus dan setiap obyek (kecuali obyek pertama) mempunyai
pendahulu. Salah satu penggunaan pointer adalah untuk membuat linked list atau senarai
berantai. Linked list sendiri dapat diartikan sebagai sekumpulan komponen yang saling
berhubungan (berantai) dengan bantuan pointer. Perhatikan ilustrasi berikut untuk lebih
jelasnya.



Masing-masing komponen disebut sebagai simpul atau node. Setiap simpul terbagi
menjadi dua bagian, yaitu bagian data dan bagian penyambung. Bagian data berisi data
yang akan disimpan dan diolah. Sedangkan bagian penyambung berisi alamat simpul
berikutnya.


Inti dari linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan
bagaimana rnenyambungkan antar gerbong / node tersebut.


ARRAY VS LINKED LIST



PEMBUATAN SINGLE LINKED LIST

Deklarasi node
Dibuat dari struct berikut ini:



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 haed yang bertipe pointer dari TNode
yang berguna sebagai kepala linked list.

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi
memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL



SINGLE LINKED LIST MENGGUNAKAN HEAD
- Dibutuhkan satu buah variabel pointer: head
- Head akan selalu menunjuk pada node pertama



Deklarasi Pointer Penunjuk Kepala Single Linked List Manipulasi linked list tidak bisa
dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer
penunjuk ke node pertama dalam linked list (dalam hal ini adalah head). Deklarasinya
sebagai berikut:

TNode *head;



Function untuk mengetahui kosong tidaknya Single LinkedList Jika pointer head tidak
menunjuk pada suatu node maka kosong




PENAMBAHAN DATA
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 dengan cara head
ditunjukkan ke node baru tersebut. Pada prinsipnya adalah mengkaitkan node baru
dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan
tetap selalu menjadi data terdepan



ilustrasi:





MENAMPILKAN DATA
Function untuk menampilkan isi single linked list (non circular)




- Function di atas digunakan untuk menampilkan semua isi list, di mana linked list
ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini
dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya
pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.
- Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai
NULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya
dan membaca isi datanya dengan menggunakan field next sehingga dapat saling
berkait.
- Jika head masih NULL berarti data masih kosong!

PENGHAPUSAN DATA
Function untuk menghapus data terdepan




Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada
linked list
- Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh
pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan
untuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulah
kemudian menghapus pointer hapus dengan menggunakan perintah delete.
- Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya
terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan
menjadi head baru (data terdepan yang baru).
- Jika head masih NULL maka berarti data masih kosong!

contoh Program Lengkap:

#include <conio.h>
#include <iostream.h>

struct TNode
{
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<<"Data Masuk\n";
}

void tampil()
{
TNode *bantu;
bantu=head;
if(isempty()==0)
{
while (bantu!=NULL)
{
cout<<bantu->data<<" ";
bantu=bantu->next;
}
cout<<endl;
}
else cout<<"Masih kosong\n";
}

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<<d<<" terhapus\n";
}
else cout<<"masih kosong\n";
}

void main()
{
int pil;
int databaru;
do
{
clrscr();
cout<<"linked List"<<endl;
cout<<"1.Insert Depan"<<endl;
cout<<"2.Tampil"<<endl;
cout<<"3.Hapus"<<endl;
cout<<"4.Exit"<<endl;
cout<<"pilihn anda= ";cin>>pil;
switch(pil)
{
{
case 1:
cout<<endl;
cout<<"data: ";cin>>databaru;
insertdepan (databaru);
break;
}
{
case 2:
cout<<endl;
tampil();
break;
}
{
case 3:
cout<<endl;
hapusdepan();
break;
}
}
getch();
}while (pil!=4);
}

15 comments:

alf1ansy4h mengatakan...

:g:
Mantab gan..
Siiiip.....

Anonim mengatakan...

:a:

arimurti mengatakan...

mantap gan !! thx yahh,...sangat2 membantu untuk memahami linked list ^_^

Anonim mengatakan...

kalo misalnya datanya berupa char, dan maw diisi lebih dari 1 abjad, gimana caranya?

Nightmare mengatakan...

8. Operasi pada pointer
/*
pointer 8 : operasi pada pointer
*/

//lib
#include
#include

//main function
int main()
{
char D[] = "hello world";
char *ptr_d;

//cara 1
ptr_d = D;

//cara 2
//ptr_d = &D[0];
printf("Tes 1:\n");
for(int i = 0; i < sizeof(D); i++)
{
printf("%c",*ptr_d);
ptr_d++;
}
printf("\n\n");

//coba ini
printf("Tes 2:\n");
for(int i = 0; i < sizeof(D); i++)
{
printf("%c",*ptr_d);
ptr_d++;
}
printf("\n\n");

//coba ini juga
printf("Tes 3:\n");
ptr_d--;
for(int i = 0; i < sizeof(D); i++)
{
printf("%c",*ptr_d);
ptr_d--;
}
printf("\n\n");

//dan ini
printf("Tes 4:\n");
ptr_d = D;
for(int i = 0; i < sizeof(D); i++)
{
printf("%c",*ptr_d);
ptr_d++;
}
printf("\n");

getch();
return 0;
}

1. Pada percobaan 8, data yang ditampilkan menjadi tidak sesuai dengan data aslinya. Mengapa demikian? Jelaskan sesuai dengan jalannya program!

bro tolong gw lagi ya...
ini tugas dari kULl...
yang kmren2 itu mantep broo..
gw minta tolong lagi ya...
cari in solusi ny....

Anonim mengatakan...

http://www.google.co.id/url?sa=t&source=web&cd=19&ved=0CEgQFjAIOAo&url=http%3A%2F%2Fjamilah.staff.gunadarma.ac.id%2FDownloads%2Ffiles%2F21768%2FPOINTER-M11.doc&ei=DPzJTdvKI8vhrAfv9NmSBQ&usg=AFQjCNEHhu34qUg08qbjznA3aNKJ6mEohg

SHadow mengatakan...

Buatlah program menggunakan double linked list circular untuk menyimpan dan
menampilkan data berikut dari data ke-3 dengan urutan terbalik :
1. Janu
2. Dadu
3. Ayu
4. Kiki
5. Budi
ada yang tau gan...????
mohong bimbingan

Opie Eyek mengatakan...

ane kaga terlalu ngerti maksutnyya gan... tapi ane kasi refrensi

http://www.snippets.24bytes.com/2010/06/double-linked-list.html

http://farid238.blogspot.com/2011/04/linked-list.html

http://syamsmobillex.blogspot.com/2011/01/program-double-linked-list-non-circular.html

SHadow mengatakan...

gan coba lo liat soal di sini:
https://simponi.mdp.ac.id/materi/SP244/111061/SP244-111061-939-21.pdf

lo ngerti gak maksut nya....????
terus bisa buat in gak contoh program ny...
tq sblum nya

miftahalfian mengatakan...

mantab....

JadiGitu mengatakan...

empurna.. makasih banyak yaa ilmunya mastah.. ane pelajari dulu. kebtulan masih bingung nih

Asalasah mengatakan...

wah mantap..makasih banayak bos :D

Anonim mengatakan...

gan saya ada tugas linked dan bst...
mis ada 1 doc text berisi kata(saya,main,kerja,tidur,nonton....).jadi saya disuruh urutkan kata tersebut dengan bst dan jumlah frekuency kata yang muncul tersebut disimpan dalam linked list.hasil nya seperti ini:

kata frekuency
saya 2
main 1
kerja 3
mohon bantuannya....

Anonim mengatakan...

:a:mau tanya dong kalau queue linkedlist itu gimana ya?penerapanya disintax

Anonim mengatakan...

ajaran ane belajar ini dong,,


kayaknya ribet banget yeee,,

di kampus belajar ga pernah mudeng :'(

Poskan Komentar

sampaikan komentar dengan sopan dan bertanggung jawab :)