DATASTR

LINKED LIST

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.

Di dalam struktur data, ada 2 aspek yang kita pelajari, yakni tipe data dan structure (struct).
Tipe data merupakan kumpulan objek dan sebuah himpunan dari operasi-operasi yang menjalankan objek-objek terseubt.
Contoh tipe data pada integer, meliputi

·                     Objek: 0, -1, +2, dll.

·                     Operator: + , - , * , / , dll.   

Secara umum, structure merupakan kelompok tipe data yang dibentuk oleh user yang dapat menyimpan berbagai informasi dalam berbagai tipe data yang berbeda, sementara array hanya dapat menyimpan kumpulan data dalam tipe data yang sama.

Stack & Queue

Stack :

Last In First Out (LIFO).

Bisa diimplementasikan dengan :

Array (ada batasan , bisa looping di awal)

Linked list (tidak ad batasan, tidak bisa looping diawal).

Operasi pada stack:

Push (x) : menambah data dari paling atas.

Pop ( ) : membuang data dari paling atas.

Top ( ) : mengambil data dari paling atas. 

Pada stack kita juga di perkenalkan dengan :

Prefix (* 4 10) :

 Operator sebelum angka atau operand.

Infinix (4 * 10) : 

Operator diantara operand atau angka.

Postfix (4 10 *) : 

Operator di akhir. 

Ketiga hal ini merupakan bahasa komputer untuk proses perhitungan . Prefix, postfix dan infinix tidak menbutuhkan tanda kurung untuk setiap operasinya.

DFS (  Depth First Search)

DFS merupakam sebuah algoritma untuk melintasi atau mencari di pohon atau grafik. DFS dapat di implementasikan dengan fungsi rekursif atau prosedur berulang dari stack .Meskipun kedua hasilny agak berbeda karena proses jalannya tetapi keduanya menunjukkan hasil yang benar.

Queue :

1. Antrian.
2. Sistem First In First Out (FIFO).
3. Diimplementasikan dengan : 
•  Array 

Operasi pada stack:

Push (x) : menambah data dari paling belakang.

Pop ( ) : membuang data dari paling depan.

Top ( ) : mengambil data dari paling depan. 

Priority Queue :

Priority Queue adalah sebuah tipe data abstrak di mana masing-masing elemen diberi prioritas.

BFS (Breadth First Search) :

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Pada BFS menggunakan sistem dari Queue atau FIFO.

Hash Table & Binary Tree

Hash Table

Hashing

Sebelum mempelajari hash table kita harus mengetahui hashing terlebih dahulu. Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil data dalam waktu yang cepat. Dalam kasus ini teknik hashing mengubah sebuah karakter string menjadi ukuran yang lebih kecil atau sebuah kunci yang merepresentasikan string aslinya. hashing juga dapat diartikan sebagai pembagian kunci ke sebuah array yang disebut hash table dengan menggunakan fungsi yaitu hash function.

Hash table

hash table merupakan suatu tempat atau array dimana digunakan sebagai tempat penyipanan string aslinya. di hash table kita menyimpan data sebagai array yang dimana setaip datanya memiliki sebuah indeksnya masing - masing. Jadi karena hal ini kita dapat mengakses data dengan sangat cepat. 

Binary Tree dan Tree

                Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di antara objek data. Beberapa hubungan dalam tree dapat diamati dalam struktur direktori atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

Tree memiliki elemen-elemen:

·                              Node

·                              Node paling atas disebut root

·                              Node yang tidak memiliki children (anak) disebut leaf (daun)

·                              Node yang memiliki parent yang sama disebut sibling

·                              Degree (tingkat) dari suatu node merupakan total subtree dari node

·                              Height/depth merupakan degree maximum dari node dalam tree

·                              Jika terdapat suatu garis yang menghubungkan p ke q, maka p disebut ancestor (leluhur) dari q, dan q merupakan descendant (keturunan) dari p.

STACK & QUEUE

Stack

            Secara harafiah, stack berarti tumpukan. Dalam struktur data, stack merupakan salah satu metode pengaturan data yang menggunakan sistem Last In First Out (LIFO). Data yang terakhir masuk, akan lebih dulu keluar/digunakan. Sebalikanya, data yang pertama masuk, akan keluar/digunakan terakhir. Sebagai gambaran, ketika anda menumpuk piring, piring yang pertama kali akan terletak di bawah piring kedua, dan seterusnya sampai piring yang terakhir berada di paling atas. Kemudian, saat anda ingin mengambil sebuah piring, tentunya anda akan mengambil piring yang paling atas. Piring pertama tadi akan terus berada di paling bawah sampai akhirnya mendapat giliran diambil.

           

            Operasi-operasi yang digunakan pada stack:

·         Push() à Menambah data baru ke paling atas

