Rangkuman Materi Semester 2
Linked
List
A. Pengertian
Linked List merupakan
koleksi linear dari data, yang disebut sebagai nodes, dimana
setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat
didefinisikan pula sebagai kumpulan nodes yang
merepresentasikan sebuah sequence. Selain itu ada
beberapa istilah dalam linked list yaitu head dan tail.
- Head adalah elemen yang
berada pada posisi pertama dalam suatu linked list
- Tail adalah element yang
berada pada posisi terakhir dalam suatu linked list
B. Macam - macam Linked List
1. Single Linked List
Single
Linked List merupakan suatu linked list yang hanya memiliki satu variabel
pointer saja. Dimana pointer tersebut
menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.
Contoh
Codingannya:
struct
Mahasiswa{
char
nama[25];
int
usia;
struct
Mahasiswa *next;
}*head,*tail;
2. Double Linked List
Double
Linked List Merupakan suatu linked list yang memiliki dua variabel pointer
yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke
node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
Contoh
Codingannya:
Struct
Mahasiswa{
char
nama[25];
int
usia;
struct
Mahasiswa *next,*prev;
}*head,*tail;
3. Circular
Linked List
Circular
Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke
head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis
Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List
4. Multiple Linked
List
Multiple
Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel
pointer.
Perbedaan
Linked List dan Array
Linked List
|
Array
|
Koleksi linear dari elemen data
|
Koleksi linear dari node
|
Menyimpan data dalam lokasi memori yang
berurutan
|
Tidak menyimpan node dalam lokasi memori
yang berurutan
|
Dapat diakses secara acak menggunakan
indeks
|
Hanya dapat diakses secara berurutan
|
Jumlah memory dapat bertambah jika
dibutuhkan
|
Jumlah memory sudah fix sesuai jumlah array
yang di inisialisasi di awal
|
Memory
Allocation
Dalam C/C++, alokasi memory dapat dilakukan
dengan menggunakan malloc , sedangkan untuk dealokasi dapat
menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak
menghapus isi dari memory tersebut.
contoh penggunaan malloc:
int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*)
malloc(sizeof(struct Facebook));
contoh penggunaan free:
free(curr);
Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah
node/data baru.
Operasi
dalam Linked List :
1.
Push
Push
merupakan sebuah operasi insert dimana
di dalam linked list terdapat 2 kemungkinan insert, yaitu insert melalui depan
(pushDepan) ataupun belakang (pushBelakang). Operasi pushDepan berarti data
yang paling baru dimasukkan akan berada di depan data lainnya, dan sebaliknya
pushBelakang berarti data yang paling baru akan berada di belakang data
lainnya.
Representasinya adalah sebagai berikut:
- PushDepan: 5, 3, 7, 9 maka hasilnya adalah:
9 ->7 ->3 -> 5 -> NULL
- PushBelakang: 5, 3, 7, 9 maka hasilnya
adalah: 5 ->3 ->7 ->9 -> NULL
2.
Pop
Pop,
kebalikan dari push, merupakan operasi delete, dimana
di dalam linked list memiliki 2 kemungkinan delete, yaitu melalui depan (popDepan) dan melalui
belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data
paling depan, dan popBelakang berarti data yang akan dihapus adalah data paling
belakang (akhir).
Dalam
penerapan code single linked list, umumnya hanya digunakan pointer head sebagai
pointer yang menunjuk pada linked list. Namun dalam pembahasan artikel ini akan
digunakan 1 pointer tambahan, yakni TAIL untuk
menunjuk data terakhir di dalam linked list dalam mempermudah proses
pembahasan.
Stack and Queue
1. STACK(Tumpukan)
A. Pengertian Stack (Tumpukan)
Stack
(Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur
linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja
yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas
(parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik
(backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real,
record dalam bentuk sederhana atau terstruktur.
Stack
adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First
Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang
dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu
penambahan elemen baru (PUSH) dan penghapusan elemen dari tumpukan(POP).
Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan
menggunakan system LIFO (Last In First Out), artinya elemen yang terakhir masuk
itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan
(Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack
merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus
selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.
Sebelum
struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam
kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya
dengan menggunakan tata susunan linear (larik) dan sebuah variable, yang
dikemas dalam tipe data record. Stack (tumpukan) adalah struktur data bertipe
record yang terdiri dari field elemen, bertipe larik/array dengan indeks dari 1
sampai dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari
0 (saat kosong) sampai dengan MaksTum (Maksimum Tumpukan).
B. Operasi – operasi pada Stack (Tumpukan)
Operasi
yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi - operasi yang dapat diterapkan
adalah sebagai berikut :
1. Push : digunakan untuk menambah item pada Stack pada
Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada
Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah
elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka
semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah
Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah
Stack sudah penuh.
Pada
proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah
mencapai maksimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW,
artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam
Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen
yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya
tumpukan kosong tidak ada elemen yang dapat diambil.
C. Macam – macam Stack
1. Stack dengan Array
Sesuai
dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus
dimulai dari elemen teratas.
2. Double Stack dengan Array
Metode ini adalah teknik khusus yang
dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan
array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.
2. QUEUE (ANTRIAN)
A. Definisi Queue (Antrian)
Queue
merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack,
perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda.
Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada
bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer,
real, record dalam bentuk sederhana atau terstruktur.
Tumpukan
disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian
belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada
pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya
elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue
jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu
contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui
dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli
tiket.
Istilah
yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah
enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian
adalah dequeue.
B. Operasi-operasi pada Queue
1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah
elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen
maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari
antrian.
5. Clear : menghapus seluruh antrian
6. IsEmpty : memeriksa apakah antrian kosong
7.
IsFull : memeriksa apakah antrian penuh.
Hashing and Hash Table
Hashing digunakan sebagai metode untuk
menyimpan data dalam sebuah array agar penyimpanan data, pencarian data,
penambahan data dan penghapusan data dapat dilakukan dengan cepat. Ide
dasarnya adalah menghitung posisi record yang dicari dalam array, bukan
membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai
atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut
tabel hash (hash table). Hash table menggunakan struktur data
array asosiatif yang mengasosiasikan record
dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan
representasi dari record tersebut.
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.
Kelebihan dari hash table
antara lain sebagai berikut:
·
Hash table relatif lebih cepat
·
Kecepatan dalam insertions,
deletions, maupun searching relatif sama
Metode-metode
Hash Table yang sering digunakan adalah:
1. Linear probing
Apabila telah terisi, linear probing mencari alamat
lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat
yang belum terisi data, dengan rumus
(h+1) mod m.
2.
Quadratic probing / squared probing
Quadratic Probing mencari
alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih
kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat
menentukan sendiri formula yang akan digunakan.
3.
Double hashing
Sesuai dengan namanya, alamat baru untuk menyimpan data yang
belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function
lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh
hash function awal telah terisi tentu saja berbeda dengan hash function awal
itu sendiri.
Kelemahan dari closed hashing adalah ukuran array yang
disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori
yang lebih besar untuk meminimalkan collision.
Selain metode-metode yang sudah disebutkan di atas, terdapat
juga beberapa metode lain diantaranya :
1. Coalesced hashing
Gabungan dari chaining dan openaddressing. Coalesced hashing
menghubungkan ke tabel itu sendiri. Seperti open addressing, metode ini
memiliki keunggulan pada penggunaan tempat dan cache dibanding metode chaining.
Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih
menyebar, tetapi pada metode ini record yang disimpan tidak mungkin lebih
banyak daripada ruang yang disediakan tabel.
2. Perfect hashing
Jika record yang akan digunakan sudah diketahui sebelumnya,
dan jumlahnya tidak melebihi jumlah ruang pada tabel hash, perfect hashing bisa
digunakan untuk membuat tabel hash yang sempurna, tanpa ada bentrokan.
3. Probabilistic hashing
Kemungkinan solusi paling sederhana untuk mengatasi bentrokan
adalah dengan mengganti record yang sudah disimpan dengan record yang baru,
atau membuang record yang baru akan dimasukkan. Hal ini bisa berdampak tidak
ditemukannya record pada saat pencarian. Metode ini digunakan untuk keperluan
tertentu saja.
4. Robin Hood hashing
Salah satu variasi dari resolusi bentrokan double hashing.
Ide dasarnya adalah sebuah record yang sudah dimasukkan bisa digantikan dengan
record yang baru jika nilai pencariannya (probe count – bertambah setiap
menemukan tempat yang sudah terisi) lebih besar daripada nilai pencarian dari
record yang sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk waktu
yang diperlukan untuk pencarian.
Binary Tree dan Binary Search Tree
Tree
merupakan salah satu bentuk struktur data tidak linear yang menggambarkan
hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.
Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus
yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang
saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di
bawah akan diuraikan istilah-istilah umum dalam tree :
a. Prodecessor :
node yang berada diatas node tertentu.
b. Successor : node yang
berada di bawah node tertentu.
c. Ancestor : seluruh
node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d. Descendant : seluruh
node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e. Parent : predecssor
satu level di atas suatu node.
f. Child : successor satu
level di bawah suatu node.
g. Sibling : node-node
yang memiliki parent yang sama dengan suatu node.
h. Subtree : bagian dari
tree yang berupa suatu node beserta descendantnya dan memiliki semua
karakteristik dari tree tersebut.
i. Size : banyaknya node
dalam suatu tree.
j. Height : banyaknya
tingkatan/level dalam suatu tree.
k. Root : satu-satunya
node khusus dalam tree yang tak punya predecssor.
l. Leaf : node-node dalam
tree yang tak memiliki seccessor.
m. Degree : banyaknya
child yang dimiliki suatu node.
Binary
Tree didefinisikan sebagai struktur data yang memfasilitasi akses data yang
lebih cepat yang disimpan dalam memori sekunder dengan membuat dan menggunakan
indeks untuk mengakses sejumlah besar data. Ini mirip dengan menggunakan indeks
dalam buku untuk mengakses konten terkait secara cepat. Binary Tree cocok untuk
membuat kamus dengan menyimpan kunci dan catatan sehingga dengan menyediakan
kunci, seseorang dapat mengakses catatan yang sesuai.
Jenis-jenis Binary Tree :
·
Perfect
Binary Tree
adalah
binary tree yang di mana setiap level berada pada kedalaman yang sama.
· Complete Binary Tree
adalah
binary tree yang di mana setiap level, kecuali mungkin yang terakhir, terisi
penuh, dan semua node berada sejauh mungkin. Pohon biner sempurna adalah pohon
biner lengkap.
·
Skewed
Binary Tree
adalah binary tree di mana setiap node memiliki paling
banyak satu anak.
·
Balanced
Binary Tree
adalah binary tree di mana tidak ada daun yang lebih jauh
dari akar daripada daun lainnya (skema penyeimbang yang berbeda memungkinkan
definisi yang berbeda tentang "lebih jauh").
Binary
Search Tree (BST) adalah Binary Tree dengan sifat bahwa semua left child harus lebih
kecil daripada right child dan parentnya. Juga semua right child harus lebih
besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi
kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian
node tertentu dalam binary tree. Binary search tree memungkinkan
pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya,
bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian
table data dengan menggunakan informasi kunci atau key.
Aturan main Binary Search Tree :
- Setiap
child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child node sebelah kanan
harus lebih besar nilainya daripada root nodenya.
Operasi-operasi dalam Binary Search Tree
:
A. Searching
Pencarian
dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive
maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan
melakukan identifikasi root node. Bila root node null maka key yang dicari
tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah
membandingkan nilai key dengan node root tersebut. Bila nilai root node sama
seperti key yang dicari, maka nilai root node tersebut akan dikembalikan
sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan
ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga
key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah
selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus
terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau
setara dengan tinggi dari tree tersebut.
B.
Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai
secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan
nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga
berada pada node luar, untuk kemudian dilakukan penambahan data key baru.
Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive
memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi
kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan
nilai dari root tersebut.
C.
Deletion
Terdapat beberapa aturan dasar yang perlu diperhatikan dalam
langkah menghapus suatu node, yakni.
1. Bila node tersebut tidak
memiliki child, node tersebut dapat langsung dihapus
2. Bila node tersebut memiliki
child, maka node (parent) tersebut dihapus dan child dari node tersebut
menggantikan posisi dari node parent
3. Bila node tersebut memiliki
dua children, maka langkah pertama yang dilakukan ialah mengganti nilai node
parent dengan salah satu child, hapus nilai node parent awal, secara recursive
hapus nilai node child yang telah digunakan untuk mengganti nilai node parent
sebelumnya, kemudian lakukan seperti pada kasus pertama atau kedua
Suatu node
dengan children, lebih sulit untuk dihapus. Bila node child lebih besar dari
node parent yang digantikan maka disebut in-order successor. Sebaliknya bila
node child lebih kecil dari node parent yang digantikan, maka disebut in-order
predecessor.
