Senin, 06 April 2020

Pendahuluan Struktur Data


Struktur data merupakan suatau cara untuk menyimpan, menyusun , mengelompokan dan merepresentasikan suatu data. Struktur data merupakan hal yang sangat penting dan wajib dikuasai oleh seorang programmer. Maka pada bahasan kali ini saya akan merangkum beberapa struktur data yang sering digunakan saat menulis program.


1.ARRAY
Array adalah sebuah koleksi dari elemen atau sutau nilai yang dapat diidentifikasi dengan menggunakan indeks. Biasanya sebuah array disimpan dalam sebuah wadah berbentuk kurung siku “[]”. Indeks dari sebuah Array dimulai dari 0 sampai panjang array tersebut. Apabila aray nya berjumlah empat jadi indeksnya dimulai dari 0, 1, 2, 3 atau secara matematis bisa di tulis dengan 0 ≥ n-1. Dengan adanya indeks pada array memungkinkan untuk pengaksesan elemen secara acak (Random Acces).

Didalam array terdapat operasi untuk bisa add(menambakan), search( mencari) , remove(menghapus) dan read(membaca). Array disusun berderet. Ketika kita akan menambahkan sebuah elemen kedalam array maka kita akan menambahkan elemen tersebut ke indeks yang terakhir.

Untuk operasi membaca berarti tinggal di panggil indeks nya saja sampai keluar nilainya. Untuk operasi mencari sebuah nilai di dalam array maka di cari indeksnya terlebih dahulu kemudian kalo sudah ditemukan data bisa di hapus, di ganti, atau di tambhkan. Sedangkan untuk menghapus yah tinggal dihapus saja nilainya.

Ketika sebuah array sudah penuh index nya maka tidak bisa langsung menambahkan. Maka harus membuat array baru dan kemudian setelah ditambahkan elemen yang baru array sebelum akan dihapus. Dibawah ini merupakan contoh dari sebuah array dengan nama Array1.

Array1 = [1, 8, 29, 7]
Array2= [[2,1][3,2]]

Contoh diatas merupakan contoh dari sebuah array satu dimensi dengan nama Array1 dan array dua dimensi dengan nama Array2.
Contoh program Array

Array1 = [1, 8, 29, 7]
print(Array1[0]) #output 1
print(Array1[1]) #output 8Array1.append(10)# untuk menambah isi array dengan elemen 10
Array1.pop(2)# menghapus nilai di index ke 2
Array1.insert(0, 300) # memasukan niali 300 di index ke 0
Array1.index(29) # Mencari index yg berisi string nilai 29
Array1.sort() # Sorting dari value terkecil keterbesar
Array1.reverse() # Sorting value dari index terbesar keterkecil
print(len(Array1)) # Menampilkan jumlah total isi array


2.LINKED LIST
Linked list adalah struktur data yang terdiri dari suatu node yang dapat terhubung dengan node yang lain karena memiliki pointer/referensi. Dalam setiap node terdapat data dan referensi ke data selanjutnya atau sebelumnya. Linked list diibaratkan sebuah gerbong kereta api. Yang saling terhubung dan saling bergandengan. Node paling depan bisasanya disebut dengan head dan memiliki referensi ke node yang belakangnya sedangkan node terakhir memiliki referensi ke null.

Hubungan sebuah linked list bisa (singly) yaitu satu arah dan bisa bolak balik atau (doubly). Tidak ada unsur Random Access di dalam linked list via indeks seperti Array. Setiap operasi biasanya perlu operasi sekuensial dari node awal. Pembacaan node hanya bisa melalui proses sekuensial dari awal sampai akhir beberapa operasi yang terdapat dalam linked list adalah:
1. Insert di awal
2. Insert di akhir
3. Remove sebuah nilai
4. Remove node pertama
5. Traversing forward dan reverse (looping seperti gelombang)


3.STACK
Stack menurut bahasa artinya tumpukan. Secara istilah yaitu sebuah data struktur yang merepresentasikan sebuah proses LIFO (Last In First Out). Arti dari LIFO yaitu data yang terakhir datang maka yang pertama pergi. Sama seperti tumpukan piring yang sudah di cuci maka piring yang paling atas yang pertama diambil. Untuk penggunaan nya stack memakai tanda kurung “( )” .

Ada 3 operasi didalam stack ada yang namanya push (memasukan data), pop (membuang data), peak(melihat data). Pemanfaatan data struktur stack yaitu untuk nyari jalan keluar di maze. Stack akan selalu berhubungan dengan yang namanya fungsi rekrusif. Fungsi rekrusif yaitu fungsi untuk memanggil diri dia sendiri. Bisa disebut me-looping diri dia sendiri.


4. QUEUE

Queue (antrian) adalah struktur data dimana data yang pertama kali dimasukkan adalah data yang pertama kali bisa dihapus. Atau bisa juga disebut dengan struktur data yang menggunakan mekanisme FIFO (First In First Out). Semua sistem yang menggunakan sistem antrian itu adalah queque. Contoh nya antrian di teller bank, antrian di KFC dan antrian-antrian lainnya.

