Summary


Pengertian Linked List
bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait. Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data. Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer.
Bentuk umum :



Operasi - Operasi dalam Linked List :
Operasi - operasi yang pasti dimiliki oleh setiap list adalah sebagai berikut: 

  • Insert / penambahan : untuk menyisipkan elemen kedalam list.
  • Delete / penghapusan : untuk menghapus suatu elemen dalam list.
Dalam implementasinya penambahan dan penghapusan suatu elemendikembangkan kembali sehingga menghasilkan beberapa variasi dalam penggunaanya. Contoh operasi hasil pengembangannya adalah sebagai berikut
  • InsertFirst : penambahan elemen pertama
  • InsertLast : penambahan elemen terakhir
  • InsertAt : penambahan elemen pada index ke-n
  • DeleteFirst : penghapusan elemen pertama
  • DeleteLast : penghapusan elemen terakhir
  • DeleteAt : penghapusan elemen pada index ke-n
Selain operasi utama seperti yang dilakukan sebelumnya, ada pula operasiyang dibuat untuk membantu dalam penggunaan linked list (operasitambahan).Contoh operasi tambahan pada linked list adalah sebagai berikut: 
  • isEmpty : Operasi untuk mengetahui apakah list tersebut kosong atautidak.
  • Inisialisasi : Operasi untuk melakukan inisialisasi (memberi nilai awal) pada list.
  • Allocate : Operasi untuk memesan alamat yang belum digunakan.
  • Deallocate : Operasi untuk membebaskan alamat yang tidak digunakan.
Macam - macam Linked List

Single Linear Linked List
Single linear linked list merupakan jenis linked list yang paling sederhana. Untuk seterusnya, jika dikatakan Linked List maka bentuk inilah yang dimaksud. Linked List ini pada tiap-tiap elemen hanya memiliki 1 pointer (penunjuk) yaitu pointer terhadap elemen selanjutnya.Berikut ini adalah gambaran untuk single linear linked list:



Contoh dalam kehidupan sehari-hari yaitu ketika di bank terdapat suatu antrian, yang datangmengantri lebih dulu akan lebih dulu dilayani sedangkan yang baru datang diharuskan untukmengantri di antrian.

Deklarasi node dengan struct:

Double Linear Linked List
Double linear linked list merupakan jenis linked list yang memiliki 2 buah pointer(penunjuk) yaitu pointer terhadap elemen selanjutnya dan juga pointer terhadap elemensebelumnya. Berikut ini adalah gambaran untuk double linear linked list:



Single Circular Linked List
Single circular linked list merupakan jenis linked list yang memiliki 1 buah pointer(penunjuk) yaitu pointer terhadap elemen selanjutnya (sama seperti single linear linked list),namun pada linked list jenis ini elemen terakhir pada list memiliki pointer menuju elemen pertama dari list tersebut, sehingga terjadi susunan elemen yang melingkar / tidak adaelemen yang bernilai null. Berikut ini adalah gambaran untuk single circular linked list:

Deklarasi Single Linked List Circular:


Double Circular Linked List
Double circular linked list merupakan jenis linked list yang memiliki 2 buah pointer(penunjuk) yaitu pointer terhadap elemen selanjutnya dan juga pointer terhadap elemensebelumnya (sama seperti double linear linked list), namun pada linked list jenis ini elementerakhir pada list memiliki pointer menuju elemen pertama yang menunjukkan elemenselanjutnya dari list tersebut dan elemen pertama memiliki pointer menuju elemen terakhiryang menunjukkan elemen sebelumnya dari elemen pertama adalah elemen terakhir,sehingga terjadi susunan elemen yang melingkar dari dua arah / tidak ada elemen yang bernilai null. Berikut ini adalah gambaran untuk double circular linked list:

pengertian stack

Stack atau tumpukan merupakan salah satu teknik dalam struktur data yang cukup mudah dipahami. Karakteristik penting stack adalah bersifat LIFO (Last In First Out) artinya data yang terakhir masuk merupakan data yang akan keluar terlebih dahulu. 
metode implementasi pada stack

Ada lima metode penting dalam implementasi stack.

push(), berfungsi untuk memasukkan data.
pop(), berfungsi untuk mengeluarkan data terakhir (atas).

peek(), berfungsi untuk melihat data yang berada pada tumpukan paling atas (akan dikeluarkan).

isEmpty(), berfungsi untuk menguji apakah stack masih kosong.

isFull(), berfungsi untuk menguji apakah stack telah penuh.
contoh stack
Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai masimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang dapat diambil.

macam - macam stack

Stack dengan Array
Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

Double Stack dengan Array
Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

pengertian queue

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

operasi - operasi pada queue

Create()
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail  = -1

IsEmpty()
Untuk memeriksa apakah Antrian sudah penuh atau belum
Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.
IsFull
Untuk mengecek apakah Antrian sudah penuh atau belum
Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh
Enqueue
Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang
Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu
Dequeue()
Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian
Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1
Penggeseran dilakukan dengan menggunakan looping.

Clear()
Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

 Tampil()
Untuk menampilkan nilai-nilai elemen Antrian
Menggunakan looping dari head s/d tail

Hashing

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Itu juga digunakan dalam banyak algoritma enkripsi.

Berikut adalah beberapa fungsi hash yang relatif sederhana yang telah digunakan:

  • Metode pembagian-sisa : Ukuran jumlah item dalam tabel diperkirakan. Angka itu kemudian digunakan sebagai pembagi ke dalam setiap nilai atau kunci asli untuk mengekstrak hasil bagi dan sisa. Sisanya adalah nilai hash. (Karena metode ini bertanggung jawab untuk menghasilkan sejumlah tabrakan, mekanisme pencarian apa pun harus dapat mengenali tabrakan dan menawarkan mekanisme pencarian alternatif.)
  • Metode lipat : Metode ini membagi nilai asli (dalam kasus ini digit) menjadi beberapa bagian, menambahkan bagian-bagian bersama-sama, dan kemudian menggunakan empat digit terakhir (atau beberapa digit angka acak lainnya yang akan berfungsi) sebagai nilai hash atau kunci.
  • Metode transformasi radix: Jika nilai atau kunci digital, basis angka (atau radix) dapat diubah menghasilkan urutan digit yang berbeda. (Misalnya, kunci angka desimal dapat diubah menjadi kunci angka heksadesimal.) Angka urutan tinggi dapat dibuang agar sesuai dengan nilai hash dari panjang seragam.
  • Metode penataan ulang digit: Ini hanya mengambil bagian dari nilai asli atau kunci seperti digit di posisi 3 hingga 6, membalikkan urutannya, dan kemudian menggunakan urutan digit itu sebagai nilai atau kunci hash.

Hash Table

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

 Operasi Pada Hash Tabel
  • insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
  • find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
  • remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
  • getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data.

Berikut contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m)
Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
Dengan hash function tersebut didapat :
Perhatikan range dari h untuk sembarang nilai k.

Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..
Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.
Misal : mencari data 25 → h = 25 (mod 13) = 12
Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat. Dalam contoh di atas gunakan m untuk me-modulo k. Perhatikan bila kita menggunakan angka m untuk me-modulo k maka pada indeks yang lebih besar dari dan sama dengan m di hash table tidak akan pernah terisi (memori yang terpakai semakin kecil), kemungkinan terjadi collision juga semakin besar.
Karena memori yang terbatas dan untuk masukan data yang belum diketahui tentu collision tidak dapat dihindari.
Berikut ini cara-cara yang digunakan untuk mengatasi collision :
1.   Closed hashing (Open Addressing)
Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

  • Ø Linear Probing
  • Ø Quadratic Probing
  • Double hashing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus
(h+1) mod m.
Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.
Contoh formula quadratic probing untuk mencari alamat baru:
h,(h+i2)mod m,(h-i2)mod m, … ,(h+((m-1)/2)2)mod m, (h-((m-1)/2)2)mod m
dengan i = 1,2,3,4, … , ((m-1)/2)
Mksud formula di atas adalah jika alamat h telah terisi, maka alamat lain yang digunakan adalah (h+1)mod m, jika telah terisi gunakan alamat (h-1)mod m,  jika telah terisi gunakan alamat (h+4)mod m, jika telah terisi gunakan alamat (h-4)mod m, dan seterusnya.
Jadi jika m=23,maka nilai maksimal i adalah : ((23-1)/2)=11.
Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.
Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.
2.   Open hashing (Separate Chaining)
Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.
Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Tree and Binary Tree

Tree


Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

Node yang berada di pangkal tree disebut node root (akar), sedangkan node yang berada paling ujung pada piramida tree disebut node leaf (daun). 

Binary Tree


Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner. Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak. Tidak boleh lebih. Pada pohon biner, umumnya kedua node anak disebut dengan

posisinya, yaitu kiri dan kanan. 

Beberapa istilah pada pohon biner:
  • Size (ukuran): jumlah total node yang terdapat pada pohon biner tersebut.
  • Depth (kedalaman): panjang jalur yang menghubungkan sebuah node sampai ke node anaknya yang paling ujung (leaf). Depth biasa juga disebut height. 
Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti memiliki 0 atau 2 node anak. Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root. Juga disebut sebagai Complete Binary Tree (Pohon Biner Lengkap) Almost Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang setiap nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus memiliki kiri. Tidak boleh memiliki kanan saja. 

 Deklarasi Tree


Inisialisasi Tree

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama *pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer *pohon ditunjukkan ke NULL.

Menambahkan Node Pada Tree

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:


Pengertian 

binary search tree (BST) atau yang terkadang disebut juga sebagai sorted binary tree, merupakan semacam container struktur data, yang menyimpan informasi seperti bilangan atau nama yang ada di dalam memory. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Binary search tree menempatkan key tersebut secara urut, yang memungkinkan pencarian dengan cara binary search. Binary tree terdiri dari node utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut.

Aturan Dalam Membangun BST

Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:
  1. Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.    
  2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.
BST berikut adalah sebuah BST berukuran 9 dengan kedalaman 3 dengan node daun (leaf) adalah 1, 4, 7 dan 13.

Contoh Aplikasi BST


  1. Membangun daftar vocabulary yang merupakan bagian dari inverted index (sebuah struktur data yang digunakan oleh banyak mesin pencari seperti Google.com, Yahoo.com dan Ask.com)
  2. Banyak digunakan dalam bahasa pemrograman untuk mengelola dan membangun dynamic sets. 

Contoh Implementasi BST




 

Comments

Post a Comment

Popular Posts