Algoritma dan Struktur Data

Kali ini kita akan bahas tentang hubungan algoritma dan struktur data. Pada saat algoritma dijalankan, maka data (input/output) akan disimpan dalam suatu tempat (struktur data) untuk kemudian diproses. Kita sudah mengenal beberapa struktur data seperti struktur data linear misalnya linked list, queue (antrian), stack (tumpukan), dan struktur data non-linear misalnya tree yang bersifat hirarki. Struktur data adalah cara merepresentasikan atau menyimpan data dalam memori komputer. Data ini harus direpresentasikan sedemikian rupa sehingga mudah diproses. Di sinilah peran struktur data dan alasan kenapa penting untuk memahami topik ini.

Sebagai bahan penyegaran, kita akan mereview beberapa jenis struktur data yang umum digunakan

  • Linked List
    Linked list merupakan sebuah struktur data list yang saling terhubung melalui suatu link. Dalam sebuah linked list terdapat node dan link. Node pertama disebut head. Ada beberapa tipe linked list misalnya single linked list, double linked list, dan circular linked list. Suatu node pada linked list terdiri dari data item dan pointer ke node lainnya. Single linked list hanya memiliki 1 pointer yang mengarah ke node selanjutnya sehingga hanya bisa melakukan proses penelusuran ke depan (forward). Double linked list terdiri dari data item dan dua pointer yang menunjuk ke node sebelum dan sesudahnya. Jadi double linked link bisa melakukan proses penelusuran ke depan (forward) dan belakang (backward). Circular linked list mirip dengan single linked list, namun pointer node terakhir menunjuk ke alamat head.

    Single Linked List
    single linked list
    Double Linked List
    Double Linked List
    Circular Linked List
    Circular Linked List

    Pada linked list dapat dilakukan operasi seperti insert menambahkan node baru baik di depan (head), di tengah, ataupun di belakang (tail). Operasi remove menghapus salah satu node. Update untuk memperbaharui nilai suatu node. Retrieve untuk mendapatkan informasi tentang isi dari suatu node tertentu.

  • Array
    Array merupakan salah satu tipe list yang memiliki suatu key atau yang lebih dikenal dengan index untuk menandai setiap elemen array tersebut. Pada beberapa bahasa pemrograman ukuran suatu array harus dideklarasikan terlebih dahulu sehingga memiliki lokasi yang fix dalam memori. Array biasanya diberi nama untuk membedakannya dengan array yang lain. Salah satu karakteristik array adalah bahwa semua elemen yang tersimpan di dalamnya memiliki tipe data yang sama. Jadi, data float tidak bisa ditampung dalam sebuah array yang memiliki tipe data integer. Array diakses dengan menggunakan indexnya. Index adalah suatu nilai yang menunjukkan urutan elemen dalam array, adapun elemen adalah data yang tersimpan dalam index tertentu. Misalkan Integer Array A[10]=12 maka bisa diartikan sebuah array A bertipe integer pada inde

    Array
    Array
  • Queue
    Queue juga merupakan salah satu jenis list namun memiliki sifat yang khas. Queue biasa dalam bahasa Indonesia disebut sebagai antrian. Queue bisa diimplementasikan dengan array ataupun linkedl list. Pada queue operasi penambahan (insertion) hanya bisa dilakukan di bagian belakang queue. Adapun penghapusan (deletion) hanya bisa dilakukan di bagian depan queue. Oleh karena itu, queue menerapkan prinsip First In First Out (FIFO). Salah satu variasi dari queue adalah Priority Queue. Pada Priority Queue setiap elemen queue memiliki suatu nilai (key) yang menunjukkan tingkat prioritasnya. Biasanya nilai yang lebih kecil menunjukkan prioritas lebih besar. Adanya nilai ini menyebabkan prinsip FIFO bisa diabaikan. Suatu elemen yang datang belakangan bisa dieksekusi terlebih dahulu karena memiliki prioritas lebih tinggi dari elemen yang sudah ada sebelumnya. Oleh karena itu, priority queue memiliki operasi tambahan yaitu mampu menentukan elemen dengan prioritas terbesar MAX (A), menaikkan prioritas suatu elemen ke nilai tertentu INCREASE-KEY (A, key, k), menentukan elemen terbesar dan menghapusnya/ekstrak REMOVE-MAX(A).

    Queue
    Queue
  • Stack
    Stack juga termasuk salah satu jenis list. Dalam bahasa indonesia stack biasa disebut juga sebagai tumpukan. Sama seperti queue, stack juga memiliki sifat atau operasi tertentu yang membedakannya dari list secara umum. Ukuran stack dapat ditentukan pada saat deklarasi. Jadi stack tersebut hanya mampu menampung sekian elemen sesuai dengan yang dideklarasikan di awal. Hal ini menyebabkan adanya operasi pada stack untuk mengetahui kondisi stack apakah kosong  (isEmpty) atau penuh (isFull). Selain itu, ada dua operasi pada stack yaitu menambahkan tumpukan (Push) atau mengambil tumpukan (Pop). Perintah Push akan menambah jumlah elemen dalam tumpukan dan harus didahului dengan perintah isFull. Hal ini dilakukan untuk menjamin bahwa masih ada ruang yang kosong untuk menambahkan elemen baru pada stack. Adapun perintah Pop akan mengambil elemen paling atas pada tumpukan sehingga jumlah elemen berkurang dan harus didahului dengan perintah isEmpty. Mengapa? karena sebelum mengambil sebuah elemen pada stack harus dipastikan dulu bahwa stack tersebut tidak kosong. Berbeda dengan Queue, Stack menganut prinsip Last In First Out (LIFO). Elemen yang terakhir masuk ke dalam stack akan pertama kali dikeluarkan karena sifat stack yang membatasi operasi hanya bisa dilakukan pada salah satu sisinya saja (bagian atas tumpukan)

