Algoritma dan Struktur Data

Stack with Linked List

Anggota Kelompok:

1. Desenia Mulyani Harja (F1D012014)

2. Riris Parahita (F1D012074)

Program Studi Teknik Informatika

Fakultas Teknik

U N I V E R S I T A S M A T A R A M

2 0 1 3

Stack with 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 tersebutsudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalahdi atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis,variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkandapat direlokasikan kembali. Setiap ingin menambahkan data, Anda selalu menggunakanvariabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer.

Oleh karena itu, ada baiknya jika Anda hanya menggunakan satu variabel pointer sajauntuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked listadalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yangsetiap 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 senaraiberantai. Linked list sendiri dapat diartikan sebagai sekumpulan komponen yang salingberhubungan (berantai) dengan bantuan pointer. Perhatikan ilustrasi berikut untuk lebihjelasnya.

Masing-masing komponen disebut sebagai simpul atau node. Setiap simpul terbagimenjadi dua bagian, yaitu bagian data dan bagian penyambung. Bagian data berisi datayang akan disimpan dan diolah. Sedangkan bagian penyambung berisi alamat simpulberikutnya.

Inti dari linked list adalah proses (tambah, edit, hapus) dari gerbong/node dan bagaimana rnenyambungkan antar gerbong /node tersebut.

ARRAY VS LINKED LIST

ARRAY LINKED LISTStatis DinamisPenambahan / penghapusan data terbatas Penambahan / penghapusan data tidak terbatas

Random access Sequential accessPenghapusan array tidak mungkin Penghapusan linked list mudah

1. Pembuatan Single Linked List

Deklarasi node dibuat dari struct berikut ini:

Penjelasan:

- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipeinteger dan field next yang bertipe pointer dari TNode.

- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNodeyang berguna sebagai kepala linked list.

2. Pembentukan Node Baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasimemorinya, kemudian node tersebut diisi data dan pointer next-nya ditunjuk ke NULL

3. 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 bisadilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointerpenunjuk ke node pertama dalam linked list (dalam hal ini adalah head). Deklarasinyasebagai berikut:

TNode *head;

Fungsi untuk mengetahui kosong tidaknya Single Linked List jika pointer head tidakmenunjuk pada suatu node maka kosong.

4. Penambahan Data

Penambahan node baru akan dikaitan di node paling depan, namun pada saatpertama kali (data masih kosong), maka penambahan data dilakukan dengan cara headditunjukkan ke node baru tersebut. Pada prinsipnya adalah mengkaitkan node barudengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akantetap selalu menjadi data terdepan.

ilustrasi:

5. Menampilkan Data

Fungsi untuk menampilkan isi single linked list (non circular)

Penjelasan :

- Fungsi di atas digunakan untuk menampilkan semua isi list, di mana linked listditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran inidilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnyapointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.

- Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilaiNULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnyadan membaca isi datanya dengan menggunakan field next sehingga dapat salingberkaitan.

- Jika head masih NULL berarti data masih kosong.

6. Penghapusan Data

Fungsi di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head padalinked list.

Penjelasan :

- Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk olehpointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakanuntuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulahkemudian menghapus pointer hapus dengan menggunakan perintah delete.

- Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnyaterlebih dahulu agar list tidak putus, sehingga node setelah head lama akanmenjadi head baru (data terdepan yang baru).

- Jika head masih NULL maka berarti data masih kosong.

Contoh Sourcecode Stack with Linked List :

#include <conio.h>#include <iostream>

using namespace std;

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"<<endl;}

void tampil(){TNode *bantu;bantu=head;if(isempty()==0){while (bantu!=NULL){

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

void main(){int pil;int databaru;do{

cout<<"linked List"<<endl;cout<<"-----------"<<endl<<endl;cout<<"1.Insert Depan"<<endl;cout<<"2.Tampil"<<endl;cout<<"3.Hapus"<<endl;cout<<"4.Exit"<<endl<<endl;cout<<"pilihan anda= ";cin>>pil;

switch(pil){{case 1:cout<<endl;cout<<"data: ";cin>>databaru;cout<<endl;insertdepan (databaru);

break;}{case 2:cout<<endl;tampil();break;}{case 3:cout<<endl;hapusdepan();break;}}getch();}while (pil!=4);}

Hasil compile :

Analisa Program :

Program di atas menggunakan visual c++ dengan header iostream dan conio.h yang dimana terdapat fungsi cout dan cin. Selain itu, menggunakan using namepace std; untuk menjalankan cout dan cin pada visual c++. Dalam program visual c++ tersebut terdapat node yang berfungsi untuk menyimpan data. 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. Pada sintaks di atas juga terdapat Fungsi IsEmpty yaitu untuk memeriksa apakah stack masih kosong dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong. Next pada sintaks di atas merupakan address (alamat) dari elemen berikutnya (suksesor) dengan demikian jika didefinisikan first adalah alamat elemen pertama list, maka elemen berikutnya dapat di akses secara suksesif dari field next elemen tersebut. head->next=NULL; artinya head tersebut didefinisikan ke next yang berisi NULL. Program tersebut menggunakan pointer untuk menuju ke alamat yang akan dituju.