review 1 semester

Linked List

dalam linked list dibutuhkan malloc untuk alokasi value ke memory yang berbeda

Pointer next dibuat untuk menyimpan data setelahnya, struct data untuk recursive

Indikator posisi awal dengan if head==NULL

Pergeseran dilakukan dengan next->curr

Tail->Next==NULL Sebagai penanda akhir list

Next adalah alamat curr setelah bergeser

Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya

Double Linked List

Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya

Keuntungan Double linked List

1.       Implementasinya tidak jauh berbeda dari Single linksed list

2.       Mampu bergeser dua arah

3.       Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan dihapus. Double linked list hanya butuh pointer node yang ingin dihapus

4.       Bisa di allocate dan di deallocate dengan lebih mudah

5.       Salah satu data structures yang paling efisien jika pergeseran dengan dua arah dibutuhkan

Aplikasinya

                Navigasi

                Back/forward pages di browser

                Undo/redo

Stack & Queue

Stack/tumpuk merupakan LIFO (Last In First Out) karena hanya memiliki head/kepala. Jika digambarkan, seperti tumpukan piring.

Jika ditambah, piring paling baru ada di paling atas, dan saat diambil, piring paling atas lah yang terambil terlebih dahulu. Jika diasumsikan hanya dapat mengambil/menambah satu piring secara berurutan, maka Stack hanya mengenal kepala/Top/Head, dan piring-piring setelahnya.

Di sisi lain, Queue merupakan FIFO (First In, First Out), karena memiliki head dan tail, jika digambarkan, seperti barisan piring

Stack

Stack dalam Data Structure merupakan struktur yang cara penambahan/penghapusan melalui satu end saja, yaitu kepala/head. Seperti penjelasan awal, Push/Insert data dimasukkan dari depan, begitu juga Pop/Delete

Kegunaan Stack

konsep Stack dalam aplikasi adalah undo/redo browser. Ketika halaman baru dibuka, maka dilakukan insert, dan ketika undo, maka akan dilakukan pop dari halaman sekarang/head. Konsep Stack untuk undo/redo juga diaplikasikan di beberapa text editor.

Queue

Queue dalam Data Structure merupakan struktur yang cara penambahan/penghapusan melalui dua end, yaitu kepala/head dan ekor/tail.  Push/Insert data dilakukan di head/kepala, dan penghapusan dilakukan di ekor/tail.

Kegunaan Queue

Penggunaan Queue ada dalam CPU Scheduling, Multiprogramming, dan asynchronous data transfer. Dalam sehari-hari, seperti urutan panggilan di call center, dan antrian kasir=987tea

Hash Table

Hash table merupakan suatu metode dalam struktur data untuk melakukan pencarian secara cepat menggunakan key untuk mencari value.

Hashing

Key yang digunakan dikonversi ke dalam suatu angka, dan dilakukan proses hashing sehingga angka tersebut menghasilkan angka 0-9

Ada beberapa metode hashing, yaitu :

• Mid-Square
• Division
• Folding
• Digit Extraction
• Rotating Hash

Collision

Dalam metode hashing bisa terdapat nilai yang sama, untuk mengatasi hal itu digunakan collision.

Ada beberapa metode collision, yaitu :

• Linear probing
• Double hashing
• Chaining

BINARY TREE

Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).

Pohon binar (binary tree) adalah himpunan simpul yang terdiri dari 2 subpohon (yang disjoint / saling lepas) yaitu subpohon kiri dan subpohon kanan.Setiap simpul dari pohon binar mempunyai derajat keluar maksimum = 2.

Pendefinisian pohon  binar bersifat rekursif. Pohon binar acapkali disajikan dalam bentuk diagram.

 

Sebuah pohon binar T didefinisikan terdiri atas sebuah himpunan hingga elemen yang disebut simpul(node), sedemikian sehingga :

a.T adalah hampa (disebut pohon null) atau;

b.T mengandung simpul R yang dipilih(dibedakan dari yang lain), disebut “akar: atau “roof” dari T, dan simpul sisanya membentuk 2 pohon binary (subpohon kiri dan subpohon kanan dari akar R).

Terminologi Pada Pohon Binar

Terminologi hubungan keluarga banyak digunakan dalam terminology pada pohon binary. Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan suksesor kanan , serta istilah ayah untuk pengganti prodesesor. Selain itu juga istilah saudara (brother) yang diberikan kepada kedua simpul yang mempunyai ayah yang sama. Jelas bahwa setiap simoul kecuali akar mempunyai ayah yang tunggal.

Pohon Binar Lengkap

Setiap simpul dari pohon binary paling banyak mempunyai dua anak. Suatu pohon binar T dikatakan lengkap atau complete, bila  setiap tingkatnya kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin yakni 21 simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul dibagian kiri pohon. Jadi, pohon binary lengkap dengan simpul, T adalah tunggal(dalam hal ini mengabaikan label simpul).

Pohon-2

Pohon Binar T dikatakan pohon-2 atau pohon binar yang dikembangkan(extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini, simpul dengan dua anak disebut simpul internal, sedanglan simpul tanpa anak disebut simpul eksternal. Dalam diagramnya, seringkali diadakan perbedaan antara simpul internal dan eksternal. Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.

Penyajian Pohon Binar Dalam Memori

Kita dapat menyajikan suatu pohon binary T dalam memori dengan dua cara. Cara pertama adalah penyajian kait (link).  Cara ini biasa digunakan. Ia analaog dengan cara list berkaitan (linked list) ketika disajikan dalam memori. Cara kedua adalah dengan menggunakan sebuah array tunggal disebut penyajian sekuensial T.

 

Kebutuhan utama yang harus dipenuhi pada setiap penyajian T bahwa seseorang dapat mempunyai akses langsung ke akar R dan T, bila diberikan sembarang simpul N, seseorang harus dapat akses langsung ke anak dari N.

Stack (Tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack.

Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain.

Queue (Antrian) sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan.