Summary Data Structure

Linked list dalam Data Structure

Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL.

Linked List : artinya node-node tersebut saling terhubung satu sama lain. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Jenis Single LinkList :

• Single linked list dengan HEAD
  
• Single linked list dengan HEAD dan TAIL 
  

Pembuatan Single Linked List

 Keyword new gunanya untuk mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.

 public void buatNode (int dt) {
        Node nodebaru = new Node();
        nodebaru.data = dt;
        nodebaru.next = pointer;
        pointer = nodebaru;
    }

Double linked list

Double Link List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang.

Elemen double link list terdiri dari tiga bagian:

• Bagian data informasi
• Pointer next yang menunjuk ke elemen berikutnya
• Pointer prev yang menunjuk ke elemen sebelumnya

Ada 2 jenis Double Linked List yaitu :

•         Double Linked List Circular
•          Double Linked List Non Circular 

1.     Double Linked List Circular

Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:

1 field pointer yang menunjuk pointer berikutnya “next“,
1 field menunjuk pointer sebelumnya ” prev “,
1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

Ilustrasi Double Linked List Circular

2.     Double Linked List Non Circular

DLLNC "Double linked list non circular" adalah Double Linked List yang memiliki 2 buah pointer yaitu pointer next dan prev.
Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.

Pengertian: 
Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL.

-  Review penggunaan struct
 -  Perbedaan array dengan linked list
  -  Linked list Operation

Perbedaan array dengan linked list yaitu dimana kita memesan sebuah memory sebesar 100, kita hanya menggunakan sebanyak 15, tetapi kita harus membayar sesuai yang telah kita pesan (100). Sedangkan linked list yaitu dimana kita memesan sebuah memory sebesar 100, kita hanya menggunakan sebanyak 15, tetapi kita hanya membayar sesuai yang kita gunakan saja.

Linked list Operation

1.  Insert

           Ø Insert Front

  v Insert pada Single Linked List

Dimana kita ingin menambahan sebuah nilai baru ( curr ) di bagian depan. Contoh:

Langkah pertama yang harus kita lakukan membuat tali ikatan antara angka 35 dengan angka 6. Langkah selanjutnya yaitu memindahkan head ke angka 35. Contoh yang saya dapatkan di kelas lab:

 vInsert pada Double Linked List

   

 Ø  Insert Back

v  Insert pada Single Linked List

          Dimana kita ingin menambahan sebuah nilai baru ( curr ) di bagian depan. Contoh:

Langkah pertama yang harus kita lakukan membuat tali ikatan antara angka 35 dengan angka 77. Langkah selanjutnya yaitu memindahkan tail ke angka 35. Contoh yang saya dapatkan di kelas lab:

vInsert pada Double Linked List

12.   Pop/Delete ( Stact dan Queue )

  Ø  Stact

Stact adalah bagian tail yang akan di buang pertama kali atau dihilangkan. Contohnya:

 v  Stact pada Single Linked List

 v  Stact pada Double Linked List

  Ø  Queue

    Queue adalah bagian head yang akan di buang pertama kali atau dihilangkan. Contohnya:

 v  Queue pada Single Linked List

v  Queue pada Double Linked List

Hashing table & Binary Tree

1. Hashing
2. Hash Table
3. Hash Function
4. Collision 
5. Tree Concept
6. Binary Tree Concept
7. Type of Binary Tree
8. Property of Binary Tree
9. Expression Tree Concept
10. Threaded Binary Tree Concept

1. Hashing

Hashing adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda.Hashing adalah bentuk akses data yang efisien secara komputasi dan ruang penyimpanan yang menghindari waktu akses non-linear dari daftar dan pohon terstruktur yang dipesan dan tidak tersusun, dan persyaratan penyimpanan yang sering eksponensial untuk akses langsung ruang negara dari kunci besar atau panjang variabel.

2. 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).

    

      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

3. Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untk membangun fungsi hash:

1. Mid-square

Kuadratkan string/identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key. Jika kuncinya adalah string, itu dikonversi ke angka.

2. Division

Membagi string atau pengidentifikasi dengan menggunakan operator modulus. Ini adalah metode hashing integer yang paling sederhana.

3. Folding

Partisi string atau identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4. Digit Extraction

Digit yang ditentukan sebelumnya dari nonor yang diberikan dianggap sebagai alamat hash.

5. Rotating Hash

Menggunakan metode hash lalu setelah mendapatkan kode atau alamat hash dari metode tersebut, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

4. Collision

Ada 2 cara untuk menanggani :

1. Probing Linier

Cari slot kosong berikutnya dan letakkan talinya di sana. Pemeriksaan linear memiliki yang buruk kompleksitas pencarian jika ada banyak tabrakan.

2. Rantai

Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut). Jadi apabila terjadi tabrakan, kita hanya perlu beralih pada rantai itu.

5. Tree Concept

- Node di atas disebut sebagai root atau akar.

- Garis yang menghubungkan induk ke anak adalah edge atau garis.

- Node yang tidak memiliki anak disebut daun.

- Node memiliki orang tua yang sama disebut saudara.

- Derajat simpul adalah total sub pohon simpul.

- Tinggi atau kedalamanan tingkat maksimum node dalam pohon.

- Jika ada garis yang menghubungkan p ke q, maka p leluhurnya q, dan q adalah keturunan p.

6. Binary Tree Concept

Binary tree adalah structure data rooted tree dimana setiap node memiliki paling banyak 2 anak yaitu kanan dan kiri. Node yang tidak memiliki anak disebut daun. 

7. Type of Binary Tree

Ada 4 macam tipe:

1. Perfect Binary Tree

    Pohon biner dimana setiap level berada pada kedalaman yang sama.

2. Complete Binary Tree

    Pohon biner dimana setiap level, kecuali mungkin terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan.

3. Skewed Binary Tree

    Pohon biner dimana setiap node memiliki paling banyak satu anak.

4. Balance Binary Tree

    Pohon biner dimana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.

8. Property of Binary Tree

- Maximum number of nodes on level k of a binary tree is 2k
- Maximum number of nodes on a binary tree of height h is 2h+1 - 1.
- Minimum height of a binary tree of n nodes is 2log(n).
- Maximum height of a binary tree of n nodes is n - 1.

9. Expression Tree Concept

1. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.

Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.
2. Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.

10. Threaded Binary Tree Concept 

Pohon biner berulir sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL. Dalam representasi tertaut, sejumlah node berisi pointer NULL baik di bidang kanan atau kiri atau keduanya. Ruang yang terbuang untuk menyimpan tunjuk NULL ini dapat digunakan secara efisien untuk menyimpan kedamaian informasi bermanfaat lainnya.

                

Nama: Dewi Mutiara
NIM: 2301887830

Refrensi

Binus Maya
https://blog.triv.co.id/apa-itu-hashing/
http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-linked-list.html?m=1
Kelas kecil lab
https://www.coursehero.com/file/45253313/Double-Linked-List-Codedocx/