Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling bersambungan, dinamis adalah senarai berkait (linked list).Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data.
Gambar sebuah node:
1]. Bagian pertama, disebut medan informasi, berisi informasi yang akan disimpan dan diolah.
2]. Bagian kedua, disebut medan penyambung (link field), berisi alamat simpul berikutnya.
Pada gambar di atas, pointer awal menunjuk ke simpul pertama dari senerai tersebut. Medan penyambung (pointer) dari suatu simpul yang tidak menunjuk simpul lain disebut pointer kosong, yang nilainya dinyatakan sebagai null (null adalah kata baku yang berarti bahwa pointer 0 atau bilangan negatif). Jadi kita bisa melihat bahwa dengan hanya sebuah pointer Awal saja maka kita bisa membaca semua informasi yang tersimpan dalam senerai.
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuanpointer. Dikatakansingle linked apabila hanya ada satu pointer yangmenghubungkan setiap node.singleartinya field pointernya hanya satu buah saja dan satu arah.
Senarai berkait adalah struktur data yang paling dasar. Senarai berkait terdiri atas sejumlah unsur-unsur dikelompokkan, atau terhubung, bersama-sama di suatu deret yang spesifik. Senarai berkait bermanfaat di dalam memelihara koleksi-koleksi data, yang serupa dengan array/larik yang sering digunakan. Bagaimanapun juga, senarai berkait memberikan keuntungan-keuntungan penting yang melebihi array/larik dalam banyak hal. Secara rinci, senarai berkait lebih efisien di dalam melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan.
Senarai berkait juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan yang dialokasikan pada runtime. Karena di dalam banyak aplikasi, ukuran dari data itu tidak diketahui pada saat kompile, hal ini bisa merupakan suatu atributyang baik juga. Setiapnodeakan berbentuk struct dan memiliki satu buahfield bertipe structyang sama, yang berfungsi sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan cara first-createfirst-access ataupun first-create-last-access. Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama next, yang bertipe struct node. Hal ini sekilas dapat membingungkan. Namun, satu hal yang jelas, variabel next ini akan menghubungkan kita dengan node di sebelah kita, yang juga bertipe struct node.Hal inilah yang menyebabkan next harus bertipe struct node.
Deklarasi Node
struct node {
char nama[20];
int umur;
float tinggi;
node *next; // Pointer menyambung ke node selanjutnya
};
Pembahasan lebih rinci mengenai bagian-bagian program utuh di bawah ini dapat Anda simak di sini:
- Cara Menambah Simpul
- Cara Menghapus Simpul
- Cara Menampilkan Simpul (dapat Anda simak di sini).
3. Menampilkan List Simpul
Sebelum menampilkan linked list perlu kita uji apakah senarai kosong atau tidak. Jika senarai kosong kita tampilkan pesan bahwa List kosong. Jika senarai tidak kosong maka kita baca senarai mulai posisi awal sampai simpul terakhir.
node *temp;
temp = awal_ptr;
cout << endl;
if (temp == NULL)
cout << "List kosong!" << endl;
else
{
while (temp != NULL)
{
// Menampilkan isi
cout << "Nama : " << temp->nama << " ";
cout << "Umur : " << temp->umur << " ";
cout << "Tinggi : " << temp->tinggi;
if (temp == posisi)
cout << " <-- Posisi node";
cout << endl;
temp = temp->next;
}
cout << "Akhir list!" << endl;
}
Program Lengkap 1
#include <iostream.h>
struct node
{
char nama[20];
int umur;
float tinggi;
node *next;
};
node *awal_ptr=NULL;
node *posisi;
int pilih;
void tambah_simpul_akhir()
{
node *temp, *temp2; //simpul sementara
//isi data
temp=new node;
cout<<"Nama : ";cin>>temp->nama;
cout<<"Umur : ";cin>>temp->umur;
cout<<"Tinggi : ";cin>>temp->tinggi;
temp->next=NULL;
//inisialisasi pointer ketika kosong
if(awal_ptr==NULL)
{
awal_ptr=temp;
posisi=awal_ptr;
}
else
{
temp2=awal_ptr;
while(temp2->next != NULL)
{
temp2 = temp2->next;
}
temp2->next=temp;
}
}
void tampil_senarai()
{
node *temp;
temp = awal_ptr;
if(temp == NULL)
cout<<"List kosong"<<endl;
else
{
cout<<endl<<endl;
while(temp != NULL)
{
cout<<"Nama : "<<temp->nama<<" ";
cout<<"Umur : "<<temp->umur<<" ";
cout<<"Tinggi : "<<temp->tinggi;
if (temp == posisi)
cout<<" << posisi simpul";
cout<<endl;
temp=temp->next;
}
cout<<"Akhir list"<<endl;
}
}
void hapus_simpul_akhir()
{
node *temp1, *temp2;
if (awal_ptr == NULL)
cout << "List kosong!" << endl;
else
{
temp1 = awal_ptr;
if (temp1->next == NULL)
{
delete temp1;
awal_ptr = NULL;
}
else
{
while (temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL;
}
}
}
void hapus_simpul_awal()
{
node *temp;
temp = awal_ptr;
awal_ptr = awal_ptr->next;
delete temp;
}
void main()
{
awal_ptr=NULL;
do
{
tampil_senarai();
cout<<"Menu Pilihan"<<endl;
cout<<"0. Keluar program"<<endl;
cout<<"1. Tambah simpul akhir"<<endl;
cout<<"2. Hapus simpul akhir"<<endl;
cout<<"3. Hapus simpul awal"<<endl;
cout<<"Pilihan >> ";cin>>pilih;
switch(pilih)
{
case 1: tambah_simpul_akhir();break;
case 2: hapus_simpul_akhir();break;
case 3: hapus_simpul_awal();break;
}
}while(pilih !=0);
}
Program Lengkap 2
#include <iostream.h>
#include <conio.h>
struct node
{ char nama[20];
int umur;
float tinggi;
node *next;
};
node *awal_ptr = NULL;
node *posisi; //digunakan untuk membaca sepanjang list
int option = 0;
void tambah_awal_list()
{
node *baru;
baru = new node;
cout << "Masukkan Nama : ";
cin >> baru->nama;
cout << "Masukkan Umur : ";
cin >> baru->umur;
cout << "Masukkan tingggi : ";
cin >> baru->tinggi;
baru->next = NULL;
if(awal_ptr == NULL)
{
awal_ptr=baru;
awal_ptr->next = NULL;
}
else
{
baru->next = awal_ptr;
awal_ptr = baru;
}
}
void menambah_node_di_akhir()
{ node *temp, *temp2; // Temporary pointers
// menciptakan node baru
temp = new node;
cout << "Masukkan Nama : ";
cin >> temp->nama;
cout << "Masukkan Umur : ";
cin >> temp->umur;
cout << "Masukkan tingggi : ";
cin >> temp->tinggi;
temp->next = NULL;
// Set up link pada node
if (awal_ptr == NULL)
{ awal_ptr = temp;
posisi = awal_ptr;
}
else
{ temp2 = awal_ptr;
// node tidak NULL -- list tidak kosong
while (temp2->next != NULL)
{ temp2 = temp2->next;
// Memindahkan pada next link dalam rantai
}
temp2->next = temp;
}
}
void display_list()
{ node *temp;
temp = awal_ptr;
cout << endl;
if (temp == NULL)
cout << "List kosong!" << endl;
else
{ while (temp != NULL)
{ // Menampilkan detail data
cout << "nama : " << temp->nama << " ";
cout << "umur : " << temp->umur << " ";
cout << "tinggi : " << temp->tinggi;
if (temp == posisi)
cout << " <<<< posisi node";
cout << endl;
temp = temp->next;
}
cout << "Akhir list!" << endl;
}
}
void hapus_awal_node()
{ node *temp;
temp = awal_ptr;
awal_ptr = awal_ptr->next;
delete temp;
}
void hapus_akhir_node()
{ node *temp1, *temp2;
if (awal_ptr == NULL)
cout << "List kosong!" << endl;
else
{ temp1 = awal_ptr;
if (temp1->next == NULL)
{ delete temp1;
awal_ptr = NULL;
}
else
{ while (temp1->next != NULL)
{ temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL;
}
}
}
void pindah_posisi_sebelumnya()
{ if (posisi->next == NULL)
cout << "Kamu berada pada akhir list." << endl;
else
posisi = posisi->next;
}
void pindah_posisi_berikutnya()
{ if (posisi == awal_ptr)
cout << "Kamu berada pada awal list" << endl;
else
{ node *previous; // deklarasi pointer
previous = awal_ptr;
while (previous->next != posisi)
{ previous = previous->next;
}
posisi = previous;
}
}
void tambah_tengah_list()
{
node *baru, *bantu;
int posisi_sisip;
if(awal_ptr != NULL)
{
cout<<"Akan disisip setelah Data Ke ? : "; cin>>posisi_sisip;
bantu=awal_ptr;
baru =new node;
for(int i=1;i<posisi_sisip-1;i++)
{
if(bantu->next != NULL)
bantu=bantu->next;
else
break;
}
cout << "Masukkan Nama : ";
cin >> baru->nama;
cout << "Masukkan Umur : ";
cin >> baru->umur;
cout << "Masukkan tingggi : ";
cin >> baru->tinggi;
baru->next=bantu->next;
bantu->next=baru;
}
else
{ cout<<"Belum ada data !! silahkan isi data dulu....";
getch();}
}
void Hapus_tengah_list()
{
int banyakdata,posisi_hapus,poshapus;
node *hapus, *bantu;
if(awal_ptr != NULL)
{
cout<<" Akan dihapus pada data ke : "; cin>>posisi_hapus;
banyakdata=1;
bantu=awal_ptr;
while(bantu->next != NULL)
{
bantu=bantu->next;
banyakdata++;
}
if((posisi_hapus<1)||(posisi_hapus>banyakdata))
{
cout<<"Belum ada data !! masukkan Data dula aja...\n";
}
else
{
bantu=awal_ptr;
poshapus=1;
while(poshapus<(posisi_hapus-1))
{
bantu=bantu->next;
poshapus++;
}
hapus=bantu->next;
bantu->next=hapus->next;
delete hapus;
}
}
else cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";
getch();
}
int main()
{ awal_ptr = NULL;
do
{
clrscr();
display_list();
cout << endl;
cout << "MENU PILIHAN : " << endl;
cout << "0. Keluar program." << endl;
cout << "1. Tambah awal list." << endl;
cout << "2. Tambah akhir list." << endl;
cout << "3. Tambah tengah list."<< endl;
cout << "4. Hapus awal list." << endl;
cout << "5. Hapus akhir list." << endl;
cout << "6. Hapus tengah list." << endl;
cout << "7. Pindah posisi pointer ke berikutnya." << endl;
cout << "8. Pindah posisi pointer ke sebelumnya." << endl;
cout << endl << " Pilihan >> ";
cin >> option;
switch (option)
{
case 1 : tambah_awal_list();break;
case 2 : menambah_node_di_akhir(); break;
case 3 : tambah_tengah_list();break;
case 4 : hapus_awal_node(); break;
case 5 : hapus_akhir_node(); break;
case 6 : Hapus_tengah_list();break;
case 7 : pindah_posisi_sebelumnya(); break;
case 8 : pindah_posisi_berikutnya();
}
}
while (option != 0);
}
Sumber
Mata kuliah Struktur Data. STMIK EL Rahma Yogyakarta.
Disusun oleh Eko Riswanto
