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)

Continue reading “Algoritma dan Struktur Data”

Advertisements

Desain dan Analisis Algoritma; Sebuah Pengantar


Hallo semua, kali ini saya akan mencoba menulis sebuah artikel tentang Desain dan Analisis Algoritma. Anak ilmu komputer, teknik informatika, matematika tentu sudah sangat familiar dengan tema ini. Namun tak ada salahnya kita coba ulas kembali untuk menyegarkan ingatan kita. Sippps?! Namun, sebelum kita bahas terlalu dalam, alangkah baiknya kita mengulang beberapa hal.

Secara umum, algoritma adalah sebuah prosedur atau langkah-langkah komputasi yang terdifinisikan dengan baik yang membutuhkan nilai/kumpulan nilai sebagai inputnya dan menghasilkan nilai/kumpulan nilai sebagai outputnya. Dari definisi ini maka bisa kita ambil kata kunci bahwa algoritma itu terdiri dari 3 elemen, ada input, proses, dan output. Algoritma ini digunakan untuk menyelesaikan permasalahan komputasi yang jelas (masalahnya harus jelas ya hehe). Biasanya, dalam sebuah permasalahan komputasi akan tergambarkan bagaiamana hubungan antara input dan output. Contoh sederhananya misalkan Continue reading “Desain dan Analisis Algoritma; Sebuah Pengantar”