LINKED LIST VS ARRAY


LINKED LIST VS ARRAY

1. PENDAHULUAN
Linkedlist adalah struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori, sedangkan array adalah Array merupakan tipe data terstruktur yang berguna untuk menyimpan sejumlah data yang bertipe sama. Bagian yang menyusun array disebut elemen array, yang masing-masing elemen dapat diakses tersendiri melalui indeks array. Ada beberapa persamaan dan perbedaan antara linked list dan array, oleh karena itu dalam penggunaanya kita harus mengetahui penggunaan antara keduanya, agar program yang kita buat dapat berjalan dengan efektif dan efisien, terutama ditinjau ari alokasi memory dan data maksimal yang akan digunakan (apakah jumlah maksimal data diketahui atau tidak).

2.1 Pengertian Linked list :

·         sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
·         struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.

 










 
 









 




Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor) Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena

Next(Last) = Nil Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null

Single Linked
 
Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. 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 List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List dapat menggunakan 2 metode:
·         LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
·         FIFO (First In First Out), aplikasinya : Queue (Antrean)

Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List
·      Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
·      IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
·      Find First
Fungsi ini mencari elemen pertama dari linked list
·      Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now


·      Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
·      Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
·      Delete Now
Linked List VS Array 4 Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
·      Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.


·      Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List
·      IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
·      Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
·      Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
·      Clear
Fungsi ini akan menghapus stack yang ada.

B. STACK DENGAN MENGGUNAKAN ARRAY
Pengertian Stack
·      Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman
·      Bersifat LIFO (Last In First Out)
·      Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack
·      Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga. 
Operasi-operasi/fungsi Stack
·      Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
·      Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
·      Clear : digunakan untuk mengosongkan stack
·      IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
·      IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
     Stack with Array of Struct
·      Definisikan Stack dengan menggunakan struct
·      Definisikan MAX_STACK untuk maksimum isi stack

Deklarasi MAX_STACK
#define MAX_STACK 10 //hati-hati mulai dari 0 jadi 0-9
Deklarasi STACK dengan struct dan array data
typedef struct STACK{ int top; char data[10][10]; //misalkan : data adalah array of string //berjumlah 10 data, masing-masing string //menampung maksimal 10 karakter };

Inisialisasi Stack
·           Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG!
·           Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!
·           Ilustrasi stack pada saat inisialisasi: 

Fungsi IsFull
·      Untuk memeriksa apakah stack sudah penuh?
·      Dengan cara memeriksa top of stack, jika sudah sama dengan  MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full

·      Ilustrasi:
 

Fungsi IsEmpty
·      Untuk memeriksa apakah stack masih kosong?
·      Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!
·      Program:
 


Fungsi Push
·      Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack
·      Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)
·      Ilustrasinya:
 

Fungsi Pop
·           Untuk mengambil elemen teratas dari stack.
·           Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang
·           Ilustrasinya:
 
Programnya:
Fungsi Print
·           Untuk menampilkan semua elemen-elemen stack
·           Dengan cara looping semua nilai array secara terbalik, karena kita harusmengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!
Program: 

PEMBAHASAN
A. Perbandingan antara Stack Dengan Linked List dan Stack Dengan Array

Berikut ini adalah perbandingan algoritma pada operasi-operasi dasar dari Stack Dengan Linked List dan Stack Dengan Array, dengan menggunakan bahasa pemrograman Pascal
Stack Dengan Linked List
Stack Dengan Array
operasi : create()
procedure create;
begin
      top := nil ;
end;

procedure create;
begin
     top := 0;
end;

operasi : empty()
function empty : boolean;
begin
         empty := false ;
         if top = nil then empty := true ;
end;

function empty : boolean;
begin
        empty := false ;
        if top = 0 then empty := true ;
end;

operasi : full()
tidak ada istilah full pada stack. program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
function full : boolean;
begin
          full := false ;
          if top = max then full := true ;
end;

operasi : push()
procedure push (elemen : typedata) ;
var now:point ;
begin
         now(now) ;
         now^.isi := elemen ;
         if empty then
            now^.next := nil ;
        else
             now^.next := top ;
        top := now ;
end;
procedure push (elemen : typedata) ;
begin
          if not full then
            begin
               top := top + 1 ;
               stack [top] := elemen ;
            end;
end;

operasi : pop()
procedure pop (var elemen : typedata) ;
var now:point ;
begin
        if not empty then
           begin
        elemen := now^.isi ;
        now := top ;
        top := top^.next ;
        dispose(now) ;
         end;
end;


procedure pop (elemen : typedata) ;
begin
          if not empty then
             begin
                     elemen := stack [top] ;
                      top := top – 1 ;
          end;
end;


operasi : clear
procedure clear ;
var trash : typedata ;
begin
       while not empty do pop(trash) ;
end;

procedure clear ;
begin
       top := 0 ;
end;



KESIMPULAN
Dari perbandingan diatas, dapat dilihat pada linked list tidak dikenal istilah full. Hal ini berkaitan dengan penggunaan alokasi memori pada linked list yang lebih dinamis jika dibandingkan dengan array, sehingga pemborosan memory dapat dihindari. Program tidak menentukan jumlah elemen stack yang mungkin ada. Kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. Tempat akan sesuai dengan banyaknya elemen yang mengisi stack.

DAFTAR PUSTAKA
Linked List vs Array.pdf, http://mti.ugm.ac.id/~lukis/UMM/ALGORITMA/linked%20list%20VS%20array.pdf
Waktu akses: 2 Maret 2010, 21.25 WIB






Categories:

Leave a Reply