Operasi yang ada didalam queque hampir sama dengan stack hanya istilahnya yang berbeda. Memasukkan data (insert) disebut juga dengan enqueue. Menghapus data (remove) biasa disebut dengan istilah dequeue. Dan juga peek yaitu melihat yang adsa di antrian.


5. TREE
Tree merupakan data struktur yang berbentuk hirarki. Jadi hubungan antar node seperti organogram atau seperti silsilah keluarga. Tree ada banyak jenisnya setiap kepala sama seperti wadah data. Untuk mempermudah bisa ditandai dengan angka angka tiap tingkatnya.

Di dalam sebuah tree sebuah panah akan langsung menghubungkan dari atas ke bawah dari ayah ke anak nya (panah di gambar dalam pohon). Karena di dalam hubungan tree ayah mengetahui si anak tetapi si anak tidak dapat mengetahui ayah nya. Ada beberapa istilah di dalam tree yang pertama yaitu root(akar). Akar(root) adalah node/ simpul tanpa ayah. Biasanya terdapat satu root untuk sebuah tree.

Sebuah daun atau leaf adalah node yang tidak memiliki anak. Kedalaman sebuah node (depth) adalah panjang jalan dari root ke node.Himpunan semua node pada kedalaman yang diberikan kadang-kadang dinamai dengan Tingkat(Level) dari tree. Root memiliki kedalaman kosong.Tinggi sebuah pohon adalah panjang jalan dari akar ke daun-daunnya.Saudara adalah simpul yang memiliki ayah yang sama

Jika terdapat sebuah jalan dari node p ke node q, dimana node p lebih dekat ke root dari pada ke node q, maka p adalah leluhur dari q dan q adalah keturunan p. Lebar daris sebuah node adalah jumlah keturunan termasuk node itu sendiri. Setiap node pasti punya 2 linke edge. satu node hanya abisa didatangi satu link . Tapi satu node bisa mengeluarkan banyak link.


6. BINARY TREE
Binary tree merupakan struktur data tree yang maksimal anaknya ada 2. Tetapi harus secara parsial jadi semuanya tidak boleh ada yang lebih dari 2. jadi ada 3 tempat di tengah nya ada data terus ada alamat kiri nya dan kananya.
Ciri Khusus :
- Anaknya max 2 , (0,2)
-Bisa dinamain anaknya left sama right kalo gak punya anak adalah null
-Kalo node yang paling atas adalah root
-Kalo yang punya anak adalah parent
-Kalo yang punya parent berarti dia child
-Kalo yang bersebelahan disebut sibling

Secara struktur binary tree juga dibagi lagi menjadi beberapa :
-Strict BT : Kalo dia punya anak harus punya anak 2 atau tidak sama sekali.
-Complete BT : Harus complete anak nya dari yang kiri dulu sudah lengkap baru ke kanan nya.
-Perfect BT : Kalo perfect BT jadi dari anak yang kiri dan kanan harus lengkap dulu baru boleh punya anak lagi semuanya harus lengkap semua seperti membentuk sebuah segitiga.

Binary Search Tree 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. Balance BT beda dept nya maksimum bedanya 1.
Ada 3 cara untuk melakukan penulusuran atau traversal pada Binary Search Tree:
1. PreOrder : Print data, telusur ke kiri, telusur ke kanan
2. InOrder : Telusur ke kiri, print data, telusur ke kanan
3. Post Order : Telusur ke kiri, telusur ke kanan, print data


7. GRAPH
Graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis. Verteks menyatakan entitas-entitas data dan sisi menyatakan G = (V, E) Dimana :

G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x,y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E. Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal: Vx = {y | (x,y) -> E}

Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.
• Graph tak berarah (undirected graph atau non-directed graph) : Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA
• Graph berarah (directed graph) :Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.
• Graph Berbobot (Weighted Graph): Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.


8. Hash table
Hash table adalah struktur data yang digunakan untuk menyimpan pasangan key/value. Hash table menggunakan fungsi hash untuk melakukan komputasi pada indeks ke suatu array. Dengan menggunakan fungsi hash yang bagus, proses hashing dapat bekerja dengan baik. Di bawah asumsi yang wajar, waktu rata-rata yang diperlukan untuk melakukan pencarian elemen dalam hash table adalah O(1).

Sedangkan HashMap adalah class implementasi dar Map, Map itu sendiri adalah interface yang memiliki fungsi untuk memetakan nilai dengan key unik. HashMap berfungsi sebagai memory record management, dimana setiap record dapat disimpan dalam sebuah Map.
Kemudian setiap Map diletakkan pada vektor, list atau set yang masih turunan dari collection. HashMap sangat baik untuk menghandle result set dari query. Hal ini memungkinkan waktu eksekusi operasi dasar, seperti get() dan put(), tetap konstan bahkan untuk set yang besar.



Sumber : medium.com