Summary Linked List, Stack & Queue

LINKED LIST

Merupakan struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. 

Dalam Linked List biasanya terdapat istilah Head dan Tail.

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Linked List sendiri terdiri dari beberapa macam, yaitu:

1. Single Linked List -> Linked List yang hanya mempunyai 1 variabel pointer saja.
2. Double Linked List -> Linked List yang memiliki 2 variabel pointer yang di mana                                        salah satu pointer nya menunjuk ke node selanjutnya dan                                             pointer satunya menunjuk ke node sebelumnya                        
3. Circular Single Linked List -> Linked List yang di mana Tail menunjuk ke Head                                                         yang menyebabkan tidak ada pointer yang menuju                                                        NULL.
4. Multiple Linked List -> Linked List yang memiliki lebih dari 2 variabel pointer

Sekarang kita akan membahas mengenai Double Linked List dan Circular Single Linked List. Single Linked List sudah dibahas pada post sebelumnya.

A. Circular Single Linked List  

Seperti dijelaskan sebelumnya, Circular Single Linked List adalah suatu linked list yang tail (node terakhir) nya menunjuk ke head (node pertama). Jadi, tak ada pointer yang menuju NULL.

 

B. Double/Two Way Linked List

Double Linked List adalah suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Double/Two Way Linked List ini dapat mengatasi kelemahan-kelemahan yang ada pada Single Linked List

Operasi pada Double Linked List :

a. Insert First -> Penyisipan pada awal sehingga pointer head akan berpindah ke elemen baru

b. Insert Last -> Penyisipan pada akhir sehingga pointer tail akan berpindah ke  elemen baru

d. Delete First ->  Penghapusan di awal list, pointer head akan berpindah ke node                                                               selanjutnya,sementara node awal akan didealokasi.

e. Delete Last -> Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya                                            sementara node akhir akan didealokasi.

f. Delete Node -> Penghapusan node dengan data tertentu.

STACK & QUEUE

STACK

Sesuai dengan artinya, stack seolah-olah seperti menumpukkan suatu data di atas data lainnya.

Stack sendiri bersifat LIFO (Last In First Out) di mana data yang terakhir masuk ke dalam stack akan menjadi data yang keluar terlebih dahulu dari stack.

Stack sendiri dapat diimplementasikan dengan block chain atau linked list.

 

Kita mengenal 5 operasi dasar Stack, yaitu:

1. Push       -  Menambahkan item pada bagian paling atas dari stack.

2. Pop        -  Mengambil item dari tumpukan paling atas.

3. Clear      - Mengosongkan stack.

4. IsEmpty - Fungsi yang digunakan untuk mengecek apakah stack sudah kosong.

5. IsFull      - Fungsi yang digunakan untuk mengecek apakah stack sudah full/terisi.

INFIX, POSTFIX & PREFIX

Infix  =  Operator dituliskan di antara operand

Postfix  =  Operator dituliskan setelah operand

Prefix  =  Operator dituliskan sebelum operand

Contoh :

((1 + 3) / (100 * 5) ^ 30)

Prefix : ^ + 1 3 / * 100 5 30

Postfix : 1 3 + / 100 5 + * 30 ^

Perlu diketahui, komputer tak mampu membaca tanda kurung ( ) pada operasi aritmatika. Maka, dibuatlah 3fix (Infix, Prefix, Postfix) yang membuat komputer dapat melakukan operasi aritmatika dengan benar.

Depth Search First (DFS) menggunakan metode Stack.

QUEUE

Disebut juga antrian. Queue adalah sekumpulan data yang penambahan elemennya hanya dapat dilakukan di salah satu ujung depan (front) atau ujung belakang (rear).

Jika pada Stack menggunakan prinsip LIFO (Last In First Out) maka pada Queue menggunakan prinsip FIFO (First In First Out). Di mana data yang pertama kali masuk akan keluar pertama kali.

Kita mengenal 3 operasi dasar queue:

1. Push  =  Menambah item dari bagian belakang queue.

2. Pop  =  Menghapus item dari bagian depan (front) queue.

3. Front  =  Menyatakan item paling depan dari suatu queue. (Top)

Front dapat dikenal juga sebagai Peek (Stack).

Queue dapat memasukkan data dari array terakhir dan dapat melakukan delete array di awal. Namun, ketika array sudah mencapai batas kita tak bisa menambah data lagi padahal array awal masih kosong. Maka dari itu, terdapat Circular Queue yang dapat mengatasi masalah ini dengan dapat berulang terus-menerus.

DEQUES (Cara membaca : Deck/Dequeue)

Dapat mengacak-acak (add atau delete) data semau user dari array manapun.

• Input Restricted Deque - Push (Input) hanya boleh/dibatasi 1x.
• Output Restricted Deque - Output nya dibatasi hanya 1.

Breadth First Search (BFS) menggunakan metode Queue.