·         Pop() à Menghapus data dari paling atas

·         Top() à Mengambil data paling atas (disebut juga peek)

Dalam pengoperasiannya, ada 3 jenis operasi perhitungan:

·         Infix à operasi perhitungan dengan susunan operand dan operator yang berurutan

Contoh: 4 + 6 (5-2) / 3

·         Prefix à operasi perhitungan dengan susunan operator berada di sebelah kiri dari operand, komputer akan memprosesnya dari kanan ke kiri.

Contoh: mengubah 4 + 6 (5-2) / 3 ke prefix kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi

4 + 6 * (5 – 2) / 3        Operator ( ) merupakan operator tertinggi

- 5 2

4 + 6 * (5 – 2) / 3        Operator * merupakan operator tertinggi

* 6 - 5 2

4 + 6 * (5 – 2) / 3        Operator / merupakan operator tertinggi

/ * 6 – 5 2 3

4 + 6 * (5 – 2) / 3        Operator + adalah operator terakhir

+ 4 / * 6 - 5 2 3

·         Postfix à operasi perhitungan dengan susunan operator di sebelah kanan dari operand, komputer akan memprosesnya dari kiri ke kanan

Contoh: mengubah 4 + 6 (5-2) / 3 ke postfix kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi.

4 + 6 * (5 – 2) / 3        Operator ( ) merupakan operator tertinggi

5 2 -

4 + 6 * (5 – 2) / 3        Operator * merupakan operator tertinggi

6 5 2 - *

4 + 6 * (5 – 2) / 3        Operator / merupakan operator tertinggi

6 5 2 - * 3 /

4 + 6 * (5 – 2) / 3        Operator + adalah operator terakhir

4 6 5 2 - * 3 / +

Queue

                Secara harafiah, queue berarti antrian. Queue merupakan salah satu metode pengaturan data yang menggunakan sistem First In First Out (FIFO). Data yang pertama masuk, akan lebih dulu keluar/digunakan. Sebaliknya, data yang terakhir masuk, akan keluar/digunakan terakhir juga. Sebagai gambaran, ketika anda mengantri di sebuah loket untuk membeli karcis, maka anda akan mengantri terlebih dahulu, ke bagian paling belakang. Orang yang berada di paling depan akan dilayani terlebih dahulu, dan akan pergi saat itu juga. Lalu dilanjutkan orang kedua, sampai giliran anda (ketika tidak ada orang lagi) di bagian terakhir. Begitu juga dengan data. Data yang dimasukkan pertama akan berada di posisi paling depan/atas/kiri. Lalu ketika ingin menghapus data (pop) atau mengambil data paling atas (top), maka data pertama yang masuk duluan tadi akan diproses di awal.

            Operasi-operasi yang digunakan pada queue:

·         Push() à Menambah data baru ke paling belakang

·         Pop() à Menghapus data dari paling atas/depan

·         Top() à Mengambil data paling atas/depan

Hash table & Binary Tree

Dalam komputasi , tabel hash ( peta hash ) adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif , struktur yang dapat memetakan kunci ke nilai . Tabel hash menggunakan fungsi hash untuk menghitung indeks , juga disebut kode hash , ke dalam array dari ember atau slot , dari mana nilai yang diinginkan dapat ditemukan.

Meja hash
Tipe	Array asosiatif tidak teratur
Diciptakan	1953
Kompleksitas waktu dalam notasi O besar
Algoritma Rata-rata Kasus terburuk Ruang O ( n ) [1] O ( n ) Cari O (1) O ( n ) Memasukkan O (1) O ( n ) Menghapus O (1) O ( n )

Buku telepon kecil sebagai tabel hash

Idealnya, fungsi hash akan menetapkan setiap kunci ke bucket unik, tetapi sebagian besar desain tabel hash menggunakan fungsi hash yang tidak sempurna, yang dapat menyebabkan benturan hash di mana fungsi hash menghasilkan indeks yang sama untuk lebih dari satu kunci. Tabrakan semacam itu selalu diakomodasikan dalam beberapa cara.

Dalam tabel hash berdimensi baik, biaya rata-rata (jumlah instruksi ) untuk setiap pencarian tidak tergantung pada jumlah elemen yang disimpan dalam tabel. Banyak desain tabel hash juga memungkinkan penyisipan sewenang-wenang dan penghapusan pasangan nilai kunci, pada ( diamortisasi ^[2] ) biaya rata-rata konstan per operasi. ^[3] [4]

Dalam banyak situasi, tabel hash ternyata rata-rata lebih efisien daripada pohon pencarian atau struktur pencarian tabel lainnya. Untuk alasan ini, mereka banyak digunakan dalam berbagai jenis perangkat lunak komputer, terutama untuk array asosiatif , pengindeksan basis data , cache , dan set .

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.

Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.