[Praktikum Algoritma dan Struktur Data] Modul I - Array dan Single Linked List

MODUL  I

ARRAY DAN SINGLE LINKED LIST 

1.1.  TUJUAN

1.    Mahasiswa dapat mengetahui bagaimana mengimplentasikan array dalam program.

2.    Mahasiswa memahami dan mampu membuat single linked list.

3.    Mahasiswa dapat membuat dan menggunakan berbagai operasi – operasi yang terdapat pada linked list.

1.2.  DASAR TEORI

1.    Array

Array atau larik adalah suatu bentuk struktur data yang menampung  satu data yang sejenis (bertipe data sama) yang diwakili oleh satu  nama variabel.

a.    Array Satu Dimensi

Array satu dimensi yaitu array yang terdiri atas satu baris dan banyak kolom. Pendeklarasian suatu array harus diikuti oleh suatu indeks yang menunjukan jumlah maksimum data yang disediakan.

Deklarasi array satu dimensi :

tipe_data nama_var_array [ukuran];

Contoh :

char huruf [9];

 

b.    Array Dua Dimensi

Array dua dimensi yaitu array yang tersusun dari banyak baris dan banyak kolom, dimana indeks pertama menunjukan baris dan indeks kedua menunjukan kolom.

Deklarasi array dua dimensi :

tipe_data nama_var_array [batas_baris] [batas_kolom];

 Contoh :

int b [2][3]= {{2,4,1},{5,3,7}};

 

c.    Array Dinamis

Array dinamis adalah array yang jumlah pemesanan tempat di memori dapat diubah sesuai dengan kebutuhan, sehingga lebih optimal dalam pemanfaatan ruang di memori.

Contoh :

static int dataktp [2] [7] [8] [5]

 

2.    Single Linked list

Sebuah list yang elemennya hanya menyimpan informasi elemen setelahnya (next) dan hanya memiliki 1 pengait ke elemen berikutnya. Sehingga jalannya pengaksesan list hanya dapat dilakukan secara maju dari sebelumnya, maka hanya dapat mengakses elemen berikutnya.

Contoh :

next       a     b     c     d   head                                  data                                                                                                          tail                           NULL

 

Gambar 1.1 Single linked list.

 

3.    Operasi – Operasi yang Ada pada Linked list

a.    Membuat Node Baru

Digunakan keyword “new”. Perintah ini digunakan untuk mempersiapkan sebuah node dengan alokasi memorinya. Selanjutnya medan informasi pada node tersebut diisi dengan data tertentu. Terakhir pointer prev dan next diisi dengan NULL. 

b.    Penyisipan simpul ke Linked list

1)   Insert first (L,N), operasi penyisipan sebagai simpul N sebagai simpul pertama di L.

2)   Insert after (L, N, Prev N), operasi penyisipan simpul N setelah simpul tertentu Prev N.

3)   Insert last (L,N), operasi penyisipan simpul N sebagai simpul terakhir.

4)   Insert before (L,N), operasi penyisipan simpul N sebelum simpul tertentu aft N.

c.    Penghapusan variabel dinamis (simpul suatu Linked list)

1)   Delete first (L), operasi penghapusan simpul pertama dari list L.

2)   Delete last (L), operasi penghapusan simpul terakhir dari list L.

3)   Delete after (L, PrevN), operasi penghapusan setelah simpul tertentu PrevN di last L.

4)   Penghapusan simpul tertentu

·      Delete Node (L,N), operasi penghapusan simpul N dari list L.

·      Delete K Node (L,K), operasi penghapusan simpul dengan key K dari list.

 

1.3.  PERMASALAHAN

1.    Buatlah array satu dimensi dengan input dinamis.

2.    Buatlah singlelinked list

a.    Add front

b.    Add back

c.    Insert (after/before/between)

d.   Delete (front & back)

e.    Delete all

 

1.4.  HASIL DAN PEMBAHASAN

1.    Permasalahan Pertama

a.    Algoritma :

1)   Mulai

2)   Memasukkan jumlah data

