PENGERTIAN LINKED LIST
Linked list adalah sejumlah simpul (node) yang dikaitkan
dengan simpul yang lain dengan bantuan pointer dalam suatu urutan tertentu.
Suatu linked list dikatakan single linked list apabila hanya ada satu pointer
yang menghubungkan setiap node (satu arah “next”).
ATURAN LINKED LIST
Linked list mempunyai aturan:
1. Data harus
memiliki hubungan dengan yang lain.
2. Data yang
terhubung tidak boleh bercabang.
PERANCANGAN LINKED LIST
1. Single Linked
List
Tahapan pertama ialah membuat struct (karena setiap node
akan berbentuk struct) Dan memiliki satu buah fungsi pointer juga bertype
struct yang akan menghubungkan setiap node .
2. Double Linked
List
Lain Halnya dengan single List, double Linked List adalah
suatu linked list yang mempunyai 2 penunjuk ke data sebelumnya dan berikutnya,
memiliki 2 buah pointer, setiap node akan terhubung dengan pointer kanan dan
kiri.
PENJELASAN MENYIMPAN DATA PADA LINKED LIST
1 → 3 → 5 → 6 → 2 → 7
Pada linked list di atas, masing-masing data mempunyai
hubungan dengan data lain. Untuk bisa benar-benar menggunakan metode linked
list, kita harus mematuhi peraturan linked list. Setelah itu, kita harus
menetapkan di mana posisi head dan null berada. Head merupakan data yang tidak
memiliki hubungan di belakang, sedangkan null merupakan data yang paling
terakhir atau yang tidak memiliki hubungan di depannya. Setiap data harus
memiliki hubungan dengan data yang lain.
struct node
{
int data;
node* next;
};
PENJELASAN MENYISIPAKAN DATA PADA LINKED LIST
1 → 3 → 5 → 6 → 2 → 7
Melakukan penyisipan data pada linked list di atas,
dilakukan dengan cara menghapus rantai hubungan terlebih dahulu lalu memberikan
angka baru dan selanjutnya memberikan rantai hubungan baru.
Jika data di
tambahkan di tengah.
Misal kita akan memberi angka 2 di antara angka 1 dan 3.
Maka mula-mula kita harus memutus rantai hubungan antara angka 1 dan 3. Setelah
itu kita memberikan rantai hubungan baru dari angka satu menuju angka 2, dan
dari angka 2 menuju angka 3.
1è 2 è 3 → 5 → 6 → 2 → 7
Jika data di
tambahkan di awal.
Misal kita akan memberi angka 8 di awal. Maka mula-mula kita
harus menambahkan angka 8 di awal. Lalu setelah itu memindah posisi head ke
angka 8 karena angka 8 merupakan data yang pertama. Selanjutnya kita harus
menghubungkan angka 8 dengan angka 1 dengan menambahkan rantai hubungan antara
angka 8 dan angka 1.
8 è 1 → 3 → 5 → 6 → 2
→ 7
Jika data di
tambahkan di akhir.
Misal kita akan memberi angka 9 di akhir. Maka kita perlu
melakukan pemindahan null, karena null merupakan penanda akhir data.
Jadi mula-mula kita harus memberikan angka 9 setelah angka
7. Lalu menggeser posisi null ke posisi 9. Terakhir kita harus menghubungkan
angka 9 dengan angka 7 dengan memberikan rantai hubungan antara angka 9 dan
angka 7.
1 → 3 → 5 → 6 → 2 → 7è 9
MENGHAPUS DATA PADA LINKED LIST
4 → 1 → 3 → 5 → 6 → 8 → 10 → 2 → 7 → 0 → 11
Misal kita akan pelakukan penghapusan pada angka 5, angka 4,
dan angka 11. Maka yang kita lakukan tidaklah menghapus angka-angka tersebut
secara fisik, melainkan hanya melakukan pembelokkan arah sehingga angka-angka
tersebut tidak memiliki hubungan dengan angka sebelum atau sesudahnya.
Pertama kita akan menghapus angka 5. Jadi yang kita lakukan
cukup melakukan pembelokkan arah pada angka 5. Maksudnya, rantai hubungan yang
menuju angka 5 ( setelah angka 3 ) di buat berbelok dan tidak menuju angka 5.
Kita buat rantai tersebut menuju langsung ke angka setelah 5 yaitu angka 6.
Lalu rantai hubungan setelah angka 5 kita hapus.
Dengan begitu angka 5 masih ada secara fisik, tetapi tidak
ada secara tampilan. Karena memang angka 5 berubah sifatnya menjadi hidden atau
tersembunyi. Itu disebabkan angka 5 tidak di deklarasikan oleh rantai hubungan.
Kedua kita akan menghapus angka 4. Untuk menghapus angka 4,
caranya masih sama seperti menghilangkan angka 5. Tetapi pada angka 4 kita
mempunyai tambahan langkah. Yakni memindah posisi head ke angka selanjutnya
yaitu angka 1.
Setelah memindah head, kita cukup menghilangkan rantai
penghubung setelah angka 4 yang menuju angka 1. Dengan begitu angka 4 kini sama
dengan angka 5, yaitu tersembunyi dan tidak di deklarasikan.
Ketiga kita akan menghapus angka 11. Untuk menghapus angka
11, caranya mirip dengan menghapus angka 4. Tetapi yang kita pindah bukanlah
head tapi null yang berada di angka 11. Itu dikarenakan angka 11 merupakan
angka terakhir dan mempunyai null sebagai penanda.
Setelah memindah null ke angka sebelumnya yakni 0. Maka kita
harus menghapus rantai penghubung sebelum angka 11 yaitu setelah angka 0.
Dengan begitu angka 11 menjadi tidak terdeklarasikan dan tersembunyi.
Begitulah bagaimana cara menghapus angka yang berada di
awal, tengah, dan juga akhir. Secara fisik angka-angka tersebut tidak terhapus,
hanya saja angka tersebut dibuat tersembunyi dan tidak dideklarasikan.
MENGHAPUS DATA PADA LINKED LIST
3 → 5 → 10 → 7 → 0
Misal kita akan melakukan pembelokkan pada data di atas.
Maka kita harus melakukan proses
menghapus / memutuskan node 10 ke 7 dan 7 ke 0.
Kemudian membelokan node dari 10 ke 0.
Kemudian membelokan node 0 ke 7, blok 7 menjadi NULL karena
data terakhir.
Queue & Stack
Queue & Stack
Stack : Konsep utama dalam STACK adalah LIFO ( Last In First
Out ) (Pertama masuk akan keluar terakhir, begitu pula yang terakhir masuk akan
keluar pertama kali) yang apabila kita mengahapus/ keluar data, maka data yang
terakhirlah yang akan terhapus/ keluar terlebih dahulu, Tumpukan data yang
seolah-olah ada data di atas data lain, Suatu metode untuk Input dan hapus di
dalam memori komputer.
Contoh Stack : jika kita menghapus sebuah kalimat di dalam
dokumen menggunakan backspace, maka yang akan terhapus/keluar terlebih dahulu
adalah data yang paling akhir.
Ada angka yang masuk ke sebuah susunan : 1,2,3,4,5.
Maka yang akan keluar terlebih dahulu jika menggunakan
konsep stack ialah : 5,4,3,2,1.
Queue : Konsep utama dalam Queue adalah FIFO ( First In
First Out ), Antrian data yang seolah-olah ada data yang mengantri dari yang
terawal sampai yang terakhir, Suatu metode untuk Input dan hapus di dalam
memori computer.
Contoh Queue : saat kita mempunyai beberapa bola basket, dan
kita lempar bola itu ke ring, maka yang akan masuk terlebih dahulu adalah bola
yang pertama kita lempar
Dalam sebuah antrian memesan makanan menggunakan nomer
antrian : 1,2,3,4,5.
Maka yang akan keluar terlebih dahulu jika menggunakan
konsep Queue ialah : 1,2,3,4,5.
hash table
Pengertian Hash Tabel
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 table, 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).
Beberapa contoh operasi Pada Hash Tabel :
- insert:
diberikan sebuah key dan nilai, insert nilai dalam table
- 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
Struktur dan Fungsi pada Hash Tabel.
Hash table menggunakan struktur data array asosiatif yang
mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash)
yang merupakan representasi dari record tersebut. Misalnya, terdapat data
berupa string yang hendak disimpan dalam sebuah hash table. String tersebut
direpresentasikan dalam sebuah field kunci k.
Cara untuk mendapatkan field kunci ini sangatlah beragam,
namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk
menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function
dan menghasilkan indeks lokasi record dalam tabel.
k(x) = fungsi pembangkit field kunci (1)
h(x) = hash function (2)
Collision (Tabrakan)
Keterbatasan tabel hash menyebabkan ada dua angka yang jika
dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama. Hal ini
disebut dengan collision.
contoh: Kita ingin memasukkan angka 6 dan 29.
Hash(6) = 6 % 23 = 6
Hash(29)= 29 % 23 = 6
Collision Resolution Open Addressing
1. Linear Probing
Pada saat terjadi collision, maka akan mencari posisi yang
kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah,
hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti
HashTable sudah penuh.
2. Quadratic
Probing
Penanganannya hampir sama dengan metode linear, hanya
lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … )
3. Double Hashing
Pada saat terjadi collision, terdapat fungsi hash yang kedua
untuk menentukan posisinya kembali.
Collision Resolution Chaining
1. Tambahkan key
and entry di manapun dalam list (lebih mudah dari depan)
2. Kerugian:
Overhead pada memory tinggi jika jumlah entry sedikit
3. Keunggulan
dibandingkan open addressing:
- Proses insert dan remove lebih sederhana
- Ukuran Array bukan batasan (tetapi harus tetap
meminimalisir
collision: buat ukuran tabel sesuai dengan jumlah key dan
entry yang diharapkan)
Binary Search Tree (BST)
Binary Search Tree (BST)
Tree (pohon) adalah salah satu bentuk struktur data yang
menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to
many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai
percabangan atas dirinya, Berarti, binary tree adalah tree yang hanya dapat
mempunyai maksimal 2 percabangan saja.
Binary Search Tree (BST) adalah struktur data yang
mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node
sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula
sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada
root node, Tujuan struktur BST untuk memberikan efisiensi terhadap proses
searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya,
proses search akan lebih cepat berikut contoh Binary search tree :
Aturan main Binary Search Tree :
- Setiap child
node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child
node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Lalu, ada 3 jenis cara untuk melakukan penelusuran data
(traversal) pada BST :
- PreOrder :
Print data, telusur ke kiri, telusur ke kanan
- InOrder :
Telusur ke kiri, print data, telusur ke kanan
- Post Order :
Telusur ke kiri, telusur ke kanan, print data
