Tugas Sebelum Uts


Linked List adalah salah satu bentuk struktur data, berisi kumpulan data
(node) yang tersusun secara sekuensial, saling sambungmenyambung,
dinamis dan terbatas.
- Linked List sering disebut juga Senarai Berantai
- Linked List saling terhubung dengan bantuan variabel pointer
- Masing-masing data dalam Linked List disebut dengan node (simpul) yang
menempati alokasi memori secara dinamis dan biasanya berupa struct
yang terdiri dari beberapa field.

1.Single Linked List Circular
 Single Linked List Circular 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.
Pengertian: 
Single : artinya field pointer-nya hanya satu buah saja dan satu arah. 
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
Ilustrasi Single Linked List Circular 
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
  berikutnya, dan juga memiliki field yang berisi data. 
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan 
  sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi 
  ke head.


2.Doubly Linked List
 "Double linked list non circular" adalah Double Linked List yang memiliki 2 buah pointer yaitu pointer next dan prev.
- Pointer next menunjuk pada node setelahnya.
- Pointer prev menunjuk pada node sebelumnya.

Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL.
 



Ilustras

-          Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

 3.Double Linked List Circular 
Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:

1 field pointer yang menunjuk pointer berikutnya “next“,
1 field menunjuk pointer sebelumnya ” prev “,
1 field yang berisi data untuk node tersebut . 
Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

Ilustrasi Double Linked List Circular
Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya
Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL
Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.
contoh Double Linked List Circular 
  
Add a node at the front


Add a node after a given node

  











Add a node at the end

Binary Search Tree
Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list
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.
Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:
§  Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.
§  Semua data dibagian kanan sub-tree dari node t selalu lebih besar atausama dengan data dalam node t.
Operasi: Insertion BST
  • Dimulai dari root
  • jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
  • jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
  • Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun Memasukan value (data) baru kedalam BST dengan rekrusif

Operasi: Delete ( Remove )
  • Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
  • Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
  • jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan)
 









Komentar

Posting Komentar