3)   Memasukkan data indeks sampai batas jumlah yang sudah dimasukkan

4)   Menampilkan isi array

5)   Selesai

b.    Source Code

#include <iostream> #include <conio>   int main () {    int A[100], n;    cout<<"Masukkan Jumlah Data : "; cin>>n;    for (int i=0;i<n;i++) {       cout<<"A ["<<i<<"] = "; cin>>A[i];    }    cout<<"Menampilkan Hasil : "<<endl;    for (int i=0;i<n;i++) {       cout<<"A ["<<i<<"] = "<<A[i]<<endl;    }    getch ();    return 0; }

c.   Hasil run program

                      Gambar 1.2 Screenshot permasalahan 1

 

2.    Permasalahan Kedua

a.    Algoritma

1)   Deklarasikan nama class.

2)   Deklarasikan private class berisi struct bisa dan kondisi awal tail, head, dan size.

3)   Deklarasikan public class berisi fungsi-fungsi yang akan dipakai diantaranya :

-     Add front

-     Add back

-     Insert After

-     Insert Between

-     Insert Before

-     Delete Front

-     Delete Back

-     Delete All

-     Cetak

4)   Fungsi addfront :

-     Membuat fungsi addfront yang mempunyai tipe data void dan parameter bertipe integer.

-     Mendeklarasikan variabel x sebagai node yang baru.

-     Mendeklarasikan x dot data sama dengan parameter fungsi add front dan x dot next sama dengan NULL.

-     Jika head dan tail sama dengan NULL, maka head dan tail akan bernilai x dan size-nya akan bertambah.

-     Jika sebaliknya maka x dot next sama dengan head dan kemudian head akan berpindah ke x.

5)   Fungsi addback :

-     Membuat fungsi untuk addback.

-     Mendeklarasikan variabel x sebagai node yang baru.

-     Mendeklarasikan x dot data sama dengan parameter fungsi add back dan x dot next sama dengan NULL.

-     Jika head dan tail sama dengan NULL, maka head dan tail akan bernilai x dan size-nya akan bertambah.

-     Jika head dan tail sama dengan NULL, maka tail dot next sama dengan x, selanjutnya tail akan berpindah ke x, dan x dot next sama dengan NULL.

6)   Fungsi insertbeafor :

-     Membuat fungsi untuk insertbeafor.

-     Membuat node baru dengan nama variabel x.

-     Menginisialisasikan x dot next sama dengan 10 dan x dot next sama dengan NULL.

-     Membuat variabel bantuan dengan nama y di head.

-     Jika y dot next tidak sama dengan NULL, maka jika y dot data sama dengan parameter fungsi, x dot next sama dengan y dot next.

7)   Fungsi insertbetween :

-     Membuat fungsi untuk insertbetween dengan dua buah parameter yang bertipe data integer.

-     Menginisialisasi nilai data dari x sama dengan 30.

-     Mengakses head dengan y.

-     Memeriksa semua data yang ada dalam linked list.

-     Jika y dot next tidak sama dengan NULL, jika y dot data sama dengan parameter fungsi dan y dot next dot data sama dengan b, maka x dot next sama dengan y dot next dan y dot next sama dengan x.

-     Ukuran size bertambah.

-     Jika nilai data dari x sama dengan a dan data setelahnya sama dengan b, maka nilai data tersebut diubah dan dihubungkan dengan y.

-     Menambahkan ukuran linked list.

8)   Fungsi deletfront :

-     Membuat fungsi untuk deletefront tanpa menggunakan parameter.

-     Mengakses head dengan x.

-     Memindahkan head ke node selanjutnya.

-     Memisahkan node x dengan linked list, lalu menghapus node x tersebut

-     Mengurangi ukuran linked list dari depan.

9)   Fungsi deletback :

-     Membuat fungsi untuk deleteback.

-     Mengakses head dengan x.

-     Memindahkan node x ke node sebelum tail, lalu memindahkan node tail ke node x.

-     Memindahkan node x ke node terakhir, memisahkan node x dengan linked list, dan menghapus node x tersebut

