Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.Pengertian:Single : artinya field pointer-nya hanya satu buah saja dan satu arah.Linked List : artinya node-node tersebut saling terhubung satu sama lain.Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar. Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
Operasi pada Double Linked List
Double linked list memiliki beberapa operasi dasar pada list, misalkan penyisipan, penghapusan, menampilkan maju, dan menampilkan mundur :
Insert First
Penyisipan di awal list, sehingga pointer head juga akan berpindah ke elemen baru.
Insert Last
Penyisipan di akhir list, sehingga pointer tail juga akan berpindah ke elemen baru.
Insert After / Before
gambar 1 : after gambar 2 : before
Penyisipan after/before kurang lebih sama satu sama lain. Pada kasus diatas berlaku juga insert before 3.
Delete First
Penghapusan di awal list, pointer head akan berpindah ke node selanjutnya,sementara node awal akan di dealokasi.
Delete Last
Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya,sementara node akhir akan di dealokasi.
Delete Node
Penghapusan node dengan data tertentu, pada kasus diatas yaitu delete node 2.
Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.
Hashingadalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasanya, hash berarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hashtable). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan recorddengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari recordtersebut.
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.
Contoh: asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68,38,52,70,44,18.
Hash function adalah suatu fungsi yang berguna untuk mengkompresi/memperkecil sebuah string yang panjang menjadi sebuah string yang lebih pendek. Dalam dunia kriptografi, hash function bukan merupakan suatu barang yang baru. Merupakan salah satu cabang dalam kriptografi, hash function memiliki daya tarik tersendiri dikarenakan cukup banyak aplikasi yang menggunakan hash function dalam penerapannya. Hash function digunakan sebagai otentikasi, integritas dan digital signature, salah satu aplikasinya yaitu penggunaan password dalam aplikasi digital atau internet.
Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.
Contoh :
Digit mulai posisi 7 sampai 10 (dari kanan) membentuk alamat relatif
Jumlah lokasi memori yang tersedi dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.
Contoh: asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68,38,52,70,44,18.
Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
Contoh :
Kunci 123456, 234351, 222456, 321654, dilipat menjadi 2 bagian, setiap 3 digit. Maka : 123+654 = 777 ; simpan 123456 dilokasi 777 234+153 = 387 ; simpan 234351 dilokasi 387 222+654 = 876 ; simpan 222456 dilokasi 876 321+456 = 777; simpan 321654 dilokasi 777 Dari perhitungan terjadi kolisi untuk nomor 123456 dan 321654.
Majemuk
Pada perkembangan selanjutnya, struktur data dibuat semakin kompleks. Dari struktur data yang sederhana kini mejadi struktur data majemuk. Pada struktur data majemuk ada yang linear dan non-linear.
Contoh multilist. Sumber : http://blog.gentra.xyz/2011/12/contoh-program-multi-list-competition.html
Majemuk Linear
Stack
Stack adalah daftar linear yang dikenal sebagai elemen puncak (top). Aturan penyisipan dan penghapusan elemen tertentu (penyisipan selalu dilakukan “atas” (top) dan penghapusan selalu dilakukan pada “atas”). Karena aturan penyisipan dan penghapusan seperti itu, “top” adalah satu-satunya alamat di mana operasi terjadi. Elemen terakhir yang ditambahkan akan menjadi elemen yang akan dihapus.
Queue
Queue adalah daftar linier yang dikenali sebagai elemen pertama (head) dan elemen terakhir (tail). Penghapusan elemen didefinisikan sebagai penyisipan setelah elemen terakhir. Penghapusan selalu dilakukan pada elemen pertama dengan satu elemen dapat diakses melalui informasi “next”.
List dan Multi List
Daftar dan Multi Daftar adalah sekumpulan daftar linier dengan elemen-elemen dengan tipe yang sama. Daftar ini memiliki urutan tertentu, yang masing-masing elemen terdiri dari 2 bagian.
Majemuk Non-Linear
Pada struktur data majemuk non-linear dibagi mejadi dua. Berikut 2 pembagian strutur data majemuk non-linear.
Contoh tree dalam bahasa java. Sumber : https://tutorialpemrograman.files.wordpress.com
Binary-Tree (Pohon Biner)
Binary-Tree adalah himpunan terbatas yang mungkin kosong atau terdiri dari simpul yang disebut root. Pohon biner terdiri dua himpunan terpisah yang merupakan pohon biner yang disebut sebagai sub-pohon kiri dan sub-pohon kanan pohon biner yang merupakan .
Pohon biner adalah jenis struktur data yang sangat penting dan sering ditemukan dalam berbagai aplikasi. Karakteristik yang dimiliki oleh pohon biner adalah bahwa setiap simpul memiliki paling banyak dua anak, dan mungkin tidak memiliki anak. Istilah yang digunakan sama dengan istilah pada pohon pada umumnya.
Grafik
Struktur data grafik adalah yang paling umum. Jika struktur linear memungkinkan kita untuk mendefinisikan keterhubungan yang berurutan antara entitas data. Maka pada struktur pohon data memungkinkan kita untuk mendefinisikan keterkaitan data secara hierarkis. Maka pada struktur grafik memungkinkan mendefinisikan koneksi tak terbatas antara entitas data.
