Linked List, Stack, Queue

Pada pertemuan hari ini, kita membahas lebih dalam mengenai coding Single Linked List dan Double Linked List. Pada blog ini saya akan membahas mengenai pelajaran yang telah diajarkan tadi dan menambahkan mengenai stack and queue.

LINKED LIST

Pada blog sebelumnya, saya pernah menulis mengenai apa itu Single Linked List dan Double Linked List. Sekarang saya akan membahas mengenai coding operasi pada Linked List, yaitu push dan pop pada Single Linked List dan Double Linked List yang paling sederhana.

Pertama-tama, kita harus mendefinisikan struct untuk nodenya. Untuk lebih jelasnya bisa dilihat pada gambar di bawah ini.

1. Single Linked List

a) PUSH

Untuk push pada Single Linked List dapat dilihat pada gambar di bawah ini.

Pada coding di atas, kita menggunakan malloc untuk mengalokasikan memori secara dinamis. Setelah itu kita memberikan value kepada curr dengan nilai a. Dilanjutkan dengan kondisi if else. Jika kita baru push sekali, maka nilai pada head dan tail masih NULL. Oleh karena itu, jika nilai dari head adalah NULL maka head = tail = curr. Jika nilai dari head tidak NULL, maka nilai tail ke next adalah curr. Lalu nilai dari tail yang baru sama dengan nilai dari curr. Setelah kondisi tersebut, harus dideklarasikan nilai dari tail ke next adalah NULL.

b) POP

Untuk pop pada Single Linked List dapat dilihat pada gambar di bawah ini.

Pada coding di atas, kita mendefinisikan nilai dari curr sama dengan head. Dilanjutkan dengan kondisi if else. Jika nilai dari tail sama dengan head, maka nilai dari curr free / dihapus sehingga nilai dari head, tail, curr adalah NULL. Namun, jika nilai dari tail tidak sama dengan head, maka akan melakukan looping selama nilai dari curr ke next tidak sama dengan tail untuk menggeser nilai curr sampai sama dengan tail. Ketika nilai curr sudah sama dengan tail, maka nilai dari tail free / dihapus dan nilai dari tail yang baru adalah curr, sehingga tail ke next adalah NULL.

2. Double Linked List

a) PUSH

Untuk push pada Double Linked List dapat dilihat pada gambar di bawah ini.

Pada coding di atas, kita menggunakan malloc untuk mengalokasikan memori secara dinamis. Setelah itu kita memberikan value kepada curr dengan nilai a. Lalu mendefinisikan nilai dari curr ke next dan curr ke prev adalah NULL (artinya nilai sesudah dan sebelumnya adalah NULL). Dilanjutkan dengan kondisi if else. Jika kita baru push sekali, maka nilai pada head dan tail masih NULL. Oleh karena itu, jika nilai dari head adalah NULL maka head = tail = curr. Jika nilai dari head tidak NULL, maka nilai curr ke next adalah head dan nilai dari head ke prev adalah curr. Lalu nilai dari head yang baru sama dengan nilai dari curr.

b) POP

Untuk pop pada Double Linked List dapat dilihat pada gambar di bawah ini.

Pada coding di atas, terdapat kondisi if else. Jika nilai dari tail sama dengan head, maka nilai dari curr free / dihapus sehingga nilai dari head, tail, curr adalah NULL. Namun, jika nilai dari tail tidak sama dengan head, maka nilai dari tail adalah tail ke prev (nilai tail yang sebelumnya). Lalu nilai tail ke next free / dihapus sehingga nilai dari tail ke next adalah NULL.

Untuk memanggil fungsi push dan pop di atas, dapat dilihat pada gambar di bawah ini.

STACK

Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Sistem pengaksesan pada stack menggunakn sistem LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack).

Operasi pada Stack adalah sebagai berikut :

1. Push : digunakan untuk menambah item pada Stack pada Tumpukan paling atas.

2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru Stack, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan Stack, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Stack ada dua jenis, yaitu:

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

QUEUE

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Sistem pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

Operasi pada Queue:

1. Create Queue  : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make Null Queue : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.

Dibuat Oleh:

Sheila Gracia Angelina

2301857456

Sumber:

1. PPT Binusmaya

2. https://furqonubd.wordpress.com/2013/05/20/stack-and-queue/