-     Mengurangi ukuran linked list dari belakang.

10)    Fungsi deletall :

-     Membuat fungsi deleteall.

-     Melakukan perulangan node di linked list sampai node tail dan head berada di satu node.

-     Mengakses head dengan x.

-     Memindahkan head ke node selanjutnya.

-     Memisahkan node x dengan linked list, lalu menghapus node x tersebut.

-     Mengurangi ukuran linked list.

-     Mengosongkan node head.

11)    Fungsi cetak:

-     Membuat fungsi cetak.

-     Mengakses head dengan x.

-     Mencetak node x dan memindahkan node x ke node selanjutnya

-     Memisahkan node x dengan linked list, lalu menghapus node x tersebut

-     Mengurangi ukuran linked list.

12)    Fungsi utama:

-     Menginisialisasi kelas

-     Pemanggilan fungsi parameter

-     Memanggil fungsi addfront

-     Menampilkan data addfront

-     Memanggil fungsi addback

-     Menampilkan data addback

-     Memanggil fungsi insertafter

-     Menampilkan data insertafter

-     Memanggil fungsi insertbetween

-     Menampilkan data insertbetween

-     Memanggil fungsi insertbeafor

-     Menampilkan data insertbeafor

-     Memanggil fungsi deletefront

-     Menampilkan data deletefront

-     Memanggil fungsi deleteback

-     Menampilkan data deleteback

-     Memanggil fungsi deleteall

-     Menampilkan data deleteall 

b.    Source Code

#include <iostream> #include <conio.h>   class LL{ private: struct bisa{ int data; bisa *next; }; int size; bisa *head; bisa *tail; public: void ll(){ head=NULL; tail=NULL; size=0; }; void addfront(int a){ bisa *x=new bisa; x->data=a; x->next=NULL; if (head==NULL && tail==NULL){ head=x; tail=x; size++; }else{ x->next=head; head=x; size++; } } void addback(int a){ bisa *x=new bisa; x->data=a; x->next=NULL; if (head==NULL && tail==NULL){ head=x; tail=x; size++; }else{ tail->next=x; tail=x; x->next=NULL; size++; } } void insertafter(int a,int b){ bisa *x=new bisa; x->data=b; x->next=NULL; bisa *y=head; while (y->next!=NULL){ if(y->data==a){ x->next=y->next; y->next=x; size++; } y=y->next; } } void insertbeafor(int a,int b){ bisa *x; bisa *tujuan; x=tujuan=head; while (x->data!=a){ tujuan=x; x=tujuan->next; } if (x->data==a){ bisa *y=new bisa; y->data=b; y->next=NULL; y->next=tujuan->next; tujuan->next=y; size++; } } void insertbetween(int a, int b){ bisa *x=new bisa; x->data=30; x->next=NULL; bisa *y=head; while (y->next!=NULL){ if(y->data==a && y->next->data==b ){ x->next=y->next; y->next=x; size++; } y=y->next; } } void deletfront(){ bisa *x=head; head=head->next; x->next=NULL; delete x; size--; } void deletback(){ bisa *x=head; while(x->next!=tail){ x=x->next; } tail=x; x=x->next; tail->next=NULL; delete x; size--; } void deletall (){ while (head->next!=NULL){ bisa *x=head; head=x->next; x->next=NULL; delete x; size--; } head=NULL; cout<<" (DATA KOSONG)\n"; } void cetak (){ bisa *x; x=head; while (x!=NULL){ cout<<" "<<x->data; x=x->next; } } }; void main(){ LL k; k.ll(); cout<<" \nData AddFront : "; k.addfront (1); k.addfront (2); k.addfront (3); k.cetak(); cout<<" \nData AddBack : "; k.addback (5); k.addback (6); k.addback (7); k.cetak(); cout<<" \nData Insert After : "; k.insertafter (5,6); k.cetak(); cout<<" \nData Insert Beafor : "; k.insertbeafor (5,10); k.cetak(); cout<<" \nData Insert Between : "; k.insertbetween (6,7); k.cetak(); cout<<" \nData Delete Front : "; k.deletfront (); k.cetak(); cout<<" \nData Delete Back : "; k.deletback (); k.cetak(); cout<<" \nData Delete All : "; k.deletall (); k.cetak(); getch(); }

