Jasono

Review

Materi tentang Linked List

Jadi, apa itu linked list , linked list itu adalah Linked List adalah suatu struktur data linier. Berbeda dengan array yang juga merupakan struktur data linier dan tipe data komposit, linked list dibentuk secara dinamik. Pada saat awal program dijalankan elemen linked list belum data. Elemen linked list (disebut node) dibentuk sambil jalan sesuai instruksi. Apabila setiap elemen array dapat diakses secara langsung dengan menggunakan indeks, sebuah node linked list diakses dengan menggunakan pointer yang mengacu (menunjuk) ke node tersebut.

1.Circular single linked list

Circular Single Linked List adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,

maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.

Image result for circular doubly linked list

2.Double linked list

Pengertian Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prevdan next. Node pada Double Linked List

Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.

Untuk membuat Linked List , kita perlu membuat Struct menyimpan Data.

struct node {

int value;

node *next,*prev;

}*head,*tail;

jadi , kita harus mengalokasikan node baru / mengalokasikan memori dan menentukan nilainya.

Untuk mengakses Malloc , kita memerlukan library stdlib.h

node *newNode(int value) {

node *curr= (node*)malloc(sizeof(node));

curr->value=value ;

curr->next=curr->prev=NULL;

return curr;;

}

3.Circular double link list

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Operasi-Operasi yang ada pada Linked List :

– Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

– IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

– Find First

Fungsi ini mencari elemen pertama dari linked list

– Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

– Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

– Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

– Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalahelemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

– Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

– Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

STACK And QUEUE

Stack

Stack memakai sistem LIFO atau last in first out (yang pertama masuk akan keluar terakhir, begitu pula yang terakhir masuk akan keluar pertama kali) yang apabila kita mengahapus/ keluar data, maka data yang terakhirlah yang akan terhapus/ keluar terlebih dahulu.

Operasi pada stack :

§ Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.

§ Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

§ Clear : digunakan untuk mengosongkan Stack.

§ Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.

§ MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.

§ IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

§ Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

prefix, infix dan postfix

prefix adalah operator yang ditulis sebelum operand.berikut adalah contoh prefix: *5 10.

infix adalah operator yang ditulis di antara operand. berikut adalah contoh infix: 3 * 8.

postfix adalahoperator yang ditulis setelah operand. berikut adalah contoh postfix: 9 3 *.

Queue

queue memakai siste FIFO atau first in first out (yang pertama masuk akan keluar pertama, begitu pula yang masuk terakhir akan keluar terakhir) yang apabila kita menghapus / mengeluarkan data, maka data yang pertamalah yang akan terhapus/ keluar terdahulu dan data yang terakhir akan terhapus/ keluar terakhir.

Operasi pada Queue :

§ Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.

§ Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

§ EnQueue : berfungsi memasukkan data kedalam antrian.

§ DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.

§ Clear : Menghapus seluruh Antrian

§ IsEmpty : memeriksa apakah antrian kosong

§ IsFull : memeriksa apakah antrian penuh.

HASHING

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

Operasi Pada Hash Tabel

Ø insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

contohnya ;

jika ingin menyimapan nama kata, maka kita dapat menyimpan karakter pertama dari setiap string menjadi angka sehingga

Tahap Tahap Membuat Hash Table :

1. Inisialisasi

2. Menambah Element Baru

3. Menghapus Sebuah element

4. Searching , teknik pencarian pada hash table yaitu mencari nilai hash yang sesuai menggunakan deklarasi sama seperti pada linked list. Jika data tidak

ditemukan maka menggunakan return NULL .

5. Resizing , Jumlah element pada hash table tidak selalu diketahui ketika terjadi penambahan data

Collision

Collision adalah 2 atau lebih kunci memiliki hash code yang sama , yang membuatnya tabrakan atau rebutan.

cara mengatasi Collision:

-Linear Probing

-Chainin.

Binary Tree

Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

Lalu, ada lagi yang namanya Binary Tree. Apa bedanya? Sebenarnya sama sama konsepnya denganTree. Hanya saja, kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan).Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja. Untuklebih jelasnya, lihat gambar di bawah ini.