Linked List (Week 2 GSLC)

-

Linked List

Pada pertemuan sebelumnya, saya telah mempelajari Single Linked List. Linked List merupakan struktur data yang memanfaatkan dynamic memory allocation dalam membuat sebuah kumpulan data, dan data-data tersebut dihubungkan oleh pointer.
Data-data pada Linked List dapat kita manipulasi dengan insertion (push) dan deletion (pop). Setiap Linked List harus diawali oleh head dan diakhiri oleh tail.
Contoh :


Single Linked List

Single Linked List merupakan Linked List yang hanya terhubung ke data berikutnya.

Codingan dasar dalam membuat Linked List:
struct node {
int nilaiData;   
struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

Circular Single Linked List


Circular Single Linked List memiliki bentuk yang sedikit berbeda dengan Single Linked List. Tail->next pada Single Linked List menunjukkan nilai NULL, sedangkan pada Circular Single Linked List, tail->next menunjuk pada head. Sehingga tidak terdapat NULL dalam Circular Single Linked List. Dalam codingan, hanya perlu sedikit modifikasi, yaitu dengan mengubah pointer next pada nilai terakhir menunjuk nilai dari head. Hal ini berlaku untuk insertion dan deletion.

Double Linked List


Double Linked List merupakan Linked List yang terhubung dengan data berikutnya dan data sebelumnya.

struct node {
int nilaiData;   
struct node *next;
struct node *prev;
};

struct node *head = NULL;
struct node *tail = NULL;

Insertion
Push depan:
1. Membuat node baru (contoh *curr)
2. Mengisi datanya
3. curr->next diisi nilai head dan curr->prev diisi NULL
4. head->prev menjadi curr
5. head menunjuk ke curr

Untuk push belakang, lakukan modifikasi pada node tail.
Untuk push tengah (contoh diantara node x dan node y):
1. Membuat node baru (contoh *curr)
2. Mengisi datanya
3. curr->next menjadi x->next
4. x->next menjadi curr
5. curr->prev menjadi x
6. Ubah prev dari y menjadi curr

Deletion
Terdapat 4 kondisi:
1. Menghapus satu-satunya node dalam Linked List
-> Melepas memori head dan tail
2. Menghapus head dari Linked List
-> Memindahkan head ke data berikutnya, lalu lepas memori head->prev dan beri nilai NULL pada head->prev
3. Menghapus tail dari Linked List
-> Memindahkan tail ke data sebelumnya, lepas memori tail->next, dan beri nilai NULL pada tail->next
4. Menghapus node yang berada di tengah Linked List
-> Cari nilai yang ingin dihapus dengan mengecek nilai next dari node, apabila sudah ditemukan, buat pointer temporary untuk menyimpan nilai dari node yang akan dihapus, dan nilai yang akan ditampung. Contoh a sebagai nilai pertama, del sebagai nilai yang akan dihapus, dan b sebagai nilai kedua. A->next berisi b, dan b->prev berisi a, kemudian lepas memori del.

Circular Double Linked List


Circular Double Linked List berbentuk sirkuit dimana tidak terdapat nilai NULL pada head->prev maupun tail->next. Head->prev berisi nilai tail dan tail->next berisi nilai head.

 





Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

-
Gambar
AVL Tree merupakan pengembangan dari Binary Search Tree. AVL Tree memberikan kompleksitas yang lebih rendah, khususnya dalam worst case, karena AVL Tree menyeimbangkan root-root dari Binary Search Tree. Dalam melakukan insertion, deletion dan searching, kompleksitasnya sangat dipengaruhi oleh tinggi dari pohon tersebut. Apabila Binary Search Tree memiliki cabang yang cenderung timpang, misal kebanyakan data berada di sisi kiri sementara sisi kanan kosong, itu berpengaruh terhadap kompleksitasnya sendiri. Dan AVL Tree menyelesaikan masalah ini dengan menyeimbangkan cabang-cabangnya sehingga tidak terlalu timpang. Ini yang disebut dengan Balanced Binary Search Tree dan AVL Tree ini merupakan salah satu dari bentuk Balanced Binary Search Tree. Tinggi sebuah node: - Tinggi dari sebuah subtree kosong adalah 0 - Tinggi leaf adalah 1 Balance Factor: Perbedaan tinggi antara subtree kiri dan subtree kanan dari sebuah node *Balance factor sebuah node hanya boleh paling besar 1 ...
Baca selengkapnya

Review

-
Gambar
Nama: Ariantoly NIM: 2301877230 Kelas: CB-01 Nama Dosen: - Henry Chong (D4460) - Ferdinand Ariandy Luwinda (D4522) Linked List Pada pertemuan sebelumnya, saya telah mempelajari Single Linked List. Linked List merupakan struktur data yang memanfaatkan dynamic memory allocation dalam membuat sebuah kumpulan data, dan data-data tersebut dihubungkan oleh pointer. Data-data pada Linked List dapat kita manipulasi dengan insertion (push) dan deletion (pop). Setiap Linked List harus diawali oleh head dan diakhiri oleh tail. Contoh : Single Linked List Single Linked List merupakan Linked List yang hanya terhubung ke data berikutnya. Codingan dasar dalam membuat Linked List: struct node { int nilaiData;     struct node *next; }; struct node *head = NULL; struct node *tail = NULL; Circular Single Linked List Circular Single Linked List memiliki bentuk yang sedikit berbeda dengan Single Linked List. Tail->next pada Single L...
Baca selengkapnya

Hashing dan Hash Tables, Trees, dan Binary Trees (Week 4)

-
Gambar
Pada pertemuan sebelumnya, saya telah mempelajari Linked List, yang dimana merupakan kumpulan data dinamis yang saling terhubung antar satu sama lain. Terdapat single linked list, double linked list, circular single linked list, dan circular double linked list. Untuk materi kali ini, linked list juga akan terpakai dalam hashing dan binary trees. HASHING DAN HASH TABLE Hashing merupakan teknik mengubah setiap record menjadi angka (hash). Kumpulan dari karakter dalam sebuah record diubah dalam bentuk yang lebih pendek (kata kunci) yang merepresentasikan kumpulan karakter itu sendiri. Keunggulan hashing ini adalah waktu aksesnya yang cukup cepat sehingga waktu yang dibutuhkan dalam penambahan, penghapusan, dan pencarian lebih singkat. Jadi, hashing ini mendistribusikan kunci-kunci dalam sebuah array yang disebut hash table, dengan menggunakan fungsi-fungsi yang disebut hash function. Contoh hash table: Misalkan kita ingin menyimpan nama mahasiswa berupa: Doni, Andi, B...
Baca selengkapnya