Linked List

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
#include

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<data<<" ";
bantu=bantu->next;
}
cout<}
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<}
else cout<<"masih kosong\n";
}

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