Rangkuman Before UTS

Linked List

Linked List Definition

A linked list is a dynamic data structure where a node is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a head and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front.

A Simple Linked List

Circular Single Linked list

In Circular Single Linked List, last node contains a pointer to the first node,We can have a circular singly linked list as well as a circular doubly linked list.There is no storing of NULL values in the list

Implementation

Insertion
A node can be added in three ways:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

2. Queue

Sistem queue adalah cara memasukin data dalam linked list secara pengantrian. jadi yang paling pertama keluar paling pertama. Jadi di sini kita mendefisini head dan tail untuk mendorong data sebagai data atas dan data paling bawah. karena 

berikut adalah contoh kodingannya. btw di bagian function node *newnode(int data) itu lupa letakkan return temp, karena dia setelah jalan yang mau dipakai adalah tempnya.

3. Stack 

yaitu tumpukan, konsepnya itu seperti tumpukan piring didalam kotak, jadi kalau mau ngambil keluar kita harus ambil yang paling atas,dimana piring yang paling terakhir dimasukan.

4.Hash

yaitu teknik mengisi data sesuai tempatnya di array.Yang pertama kita harus nyari dulu keynya dengan hashfunction dimana bisa berbagai macam function. terserah menurut kalian yang mana bagus. setelah mencari key  kita akan memasukin data tersebut ke dalam array dimana index si key tersebut.

Jadi bagaimana kalau keynya sama? ada 2 cara yaitu linear probing dan chaining. Yang bagus itu chaining, karena linear probing menyimpan data setelah array ke key tersebut. jadi kalau misalnya ada rak buku nih, tempat buku tersebut kalau sudah terisi, maka buku itu diletakkan disampingnya. jadi rak buku itu tidak bisa membesar.

Kenapa saya bilang chaining? karena chaining itu dia membuat linked list di array ke key tersebut untuk terus menyambungkan data tersebut dengan data lain dimana memiliki key yang sama. Hash function itu dibuat sesuai dengan size si rak buku yaitu hash table contoh hash func yang paling gampang adalah pembagian dimana keynya didapatkan dari data%size.

OH YAH HAMPIR KELEWATAN!

5. Postfix,Infix dan Prefix

itu apa? boleh dibilang penerapan di queue dan stack. jadi ini adalah soal matematika dasar seperti contohnya a + b * c, nah ini gimana diubah jadi postfix,infix dan prefix. Maksudnya diubah itu setiap karakter didalam string "a+b*c" akan dimasukan kedalam node berbeda.

  a. postfix. jadi postfix itu adalah penulisan operator seperti "*/+-" itu di tulis di paling belakang

jadi string "a+b*c" itu jadi kaya gini , "abc*+".

b. infix,kalau infix sih penulisan string seperti biasa "a + b *c" ini sudah termasuk infix.

b.prefix, prefix adalah penulisan operator di paling depan sehingga angka-angkanya tertulis paling belakang. contohnya ,"+a*bc",kenapa kalinya ditengah? karena perkalian diutamakan terlebih dahulu dalam melakukan aritmatika.

ini adalah contohnya, jadi kalo ada brackets seperti "()" maka akan diutamakan dulu -nya dalam postfix dan dalam prefix akan ditaro di tengah terlebih dahulu, baru perkalian, karena yang diutamakan adalah yang didalam brackets.

6. Binary Search Tree.

Sebetulnya ini lebih banyak ke rekursif sih. jadi mirip linked list cuman rantainya tuh ada root, left dan right. dimana root adalah data paling atas dan left adalah data yang lebih kecil dari root yang terletak di kirinya si root. dan right adalah data yang lebih besar dari root yang terletak di kanan si root. Jadi disini kita akan menganggap kalau root left dan right sudah penuh, kita menganggap left itu jadi root, jadi kita isi lagi bagian kiri itu jadi data lebih kecil dan kanan lebih besar. Ini akan terus berulang menggunakan rekursif. 

Sebetulnya BST ini harus lebih banyak simulasi sih.Jadi kalau hanya dijelaskan seperti ini jadi aneh.

Terus didalam penghapusan data di BST itu nyari data yang bisa menggantikan data tersebut dan tidak merusak aturan rantainya. Daripada pusing berikut adalah link simulasi BST boleh di coba.