c.   Hasil run program

Gambar 1.3 Screenshot permasalahan 2

 

1.4.  ANALISA

1.    Analisa Permasalahan Pertama.

#include <iostream> #include <conio>

·      Merupakan header file yang digunakan dalam program

int main () { int A[100], n;    cout<<"Masukkan Jumlah Data : "; cin>>n;    for (int i=0;i<n;i++) {       cout<<"A ["<<i<<"] = "; cin>>A[i];}

·      Mendeklarasikan array satu dimensi dengan batas 100. Jumlah array dimasukkan secara dinamis. Menggunakan sebuah perulangan untuk mengecek kondisi, jika masih tidak terpenuhi maka akan tetap melakukan perulangan sampai batas array yang telah dimasukkan sebelumnya, dan kemudian memberikan nilai disetiap indeks array secara dinamis.

for (int i=0;i<n;i++) {       cout<<"A ["<<i<<"] = "<<A[i]<<endl;

·      Untuk menampilkan hasil array yang telah diberikan nilai dimasing-masing indeks pada tahap sebelumnya.

 

2.    Analisa Permasalahan 2.

class LL{

·      Menampung tipe data baru pada linked list, dan “LL” merupakan nama dari ”class”.

private: struct bisa{ int data; bisa *next; }; int size; bisa *head; bisa *tail;

·      ”private:” ini hanya akan diakses di “class” saja. Di dalamnya terdapat deklarasi struct dengan nama variabel “bisa” yang terdapat deklarasi variabel data dan size dengan tipe data integer dan juga next, head dan tail yang merupakan atribut dari struct.

public: void ll(){ head=NULL; tail=NULL; size=0; };

·      “public” dapat diakses oleh semua bagian program. di dalamnya terdapat konstruktur “void ll()” dan pendeklarasikan head dan tail bernilai NULL dan size bernila nol.

void addfront(int a){ bisa *x=new bisa; x->data=a; x->next=NULL; if (head==NULL && tail==NULL){ head=x; tail=x; size++; }else{ x->next=head; head=x; size++;} }

·      Merupakan sebuah fungsi untuk menambahkan node dari depan. Diawali dengan pembuatan node baru dan pendeklarasian x dot data sama dengan parameter a, sedangkan x dot next-nya sama dengan NULL. Selanjutnya pengecekan kondisi. Jika kondisinya terpenuhi, dimana head dan tail sama dengan NULL, maka head dan tail sama dengan x. Namun jika kondisi tidak terpenuhi, maka akan menjalankan statement yang terdapat pada kondisi “else” untuk membuat x menjadi head dengan “size++” untuk menambah node.

·      “addfront” dan “addback” sebenarnya sama saja. Hanya bedanya di “addfront”, x-nya yang akan dibuat menjadi head dan di “addback”, x-nya akan dibuat menjadi tail.

void insertbeafor(int a,int b){ bisa *x; bisa *tujuan; x=tujuan=head; while (x->data!=a){ tujuan=x; x=tujuan->next; } if (x->data==a){ bisa *y=new bisa; y->data=b; y->next=NULL; y->next=tujuan->next; tujuan->next=y; size++;} }

·      Merupakan fungsi untuk menambahkan node di sebelum node yang keberapa sesuai yang diinginkan. Variabel x dan tujuan merupakan atribut dari struct bisa. Menempatkan x dan tujuan pada head. Dilanjutkan dengan pengecekan kondisi untuk menempatkan posisi “x” dan “tujuan” ke node a jika x dot data tidak sama dengan a. Sebaliknya jika x dot data sama dengan a, maka dilanjutkan ke kondisi untuk mengeksekusi statement didalamnya hingga node baru tersebut terhubung dengan node sebelum dan sesudahnya.

·      “insertafter” dan “insertbetween” hampir sama dengan “insertbeafor”, bedanya “insertbeafor” menambahkan node baru didepan, “insertafter” menambahkan node baru setelahnya, sedangkan “insertbetween” menambahkan node baru diantara kedua node yang diinginkan.

void deletfront(){ bisa *x=head; head=head->next; x->next=NULL; delete x; size--;}

·      Merupakan fungsi untuk menghapus node dari depan. Awalnya Mendeklarasikan variabel x yang menjadi atribut dari stuct menjadi sama dengan head. Head sama dengan head dot next, untuk memindahkan head ke node setelahnya dan kemudian x dot next dibuat sama dengan NULL agar memutuskan node x dari linked list. Hal terakhir yaitu “delete x” untuk menghapus node x. “size—“ untuk mengurangi ukuran size.

·      “deletefront” sama halnya dengan “deleteback”, hanya bedanya “deletefront” menghapus node dari depan atau head sedangkan “deleteback” menghapus node dari belakang atau tail.

void deletall (){ while (head->next!=NULL){ bisa *x=head; head=x->next; x->next=NULL; delete x; size--; } head=NULL; cout<<" (DATA KOSONG)\n";}

·      Merupakan fungsi untuk menghapus semua node. Pertama akan dicek kondisi yang ada dan jika kondisi tersebut tidak terpenuhi maka akan menjalankan statement didalamnya untuk menghapus data dari depan secara satu persatu hingga tersisa “head”-nya saja. Sedangkan jika kondisi tersebut terpenuhi maka menjalankan statement diluar while untuk mengosongkan nilai “head” sehingga data terhapus semua.

void cetak (){ bisa *x; x=head; while (x!=NULL){ cout<<" "<<x->data; x=x->next;} }

·      Merupakan fungsi untuk menampilkan hasil list. “void cetak()” merupakan bagian dari kelas LL yang bertipe data void. Nilai x sama dengan head. “while (x!=NULL) artinya jika x tidak sama dengan NULL, maka {cout<<" "<<x->data;x=x->next;}” untuk menampilkan data dari setiap node satu persatu.

void main(){ LL k; k.ll(); cout<<" \nData AddFront : "; k.addfront (1); k.addfront (2); k.addfront (3); k.cetak(); . . .

·      Merupakan fungsi utama dalam program. “LL k” adalah pendeklarasian class “LL” dalam variabel “k”. “k.addfront (3)” adalah kode untuk memanggil dan menjalankan fungsi yang telah dibuat dan 3 adalah data yang dikirim ke fungsi yang dipanggil begitu seterusya. Sedangkan “getch()” adalah fungsi untuk mengakhiri program dan menahan tampilannya agar tidak keluar saat di jalankan.

1.6.  KESIMPULAN

Berdasarkan praktikum yang telah dilaksanakan dapat disimpulkan bahwa :

1.    Array adalah sebuah variabel yang menyimpan sekumpulan data yang memliki tipe data yang sama. Array terdiri dari array satu dimensi, dua dimensi, dan array dinamis.

2.    Single linked list  hanya memiliki satu penunjuk arah yaitu next, didalam single linked list  langkah yang pertama yang wajib dibuat yaitu nama class dimana sebagai nama konstruktor yang menampung suatu bentuk tipe data baru dalam linked list. Dimana terdiri dari private dan public. Private berfungsi mengakses source code yang ada di dalam kelas itu saja, sedangkan public berfungsi mengakses seluruh program yang ditampung dalam struct node. 

3.    Operasi linked list dibagi menjadi 3 yaitu, operasi pembuatan, penyisipan dan penghapusan. Dimana dalam membuat node baru menggunakan keyword new. Penambahkan node dapat menggunakan penyisipan dimana kita dapat menyisipkan node melalui  insert first, insert after, insert last, dan insert before. Sedangkan penghapusan kita dapat melakukan penghapusan node dari delete after, delete last, delete first, dimana penghapusan simpul tertentu ada dua macam, yaitu delete K node, delete node.