Langsung ke konten utama

3 - LINKED LIST IMPLEMENTATION 2 - 2101714345 - Vallentina Christy

Vallentina Christy / 2101714345 / CA01


LINKED LIST IMPLEMENTATION 2

STACK

Image result for stack
Stack merupakan salah satu tipe data structure yang cukup penting dimana stack itu sendiri menyimpan elemen-elemen seraca berurutan.
Stack juga merupakan linear data structure yang dapat diimplementasikan dengan menggunakan array maupun linked list.
Elemen dalam stack ditambah maupun dikurangi di hanya di satu edge, edge ini disebut top.
Stack berlaku First In Last Out (FILO) atau Last In First Out (LIFO).
Stack memiliki 2 variabel, TOP (digunakan untuk menyimpan alamat dari elemen paling atas) dan MAX (digunakan untuk menyimpan maximum number dari elemen yang dapat ditampung oleh stack).

Di dalam linked stack, setiap node memiliki dua bagian, yang pertama menyimpan data dan yang kedua menyimpan alamat dari node berikutnya.
Pointer START pada linked list digunakan sebagai TOP.
Semua insertion dan deletion diselesaikan di node oleh TOP.
Jika TOP = NULL maka itu berarti bahwa stack kosong.

Operasi stack:
- push(x) = menambah item x ke bagian atas stack
- pop() = menghapus sebuah item dari bagian atas stack
- top() = reveal / return item bagian atas dari stack

Aplikasi stack:
- infix evaluation
- postfix evaluation
- prefix evaluation
- infix to postfix evaluation
- infix to prefix evaluation
- depth first search

Terdapat 3 notasi aritmatik yaitu:
- prefix notation = operator ditulis sebelum operan
- infix notation = operator ditulis diantara operan
- postfix notation = operator ditulis setelah operan

Depth First Search (DFS)

Related image
DFS merupakan algorithm untuk melakukan pencarioan pada tree atau graph. 
Dimulai dari akar lalu kemudian melebar seluas-luasnya melalui cabang sebelum terjadi backtracking.

QUEUE

Image result for queue linked list
Queue merupakan struktur data yang menyimpan elemen dalam cara yang teratur.
Queue dapat diimplementasikan dengan menggunakan array maupun linked list.
Elemen di dalam queue yang ditambah pada salah satu edge disebut rear dan yang dihilangkan pada salah satu edge yang lain disebut front.
Queue berlaku First In First Out (FIFO) atau Last In Last Out (LILO).
Queue memiliki 2 variabel yaitu front dan rear.

Didalam linked queue, setiap elemen memiliki 2 bagian:
- yang satu untuk menyimpan data
- yang satu  lagi menyimpan alamat dari elemen selanjutnya

Pointer START dari linked list digunakan sebagaim FRONT.
Semua insertion akan dilakukan pada REAR dan semua deletion akan dilakukan pada FRONT end.
Jika FRONT = REAER = NULL, maka itu berarti bahwa queue sedang kosong.

Operasi queue:
- push(x) = menambah item x ke bagian belakang queue
- pop() = menghapus sebuah item dari bagian depan queue
- front() = reveal / return dari bagian terdepan queue

Aplikasi queue:
- deques
- priority queue
- breadth first search

Deques

Related image
Deque merupakan list dimana elemen dapat dimasukkan maupun dihapus baik di kedua end.
Disebut juga sebagai head-tail linked list karena elemen dapat ditambahkan maupun dihapus dari depan (head) maupun belakang (tail).

Priority Queue

Image result for priority queue
Priority Queue merupakan abstrak data type dimana setiap elemen assign sebuah priority.
Peraturannya adalah dimana elemen dengan priority lebih tinggi akan diproses terlebih dahulu sebelum elemen dengan priority yang lebih rendah. 
Selain itu, jika terdapat dua elemen dengan priority yang sama maka akan berlaku First Come First Served (FCFS).

Breadth First Search (BFS)

Related image
BFS merupakan algoritm untuk melakukan pencarian pada sebuat tree atau graph.
Dimulai dari akar dari tree yang kemudian akan melebar ke node terdekat dari satu level ke level selanjutnya hingga menemukan goalnya. 


Komentar

Posting Komentar

Postingan populer dari blog ini

4 - INTRODUCTION TO TREE, BINARY TREE AND EXPRESSION TREE - 2101714345 - Vallentina Chisty

Vallentina Christy / 2101714345 / CA01 INTRODUCTION TO TREE, BINARY TREE AND EXPRESSION TREE TREE AND BINARY TREE Tree Concept Tree merupakan sebuah koleksi atas satu atau lebih nodes. Node yang berada paling atas disebut root . Sebuah garis yang menghubungkan parent dengan child disebut edge . Nodes yang tidak memiliki child disebut leaf . Nodes yang memiliki parent yang sama disebut sibling . Degree  dari node merupakan total sub tree dari node. Height / Depth merupakan maximum degree dari nodes pada tree. Jika terdapat garis yang menghubungkan p kepada q, maka p disebut ancestor dari q,   dan q disebut descendant dari p. Binary Tree Concept Binary tree merupakan percabangan tree data structure dimana setiap node memiliki paling banyak dua children yaitu child kiri dan child kanan. Type of Binary Tree PERFECT Binary Tree merupakan binary tree dimana di setiap level memiliki depth / kedalaman / lebar yang sama....
Posting Komentar
Baca selengkapnya

2 - LINKED LIST IMPLEMENTATION 1 - 2101714345 - Vallentina Christy

Vallentina Christy / 2101714345 / CA01 LINKED LIST IMPLEMENTATION 1 LINKED LIST Linked list merupakan koleksi linear dari data, yang disebut node, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked list juga dapat didefinisikan sebagai kumpulan node yang mempresetasikan sebuah sequence. SINGLE LINKED LIST Single linked list merupakan linked list yang menggunakan sebuah pointer untuk menyimpan banyak data. Pointer hanya dapat bergerak ke satu arah saja. Single Linked List : Insert Front Penambahan data di depan membutuhkan penambahan node baru yang akan dikaitkan di node paling depan, tetapi pada saat pertama kali, saat data masih kosong, penambahan data dilakukan pada head nya. Untuk menghubungkan node yang terakhir dengan node yang terdepan dibutuhkan pointer baru. Back Penambahan data di belakang tentu saja dilakukan di belakang. Pada saat pertama kali, data langsung ditunjuk pada head nya. Kita me...
Posting Komentar
Baca selengkapnya