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