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