PREV ELEMEN KEDUA

list kosong

menghapus elemen dari list L, baru nilai yang di hapus di assign ke X

prev dari elemen pertama dan next dari elemen terakhir selalu NIL

First L dan Last L bernilai sama

kasus biasa

satu-satunya adalah elemen last jadi cuman satu elemen dan dihapus jadi LIST KOSONG.

maju dulu

akan selalu mengikuti last, satu langkah di belakang last

elemen dummy akan berganti menjadi elemen dummy yang lain

tanpa while loop HARUSNYA LEBIH EFISIEN. Jadi elemen baru akan dicopy ke dummy yang sudah ada dan akan dibuat node baru untuk dummy yang ditunjuk oleh dummy yang menjadi elemen

alokasi

jadi x itu udah pasti ditemukan, baik ditemukan di elemen (berarti ketemu) atau ketemu di dummy (ga ketemu).

x jadi elemen dummy dan berfungsi sebagai sentinel

tidak penting angkanya berapapun karena info dummy ga penting

ini namanya MAKRO selector

Oke, kita sederhanakan ya! 😊

Kenapa ADT List Linear Pakai Tag (tNode):

• Karena ada pointer ke dirinya sendiri!
• Di list linear, next itu adalah pointer yang menunjuk ke struct yang sama (struct tNode).
• Compiler butuh nama/tag (tNode) untuk ngerti kalau next menunjuk ke dirinya sendiri.

