Rangkuman Data Struct

1.Circular Single Linked List

Dalam linked list ini , tidak ada ada "last node" ,jika sudah sampai ke node terakhir , akan berisikan pointer node pertama , sehingga tidak ada node yang berisikan NULL value. Semua node dalam Circular Single Linked List dapat menjadi starting point.

2.Doubly Linked List

Di dalam Doubly Linked List,setiap node memiliki 2 link , 1 untuk menuju ke node selanjutnya , 1 nya lagi untuk menuju ke node sebelumnya.

seperti kita lihat di gambar , jika single linked list memiliki 1 kotak , sedangkan doubly linked list memiliki 2 kotak berisi next dan previous.


2.1 Doubly Linked List Insertion

Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert depan dan insert dari belakang. Insert dari depan akan memasukan data paling baru ke depan data sebelumnya , jika insert dari belakang berarti akan menempatkan data paling baru ke belakang data sebelumnya . Contoh : 

 1. Insert dari depan : 1 ,2 ,3 ,4 maka hasilnya akan mejadi 4,3,2,1

 2. Inser dari belakang : 1,2,3,4 maka hasilnya akan 1,2,3,4

2.2 Doubly Linked List Deletion
Pop merupakan operasi delete diaman ada 2 cara yaitu pop dari depan , berarti akan mengahapus data yang paling depan , sedangkan pop belakang akan menghapus data dari paling belakang.

Operasi pop dari depan

Operasi pop dari belakaang

3.Circular Doubly Linked List
 Circular Doubly Linked List hampir sama seperti CIrcular Single Linked List , akan tetapi setiap node memiliki 2 pointer yaitu next dan previous.

 Hash Table

       Hashing adalah metode untuk menyimpan data di alam sebuah array agar penyimpanan, pencarian , penambahan , dan penghapusan data dapat dilakukan dengan cepat.Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

                              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

 Kelebihan Dari Hash Table :

1.waktu akses relatif cepat

2.kecepatan insertion dan eletion relatif sama

3.cocok untuk merepresentasikan data dengan frekuensi insert, delete , dan search yang tinggi.

Kelemahan Dari Hash Table :

1.sering ditemukan hash table yang recordnya bertabrakan

2.tidak efisien mencetak seluruh elemen pada table hash

3.tidak efisisne untuk mencari elemen maksimum dan minimum

contoh coding fungsi hash :

int hash(String key, int tableSize) 

{ 

    int hashVal = 0; 

    for (int i=0; i < key.length(); i++) 

        {

             hashVal = (hashVal * 128 + key.charAt(i)) % tableSize; 

        } 

              return hashVal % tableSize; 

}

Binary Tree

   Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

     Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary treemaksimumnya berjumlah 2n-1. 

Binary Search Tree

BST ( Binary Search Tree ) memiliki ciri-ciri :

• Setiap node mempunyai value dan tidak ada value yang double
• value yang ada di kiri tree lebih kecil dari rootnya
• value yang ada di kanan tree lebih besar dari rootnya
• kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

Operasi dalam BST : 

1.Search 

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

2.insertion:

• Dimulai dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
• Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

contoh  

Kita ingin menambahkan value 35 kedalam BST yang sudah ada

yang berwarna hijau adalah root , setiap menginsert , mencari , atau delete selalu di mulai dari root.

dan new node berwarna orange yang memiliki value 35, kemudian kita cek dengan root(30), maka 30 .. 35 ?  karena 30 < 35 maka , node lebih besar dari root kemudian kita arahkan ke sub-tree yang berada di kanan dan kemudian cek ulang kembali

Sekarang kita cek 35 dengan 37 , maka 35 < 37 jadi kita arahkan ke bagian kiri dan kita cek kembali , karena di bagian kiri sudah ada value yaitu 32

kemudian kita cek 32 dengan 35 , ternyata 35 > 32 jadi kita masukan ke kanan , dan ternyata kita sudah menemukan tempat kosong untuk mengisi new node(35) jadi kita masukan 35 di sebelah kanan dari node(32)

3.Deletion

• Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan)

contoh : 

 Delete value(30) , value 30 adalah root dari BST , memiliki 2 anak sama seperti case sebelumnnya “Kiri , anak paling kanan atau kanan anak paling kiri”.

jadi kita bisa ambil ( 26 atau 31 ) untuk menggantikan root(30)

Heap and Tries

Heap adalah complete binary tree (bukan binary search tree) yang mempunyai 2 properties yaitu :

1.Min heap

dalam min heap disimpulkan parentnya merupakan nilai terkecil , dan nilai terbesar berada dalam salah satu leaf / anaknya.

contoh :

 .

Insertion Min heap :

dalam menginsert di min heap , kita menaruh anak di tempat setelah terakhir , jika anak tersebut lebih kecil dari parentnya , maka di tukar.

Deletion Min heap :

Node yang di delete adalah root (karena nilainya paling kecil) lalu di gantikan oleh node yang terakhir kali di insert dan di sesuaikan dengan properties secara rekursif.

2.Max heap

node paling atas adalah node yang terbesar , dan node terkecil berada salah satu leaf / anaknya.

Insertion Max heap :

dalam menginsert di min heap , kita menaruh anak di tempat setelah terakhir , jika anak tersebut lebih besar dari parentnya , maka di tukar.

Deletion Max heap :

menukar anak kiri atau kanan dari root dengan node terakhir dari heap lalu hapus. Lalu downheapmax dari node tersebut.

3.Min-Max heap :

gabungan dari min dan max , dalam konsep ini root akan bernilai terkecil , selanjutnya akan bernilai maksimum , lalu minimum lgi ,dan seterusnya

insertion Min-max heap :

• Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level.
• Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
1. Parent
2. Grand Parent

Deletion Min - max heap :

• Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
• Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
1. Grand child
2. Child ( grand child disesuaikan dengan parentnya)

Tries
Berasal dari kata reTRIEval yang berarti untuk menyimpan asosiatif array dan jika dalam aplikasinya trie concept ini seperti auto-complete

• Properties pada tries:
• Setiap vertex/node merepresentasikan satu huruf
• Root merepresentasikan karakter kosong

.

Nama : Joviandy Widyananda

NIM : 2301846225