Stack
Stack
  • Tree
    Struktur data Tree memiliki bentuk yang berbeda dengan struktur data list. Ada dua istilah umum dalam tree yaitu node dan edge. Node adalah elemen penyusun tree sedangkan edge adalah sesuatu yang menghubungkan suatu node dengan node yang lain. Ada beberapa istilah dalam struktur data tree yaitu

    • Root merupakan node yang berada dipuncak tree. Node ini tidak memiliki Parent.
    • Parent merupakan suatu node yang memiliki child
    • Child merupakan suatu node yang berada di bawah node lain yang berhubungan secara langsung
    • Sibling merupakan kumpulan node yang memiliki parent yang sama
    • Descendant merupakan kumpulan node yang berada setelah node tertentu dan berada pada satu jalur (path)
    • Ancestor merupakan kumpulan node yang berada sebelumnya node tertentu dan berada pada satu jalur (path)
    • Leaf merupakan node yang tidak memiliki child biasa juga dikenal dengan sebutan external node
    • Internal node seluruh node yang paling tidak memiliki sebuah child.
    • Subtree merupakan sebuah tree yang lebih kecil pada tree yang lebih besar
    • Path merupakan urutan suatu node dengan edge yang menghubungkan sebuah node dengan descendant-nya
    • Level node adalah jumlah edge yang menghubungkan node tersebut dengan root + 1
Tree
Tree

Ada beberapa jenis tree misalnya binary tree, B tree, dan B+ tree. Masing-masing tree ini memiliki karakteristik yang berbeda. Meskipun demikian, secara umum mengikuti pengertian atau istilah pada tree secara umum.

Suatu algoritma biasanya membutuhkan struktur data tertentu agar bisa dijalankan dengan efisien. Misalkan Insertion Sort akan lebih efisien dijalankan dengan struktur data list dibanding menggunakan tree. Atau suatu algoritma sorting seperti Heap Sort akan efektif dijalankan dengan menggunakan struktur data Heap. Cara merepresentasikan ini akan sangat mempengaruhi cara kerja suatu algoritma. Terkadang programmer membuat suatu struktur data sendiri untuk algoritma yang dibuatnya agar algoritma ini bisa berjalan dengan efisien. Oleh karena itu, penting bagi kita untuk memahami struktur data apabila ingin mempelajari desain dan analisis algoritma. Sekian dulu tulisan kali ini. Insya Allah akan dilanjutkan di kesempatan lain.

Advertisements

12 thoughts on “Algoritma dan Struktur Data

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s