Contoh: c typedef struct tNode { ElType info; // Data di node Address next; // Pointer ke struct tNode lain } Node; Kalau tanpa tag, compiler bingung karena belum selesai baca tipe struct-nya.

Kenapa ADT Stack Nggak Butuh Tag:

• Karena nggak ada pointer ke dirinya sendiri.
• Stack cuma punya array (buffer) dan variabel biasa (idxTop), nggak ada elemen yang menunjuk ke struct Stack.
• Jadi, tag nggak diperlukan.

Contoh: c typedef struct { ElType buffer[CAPACITY]; // Array penyimpan elemen int idxTop; // Penunjuk elemen teratas } Stack;

Perbedaannya:

• List Linear: Pakai pointer ke struct yang sama → butuh tag.
• Stack: Nggak pakai pointer ke dirinya sendiri → nggak butuh tag.

Udah lebih jelas, kan? 😄

• Elemen pertama prev nya adalah elemen terakhir
• Next dari elemen terakhir adalah elemen pertama.

Kalo NIL gaakan punya panah next/prev

selain ada pointer next, ada previous untuk nunjuk ke elemen sebelumnya

bisa maju mundur semuanya karena kalo yg biasa ga bisa mundur

tapi ini harus dibayar cukup mahal karena butuh memory yang lebih besar

kalo ini sbnenrnya kita gapunya FIRST karena list selalu muter.

Keunggulan: Bisa melakukan instruksi secara terus menerus

Next dari elemen terakhir == address dari First(L)

Akses elemen pertama cukup First(L)

Elemen terakhir berarti memiliki next address diri dia sendiri

Elemen yang menunjuk dummy terakhir

Elemen yang sebelumnya next dari dummy pertama

lebih berguna ini karna kalo yang naro dummy di akhir doang tetep harus di traversal dari awal sampe akhir (next elemen p == address dummy)

sama kaya tadi cuman ditaruh diakhir.

dummy disini berlaku seperti sentinel. (mark)

Elemen terakhir adalah elemen sebelum dummy (jika next elemen p merupakan address dari dummy)

Tentu! Berikut penjelasan dengan bahasa simpel dan poin-poin:

Apa itu Dummy Element?

• Elemen kosong di awal list.
• Tidak menyimpan data penting.
• first selalu menunjuk ke dummy element (tidak pernah berubah).

Kenapa Dummy Element Ada?

• Sederhanakan Algoritma:
• Kalau ada insert di awal (insert first), kita nggak perlu ubah pointer first. Fokusnya hanya pada elemen setelah dummy.
• List Kosong Tetap Punya Dummy:
• Dummy element bikin list kosong tetap terstruktur (nggak perlu bikin kondisi khusus).
• Konsistensi:
• Operasi seperti insert/delete lebih seragam karena selalu mulai dari dummy.

Cara Kerja Dummy Element:

• Elemen pertama yang "asli" adalah di first.next, bukan di first.
• Kalau list kosong, first.next = null (dummy tetap ada).

Keuntungan:

• Nggak Perlu Banyak Kondisi:
• Misal, kalau list kosong, tetap ada dummy, jadi kode lebih simpel.
• Kurangi Kesalahan:
• Pointer first nggak pernah berubah, jadi aman.
• Operasi Insert/Delete Lebih Mudah:
• Fokus langsung ke elemen setelah dummy tanpa repot atur pointer first.

Contoh Insert First:

• Tanpa Dummy:
• Harus ubah first ke elemen baru.
• Periksa kalau list kosong dulu.
• Dengan Dummy:
• Tinggal atur first.next ke elemen baru.
• Pointer first nggak usah diubah.

Dummy element itu intinya biar kode lebih simpel, aman, dan seragam. Udah lebih jelas? 😊

DUMMY ELEMENT: bukan elemen sesungguhnya, tidak menyimpan informasi yang akan kita gunakan.

biasanya hanya untuk kajian ilmiah. Elemen pertama bukan yang ditunjuk first, tapi yang ditunjuk NEXT DARI FIRST

muncul karena ketika insert first/last atau at akan berbeda algoritmanya.

kalau insertfirst akan memengaruhi first dan kasus lainnya.

pake dummy element di awal ini, maka first ini gapernah berubah dan selalu nunjuk ke dummy element

ini misalkan buat bahasa pemrograman yang ga punya NIL, jadi nodenya nunjuk ke diri sendiri (kalo di akhir)

Biasanya hanya untuk kajian ilmiah saja

biasanya macam-macam list linier itu faktor pembedanya ada di 3 faktor ini

Kondisi awal, FirstAvail menunjuk ke nol. FirstList = NIL

Saat InsertFirst: FirstList nunjuk ke 0 dan nextnya NIL FirstAvail nunjuk ke 1 (nunjuk ke elemen yg available berikutnya)

InsertFirst lagi FirstList pindah ke 1, next nunjuk ke 0 FirstAvail nunjuk ke elemen yang kedua.

DeleteLast Node yang terakhir dimasukkan dikembalikan ke FirstAvail (iya emg jadi kaya stack) FirstList menjadi 1

IS EMPTY CUMAN BISA UNTUK LIST BUKAN ADDRESS

pada dasarnya L gapunya info dan next, cuman FIRST

rekureens

tidak melakukan proses rekursif lagi,

basically kaya rekursif

kalo mau insert di linkedlist SELALU PAKE NEWNODE karena itu udah auto alokasi dan assign val ke address baru

dengan menggunakan satu kondisi tertentu yang dinyatakan oleh predikat P

TANPA BOOLEAN: tidak ada boolean dalam while loop

kondisi setelah keluar dari loop: apakah P^.Next = Nil (sampe ujung) ata P^.info = X (Ditemukan)

ada handling list kosong

DENGAN BOOLEAN, kalau not found -> P = NIL

perbedaan dengan skema 2, disini P saat keluar dari loop ini akan menunjuk ke elemen terakhir.

di skema 2: P saat keluar loop akan bernilai NIL.

REPEAT UNTIL, karena jika sudah sampai titik ini list sudah pasti TIDAK KOSONG, sudah di handle di atas

bedanya di awal ada PERLAKUAN KHUSUS UNTUK LIST KOSONG

peak

pengelompokkan yang isi dan kosong

tadikan ini mem bikin semua blok <1,25> sekarang alokasi emg butuhnya berapa

list zona yang kosong

gabisa cuman ngandelin indexnya

kenapa perlu representasi berkait karna kalo x^1000, harus bikin array sepanjang itu jadi agar lebih efisien

buat input

bikin polinom isinya 0 semua

polinom sukunya kosong,

misal x^5 dijumlahkan dengan -x^5 jadi polinom kosong

BOLEH GA NGURUT

sampai MARK

array

ini adalah MARK

pasangan harga

lebih enak di tulis kebalik biar pemrosesannya lebih mudah

bisa pake array dan list berkait

ini kontigu (berarti array)

karna tail gaada gunanya mending pake list linear biasa (next) kalo mau hapus elemen ga masalah selalu dari depan dan insert pun bakal search dulu dari depan sampe posisi yang tepat untuk elemen tersebut

untuk insert element (enqueue), harus insert sesuai prioritas, kalau mulai dari tail gapunya pointer ke depan, jadi selalu mulai dari depan dan melihat posisi yang pas dimana.

first jadi head dan last jadi tail. head mencatat elemen pertama dari queue last mencatat elemen terakhir dari queue

menunjuk ke elemen ke 2 (next dari p)

node gagal dibuat karna bernilai nil (karna memori penuh)

untuk mengisi address dari struct node

overflow pada unsigned

flag untuk bilangan unsigned. kalo operasi ada carrynya, misal : 14+3 = 17 tp pada 4 bit jadi 1 dan ada carry 1.

kalo ini terjadi, carry flag nyala (overflow pada bilangan unsigned)

jika operasi hasilnya negatif, maka sign flag (SF) akan diset

overflow ini kaya kalo penjumlahan 4 bit 6+4 = 10 kan harusnya tp karna 4 bit jadi -6, nah ini ga sesuai sama "keinginan manusia" lah jadi ini overflow dan OF akan di set

OF di set ketka terjadi overflow

ciri2 bilangan negatif MSB nya 1

asumsi gw adalah kalo lossless ini emg ada kondisi khusus (liat next) berarti ga semua data itu lossless, kalo emg udh lossy dari awal gabisa di ubah jadi lossless.

udah pakem ini fix bgt

kebetulan (ga applied globally), karna asumsi juga bisa

F

F

F^+

emg FD ini generalisasi dari konsep key jadi emg mirip, menghubungkan suatu atribut unik untuk identifikasi atribut lain

jika tidak ada informasi yang hilang.

cara memenuhi lossless adalah jika setelah dipecah dan digabgung lg dengan natural join akan sama hasilnya dengan relasi awal

ini emg masih perkenalan apa itu lossy dan lossless

untuk mengatasi repetisi, dekomposisi jadi 2 skema. ex jadi instructor dan department.

masalahnya kalo ada kasus misal nama nya sama, jadi ada kelebihan informasi

misal dibuat tabel nih. kenapa bakal beda sama yang sblumnya? karna akan dilakukan dekomposisi

masalah dari hasil join ini ada repetisi misal di yang kerja di physics ada Einstein dan Gold,

informasi building dan budgetnya jadi berulang

naro elemen di sebelum dummy

berarti dummy akan selalu di akhir

gagal terbentuk kalo memorinya habis

sentinel ini kaya MARK

lebih fleksibel yang ini karena ada LAST JUGA sblm nya cmn first jadi cuman bisa mulai dari kiri

kalo ini bisa dari kanan juga

ini lebih praktis dari dummy last yang gapake "LAST" karena kalo yg sblmnya tetep harus looping dari awal

BISA SAMA KAYA SBELUMNYA ATAU NGEBANDINGIN NEXT DI TERAKHIR SAMA DENGAN ADDRESS DI LAST ATAU NGGAK

kalo ini node terakhir ditandain nextnya NIL

variasi dari list biasa, ada last jadi bisa implementasi queue pake ini

dilihat edge nya

dilihat titiknya tepat sekali

ga semua terhuubung, b->d gaada

semua bakal terhubung

simple circuit kalo ga lewat ke garis yang sama lebih dari sekali

path jalur, kalo balik ke titik awal circuit

karena sama persis

diliat derajatnya (sama) misal b sama kaya x d kaya z

diagonal pasti 0

graph bisa dibagi 2, titik atas dan bawah tidak terhubung secara lgsg

perbedaan antara gambar 1,2,3 (garis,kotak,kubus) tiap titik beda sat 0->1 10->11

ada titik tengahnya

minimal titik nya 3

SETIAP TITIK TERHUBUNG SATU SAMA LAIN

kalo directed ada dua, deg+ (berarti keluar) deg- (berarti masuk)

GAADA DI SLIDE

adjacent berdekatan azza

ada brpa garis ke titik tsb

garis menyentuh suatu titik

karena searah jadi masih simple

berbentuk gelang,mis V2 kembali ke V2 secara melingkar

kumpulan titik garis

pake newnode karena build from groundzero

algoritma ini berlaku untuk list kosong attau tidak kosong, why? pikirin ae

harusnya 0..(length(l)-1)

bedakan set dan insert kalo get/set node sudah ada kalo insert from ground zero

index disini lebih "posisi ke berapa" bukan index spt di array karena ya linked list kan info sama next, sbnrnya gaaada index tapi dibuat2 aja

sbnrnya di linked list gaada index. tp kalo kita "buat" index virtual bisa memudahkan kita

TRIVIAL, GAMUNGKIN ADA DIUAS HARUSNYA YG BIASA

Binary vs. Non-Binary Relationships:

Binary Relationships: Melibatkan dua entities. Beberapa hubungan non-binary dapat dipecah menjadi beberapa binary relationships untuk menangani kasus tertentu. Misalnya, hubungan ternary parents dapat dipecah menjadi father dan mother untuk memungkinkan informasi parsial. Non-Binary Relationships: Melibatkan lebih dari dua entities (n-ary, untuk n > 2) dan digunakan saat hubungan lebih jelas jika beberapa entities berpartisipasi bersama dalam satu hubungan. Contoh: proj_guide.

aggregasi disini beda dengan di aljabar relasional dan sql.

jadinya, instructor ini kalo ga pake aggregasi bakal terhubung ke semua relasi di atas, biar ga terlalu banyak panah, dibuat kotak besar satu relasi DAN entity ini di hubungkan ke kotaknya aja. contoh bener di slide bwah

berdasarkan kondisi

ook jadi bedanya coondition defined dan user defined, kalo di sql condition defined itu udah di auto assign relasi2nya kalo user defined harus diinput satu2

ini condition defined karna ada type lalaili, yg gaada user defined

Entity tidak wajib menjadi anggota salah satu lower-level entity sets.

Entity harus menjadi anggota salah satu lower-level entity sets.

Completeness constraint menentukan apakah sebuah entity di higher-level entity set harus menjadi anggota dari salah satu lower-level entity sets.

bisa lebih dari satu anggota lowe level entity set

hanya bisa menjadi anggota satu lower level entity set

Menentukan apakah entities bisa termasuk dalam lebih dari satu lower-level entity set.

ditentukan pengguna

Kendala dalam menentukan apakah entity dapat menjadi anggota lower level entity set (Membership constraint)

mulainya dari bawah, misal ada attribut permanent pengen dibuat higher levelnya employee

Generalization adalah proses desain bottom-up, di mana kita menggabungkan beberapa entitas dengan fitur yang sama ke dalam entitas tingkat lebih tinggi. Specialization dan generalization adalah kebalikan satu sama lain dan digambarkan dengan simbol yang sama dalam diagram E-R. Hubungan ISA menunjukkan pewarisan dari superclass ke subclass. Contoh: "Employee" dapat memiliki subclass seperti "Permanent" dan "Temporary," serta "Officer," "Teller," atau "Secretary."

jjadi dia mulainya dari sub class dulu instead of higher levelnya?

Betul! Generalization dimulai dari subclass (entitas tingkat lebih rendah) dan menggabungkannya menjadi superclass (entitas tingkat lebih tinggi). Jadi, kita mengidentifikasi fitur yang sama di beberapa subclass dan menyatukannya ke dalam satu entitas umum yang disebut superclass.

Specialization adalah proses desain top-down di mana kita membagi entitas menjadi subkelompok yang memiliki karakteristik unik. Subkelompok ini menjadi entitas tingkat lebih rendah yang mewarisi semua atribut dari entitas tingkat lebih tinggi, tetapi memiliki atribut atau hubungan tambahan yang khusus. Proses ini digambarkan dengan simbol segitiga bertuliskan "ISA", yang menunjukkan hubungan pewarisan. Contohnya, "Customer" adalah subkelompok dari "Person."

nama lain is a

atribut yang berada di "lower level" mewarisi atribut yang ada di atasnya. Misal employee mewarisi person (jadi ada 1 + 3 atribut)

dibagi menjadi subgroup pakai ISA, jadi person dibagi jadi employee dan customer

udh pasti gk kosong

menghitung banyak elemen. kan bakal pake cnt, karna kalo list kosong ya cnt ttp 0

contoh lain, mencari elemen terbesar yang mana. ga bisa pake traversal, karena kalo kosong ya gaada yang terbesar, gaberlaku pada list kosong. jadi kasus kedua, ada perlakukan khusus kalo kosong

contoh lain, kasus rata-rata, pembagi gaboleh nol

how to determine kapan kita pake jenis traversal? simply ya emang di coba aja, kalo misal pake dasar ga works try the other way

harus paham kapan kita pake traversal atau search

sama aja kaya di awal tapi ada tambahan l: List

jadi ngubah reference nunjuk dari elemen ke yang pengen di hapus jadi di skipp.

bisa 2 kasus, hapus dan ga dipake lagi di "free" kalo di hapus dan di pake lagi berarti ga di "free"

"free" ini ngehapus memory yak

jadi ya ganti aja update alamatnya bukan nyisipin satu satu

oke tiap node akan ada reference lanjut ke node mana? kalo node pertama gmn?

jadi harus buat kotak node baru lagi bernama First untuk mencatat alamat dari node pertama

kalo di notal "pointer to node"

ok intinya ini pake tag node biar bisa memberi instruksi ke preprocessor membuat struct baru node dengan Address yang beda-beda.

pada umumnya itu typedef Node (cara aksesnya)

cuman karna ini pake tag, instead of mengubah, kita membuat baru dengan address yang bisa beda beda

ini typedef struct node* Address (perhatikan bahwa struct di tulis juga)

ini tag

tag dan type nya dibedakan (node dan Node) untuk mengatasi strictnya bahasa C dimana tipe tidak bisa di declare setelah operasi lain. dibuatlah jadi tag, im not to sure so ask again ke GPT

type

maksud p1 panah ke atas adalah benda yang ditunjuk p1 jadi p2 (5)

jadi node lebih efisien

note terdiri atas info (isi elemen) dan dan next (untuk menunjuk ke elemen selanjutnya)

Node ini berbeda dengan array, kalo array yaudah per memory isi elemen. Kalo node bisa butuh 2 memory, 1 untuk elemen dan 1 untuk "menunjuk" ke elemen node selanjutnya

mysql> SELECT '437' AS FOO;

+-----+

| FOO |

+-----+

| 437 |

+-----+

1 row in set (0.00 sec)

menghasilkan konstan dan dinamakan FOO

ini namanya stack of float.

sebenernya bisa ttp stack of token, tapi ribet, sebelum dioperasikan harus diconvert terus setlah operasi di convert jadi token lagi

tambahan, harusnya kalo angka gaakan ada negatif

kebetulan bahwa kita mendefinisikan idxUndefnya -1 jadi auto, kalo pop 0 jadi -1 dan ya udah gausah ada handling khusus

bisa dinamis, tapi type stack ada tambahan capacity, jadi kalo dah cukup ya realloc

Function Calls: Like stacking ingredients when cooking – the last added ingredient is used first.

Recursion: Climbing a mountain – you reach the top and then come back down through the same checkpoints in reverse.

Arithmetic Calculations: Old calculators – they solve operations in the order they were entered, using the last numbers first.

Backtracking: Navigating a maze – if you hit a dead end, you backtrack to the previous path until you find the way out.

15 langkah mas

elemen yang terakhir dimasukkan ke dalam stack akan menjadi yang pertama dihapus, seperti ketika menumpuk buku, buku terakhir yang ditaruh di atas akan menjadi yang pertama diambil.

penghapusan dan penambahan juga dilakukan dari paling atas

kebalikan queue, penambahan jadinya diatas dan menjadi TOP baru

hapus

setelah sama, idx tail jadi 0

geser satu ke kanan

seolah olah elemen akhir dan awal berdekatan,

jadi head tail bisa berputar mengelilingi array

harus geser.

pergeseran hanya dilakukan ketika TAIL == IdxMax dan hanya saat ingin tambah elemen lagi

penuh setelah penghapusan, ada array yang kosong akibat penghapusan.

ada elemen koosong sebelum head dan tidak setelah tail

geser index head doang

karena ada pergeseran elemen

trus yaudah geser sebelah kanan head ke kiri

step 1, ambil HAPUS elemen dari head

kalo inisialnya queue kosong, asalanya undefined jadi 0 indexnya

tail digeser ke kenan (di 5) jadi elemen baru punya index 5

alt 1, head tidak pernah pindah

agar tidak menunjuk ke elemen tabel manapun

nambah ke paling belakang yak