Post on 24-Aug-2019
Pertemuan 12:
INF202: Struktur Data
LINKED LIST (Senarai
Berantai)
Dosen: Wayan Suparta, PhD
1. Dasar Teori
Linked List merupakan deretan elemen yang
berdampingan di memori namun masih terpencar-pencar.
Untuk mengakses semua elemen digunakan pointer
tunggal.
Masing-masing elemen terdiri dari dua bagian, yaitu
sebuah data dan sebuah pointer yang disebut dengan
pointer next.
Dengan menggunakan struktur two-member seperti ini,
linked list dibentuk dengan cara menunjuk pointer next
suatu elemen ke elemen yang mengikutinya. Pointer next
pada elemen terakhir merupakan NULL, yang
menunjukkan akhir dari suatu list.
Elemen pada awal suatu list disebut head, dan elemen
terakhir dari suatu list disebut tail.
Ketika sebuah variabel dideklarasikan, terlebih dahulu
harus diinisialisasi termasuk juga ’pengalokasian secara
dinamis’.
Fungsi untuk mengalokasikan sebuah node baru: fungsi
allocate_node() menggunakan malloc() untuk
mendapatkan memori aktual, yang akan menginisialisasi
suatu field data.
next selalu diinisialisasi sebagai NULL.
Untuk melihat kemungkinan alokasi memori gagal, maka
fungsi allocate_node menghasilkan 0, sebaliknya 1 jika
berhasil.
Untuk membebaskan node digunakan fungsi free_node.
Fungsi dari alokasi node adalah sebagai berikut :
Inisialisasi LIST setelah alokasi untuk node pertama sebagai
berikut:
Fungsi free_node() akan menghancurkan node yang
menunjuk ke pointer yang dilewati karena itu pointer
didefinsikan dengan NULL:
2. Operasi Pada Linked List
Opearsi penting pada Linked List:
Insert
Delete
Fungsi INSERT meliputi
insert sebagai node awal (head) dari linked list
insert setelah node tertentu
insert sebelum node tertentu
insert sebagai node akhir (tail) dari linked list.
Fungsi DELETE meliputi
delete sebagai simpul pertama(head) dari linked list
delete setelah simpul tertentu
delete simpul terakhir
(a) Insert sebagai node awal (head) dari linked list
(b) Insert setelah node tertentu
(c) Insert sebelum node tertentu
Statement untuk insert setelah node tertentu dari linked list adalah
(d) Insert di akhir (tail) dari linked list
do
(2) Fungsi DELETE
(a)
Langkah
penghapusan
1. Pointer first
diarahkan data
ke-2
2. Pointer p
diarahkan pada
data ke-1
3. Bebaskan
pointer p
(secara otomatis
data ke-1
terhapus)
(b)
(c)
Langkah-langkah untuk proses di atas adalah sebagai berikut:
1. Telusuri simpul s/d first->next = NULL
2. Arahkan pointer p ke first
3. Bebaskan pointer p->next (Simpul Terakhir)
4. Arahkan p->next ke NULL
3. MERUBAH ISI DARI SUATU SIMPUL PADA
LINKED LIST
1. Menulusuri linked list sampai didapatkan simpul yang akan dirubah.
Contoh KASUS Polinomial
Pertimbangkan dua polinomial f(x) dan g(x), yang dapat diwakili
menggunakan linked list.
h (x) dapat direpresentasikan dengan h(x)= f(x)+ g(x)=
f(x) = ax3 + bx + c dan g(x) = mx4 + nx3 + ox2 + px + q
Yaitu menambahkan konstanta dari polynomial yang sesuai dari
eksponensial sama.
Kedua polinomial dapat ditambahkan dengan:
h(x)= f(x)+ g(x)= mx4 + (a + n) x3 + ox 2 + (b + p)x + (c + q)
yaitu menambahkan konstanta dari polinomial yang sesuai dari
eksponensial sama.
Hasil dari H(x) dapat dijabarkan seperti gambar berikut:
Contoh Program 1:
Menambah data di depan dan di akhir
//Program linked list for Node Insert Kiri dan Insert Kanan #include <iostream> #include <cstdlib> #include <stdlib.h> #include <conio.h> using namespace std; struct node { int urut; node *next; }; node *awal_ptr = NULL; node *posisi; //digunakan untuk membaca sepanjang list int option = 0;
//Tambah data di depan void tambah_awal_list() { node *baru; baru = new node; cout << "Masukkan Data : "; cin >> baru->urut; baru->next = NULL; if(awal_ptr == NULL) { awal_ptr=baru; awal_ptr->next = NULL; } else { baru->next = awal_ptr; awal_ptr = baru; } }
//Tambah data di akhir
void menambah_node_di_akhir()
{
node *temp, *temp2; // Temporary pointers
// menciptakan node baru
temp = new node;
cout << "Masukkan urut : ";
cin >> temp->urut;
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; }
}
//Menampilkan data
void display_list()
{
node *temp;
temp = awal_ptr;
cout << endl;
cout << "DATA [";
if (temp == NULL)
cout << "List kosong!" << endl;
else
{
while (temp != NULL)
{ // Menampilkan detail data
cout << "" << temp->urut <<
",";
if (temp == posisi)
cout << " <<<< posisi node";
// cout << endl;
temp = temp->next; }
cout << "] ";
cout << "Akhir list!" << endl;
}
}
//Inisialisasi Nilai
int init(int nilai){
node *baru;
baru = new node;
baru->urut=nilai;
baru->next = NULL;
if(awal_ptr == NULL)
{
awal_ptr=baru;
awal_ptr->next = NULL;
}
else
{
baru->next = awal_ptr;
awal_ptr = baru;
}
}
//Program Utama
int main()
{
cout << "===================" << endl;
cout << "STRUKTUR DATA - LINKED LIST"
<< endl;
cout << "===================" << endl;
awal_ptr = NULL;
init(10); //data kanan
init(12);
init(5);
init(7);
init(22); //data kiri
do {
// clrscr();
display_list();
cout << endl;
cout << "MENU PILIHAN : " << endl;
cout << "1. Tambah Sebelah Kiri" << endl;
cout << "2. Tambah Sebelah Kanan" <<
endl;
cout << "3. EXIT" << endl;
cout << endl << " Pilihan >> ";
cin >> option;
switch (option)
{
case 1 : tambah_awal_list();
break;
case 2 : menambah_node_di_akhir();
break;
}
}
while (option != 3);
}
Output Program:
Tambah data kiri: Tambah data kanan:
Contoh Program 2: Fungsi lainnya
//Hapus data di depan
void hapus_awal_node()
{
node *temp;
temp = awal_ptr;
awal_ptr = awal_ptr->next;
delete temp;
}
//Hapus data di akhir
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;
}
}
}
//Pindah pointer ke posisi sebelumnya
void pindah_posisi_sebelumnya()
{
if (posisi->next == NULL)
cout << “Pointer berada di akhir list" << endl;
else
posisi = posisi->next;
}
//Pindah pointer ke posisi berikutnya
void pindah_posisi_berikutnya()
{
if (posisi == awal_ptr)
cout << “Pointer berada pada awal list" <<
endl;
else
{
node *previous; // deklarasi pointer
previous = awal_ptr;
while (previous->next != posisi)
{ previous = previous->next; }
posisi = previous; }
}
//Tambah data di tengah
void tambah_tengah_list()
{ node *baru, *bantu;
int posisi_sisip;
if(awal_ptr != NULL) {
cout<<"Akan diinsert setelah Data
Ke ? ";
cin>>posisi_sisip;
baru =new node;
bantu=awal_ptr;
for(int i=1;i<posisi_sisip-1;i++) {
if(bantu->next != NULL)
bantu=bantu->next;
else
break; }
cout << "Masukkan urut : ";
cin >> baru -> urut;
baru->next = bantu -> next;
bantu->next=baru; }
else
{ cout<<"Belum ada data !! silahkan
isi data dulu....";
getch(); } }
//Hapus data di posisi tengah
void Hapus_tengah_list()
{
int bykdata,posisi_hapus,poshapus;
node *hapus, *bantu;
if(awal_ptr != NULL)
{
cout<<" Akan dihapus pada data ke : ";
cin>>posisi_hapus;
bykdata=1;
bantu=awal_ptr;
while(bantu->next != NULL)
{
bantu=bantu->next;
bykdata++;
}
if((posisi_hapus<1)||(posisi_hapus>bykdata))
{
cout<<"Belum ada data !! Boleh
memasukkan data.\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 menghapus data dari tengah! ";
getch();
}
//Program Utama Lengkap
display_list();
cout << endl;
cout << "MENU PILIHAN: " << endl;
cout << "1. Tambah data di awal" << endl;
cout << "2. Tambah data di akhir." << endl;
cout << "3. Tambah data di tengah."<< endl;
cout << "4. Hapus data di awal" << endl;
cout << "5. Hapus data di akhir" << endl;
cout << "6. Hapus data di tengah" << endl;
cout << "7. Pindah posisi pointer ke
berikutnya" << endl;
cout << "8. Pindah posisi pointer ke
sebelumnya" << endl;
cout << "9. EXIT" << 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 != 9);
}
LATIHAN 18 A. Diketahui:
P1 = 6x8 + 8x7 + 5x5 + x3 + 15
P2 = 3x9 + 4x7 + 3x4 + 2x3 + 2x2 + 10
P3 = x2 + 5
Representasikan bilangan polinom dengan menggunakan
linked list dan buatlah prosedur-prosedur untuk :
• Menyisipkan simpul di awal jika pangkat yang dimasukkan
lebih dari pangkat tertinggi dari bilangan polinomial.
• Menyisipkan simpul di tengah jika pangkat dari bilangan yang
kita sisipkan berada di tengah.
• Menyisipkan simpul di akhir jika pangkat dari bilangan yang
disisipkan adalah 0.
• Menghapus simpul, baik di awal, di tengah, ataupun di akhir.
B. Dari contoh program 1 dan 2, gabungkan program tersebut
dengan output proram:
C. Implementasikan sebuah single linked list yang dapat
merepresentasikan data mahasiswa. Data mahasiswa berupa NIM,
Nama, Alamat dan Indeks Prestasi. Buatlah fungsi-fungsi untuk
menelusuri, menambah simpul dan menghapus simpul.
MENU PILIHAN:
1. Tambah data di awal
2. Tambah data di akhir
3. Tambah data di tengah
4. Hapus data di awal
5. Hapus data di akhir
6. Hapus data di tengah
7. EXIT