Variasi Linked List



Pada blog kali ini, saya akan menjelaskan beberapa varian dari linked list. Namun sebelumnya, alangkah lebih baik lagi apabila kita mengulas kembali secara cepat tentang linked list biasa.

Review tentang Linked List

Illustrasi gambar tentang linked list:
Sumber: https://fasyamaharani.files.wordpress.com/2013/01/bergandengan-tangan1.jpg

Linked list adalah suatu tipe data struktur yang menggunakan alamat memori untuk menunjukkan data selanjutnya. Linked list ini hanya bersifat satu arah saja alias irreversibel. Oleh karena itu, ia tidak dapat kembali ke data sebelumnya. 

Isi dari linked list:
- Pointer ke data selanjutnya
- Kumpulan isi data suatu node, baik itu merupakan kumpulan dari array, char, int, string, maupun data-data lainnya

Contoh node dari linked list dalam bahasa C maupun C++:
struct NodeMahasiswa{
    char nama[10];
    int umur;
    char NIM[12];
    struct Node* next;
}

Karena di sini kita bermain dengan memori, maka untuk menandakan bahwa data tersebut di suatu node adalah data terakhir, maka alamat untuk ke data selanjutnya ditandakan dengan null.

Operasi linked list antara lain:
- Insertion
- Search
- Deletion

Nah, karena kita sudah mengulas kembali materi linked list, maka kita bisa berbicara tentang varian dari linked list tersebut. Berikut penjelasannya.

Double linked list
Double linked list kurang lebih hampir sama dengan linked list pada umumnya. Namun, Ia memiliki satu tambahan pointer lagi, yaitu previous (referensi yang menunjuk ke alamat sebelumnya). Jadi sekarang dia memiliki dua pointer, yaitu previous dan next.

Untuk lebih jelasnya, perhatikan contoh gambar berikut:

Tidak seperti linked list biasa, jika kita sudah maju ke alamat berikutnya, maka kita tidak bisa kembali lagi ke alamat sebelumnya (bersifat satu arah saja, yaitu ke depan). Namun, berkat previous pointer ini, kita bisa bergerak dua arah, yaitu ke alamat selanjutnya dan sebelumnya. Jadi, kita bisa melihat data sebelumnya yang sudah kita lalui.

Circular Linked List
Circular linked list juga hampir sama dengan linked list biasa, namun ia memiliki 1 ciri khas, yaitu ia tidak memiliki pointer yang menandakan data yang kosong (null). Akibatnya, kita bisa balik lagi ke data pertama yang kita sudah lihat sebelumnya.

Circular linked list bisa digambarkan seperti berikut:


Pada gambar di atas, linked list tersebut tidak memiliki pointer yang menunjukkan ke data yang kosong (null). Pada saat kita melakukan beberapa kali looping untuk menelusuri data yang ada, kita pasti akan menemukan data yang sama. Hal ini disebabkan karena pointer next yang berada di ujung linked list tidak menunjukkan null, namun ia kembali lagi ke data awal.

Circular double linked list
Circular double linked list merupakan gabungan dari kedua ciri khas fungsi circular dan double linked list di atas.

Ciri-cirinya adalah:
·        Ia bisa menunjuk ke data sebelumnya
·        Ia bisa balik lagi ke data awal.
·        Tidak memiliki pointer yang menunjuk ke data null

Pada akhirnya, circular double linked list membentuk gambar berikut:



Sebagai penutup...

Saya akan menyajikan contoh kode dalam bahasa C untuk double linked list, yaitu berupa operasi searching, insertion, dan deletion. Jika Anda mau, Anda bisa memodifikasi sedikit dari kode di bawah sehingga operasi-operasi tersebut juga bisa dilakukan di ketiga varian di atas.

#include <stdio.h>
#include <stdlib.h>

struct Node{
int data;
struct Node* next;
struct Node* prev;
} typedef Node;

Node* addNode(int data){
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = NULL;
node->prev = NULL;
return node;
};

Node* head = NULL;
Node* tail = NULL;

void addNodeFromTail(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
tail->next = node;
node->prev = tail;
tail = tail->next;
}
}

void addNodeFromHead(Node* node){
if (head == NULL){
head = node;
tail = node;
}
else{
head->prev = node;
node->next = head;
head = head->prev;
}
}

void addNodeFromMiddle(int index, Node* node){
if (head == NULL){
printf("Currently, the data is empty. We will automatically add this to index 1!\n\n");
head = node;
tail = node;
}
else{
int currentIndex = 1;
Node* temp = head;
while (index != currentIndex){
temp = temp->next;
currentIndex++;
}
node->next = temp;
node->prev = temp->prev;
temp->prev->next = node;
temp->prev = node;
}
}

void scanDataFromHead(){
Node* temp = head;
printf("Previewing from head: ");
while (temp != NULL){
printf("%i ", temp->data);
temp = temp->next;
}
}

void scanDataFromTail(){
Node* temp = tail;
printf("Previewing from tail: ");
while (temp != NULL){
printf("%i ", temp->data);
temp = temp->prev;
}
}

void deleteDataFromHead(){
head = head->next;
free(head->prev);
head->prev = NULL;
}

void deleteDataFromTail(){
tail = tail->prev;
free(tail->next);
tail->next = NULL;
}

void deleteDataFromMiddle(int index){
Node* temp = head;
int counterIndex = 1;
while (counterIndex != index){
temp = temp->next;
counterIndex++;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
temp->prev = NULL;
temp->next = NULL;
free(temp);
}

int main(){
int size = 0;
int i = 0;
int number = 0;
char mode;
printf("============ A Double linked list simulator ============\n");
printf("How many data to be inserted? ");
scanf("%i", &size);
getchar();
printf("Format: integer [space] mode\n");
printf("Middle insertion: integer [space] M [space] index\n");
for (i = 0; i < size;){
printf("Data %i: ", i+1);
scanf("%i %c", &number, &mode);
if (mode == 'T'){
addNodeFromTail(addNode(number));
i++;
}
else if (mode == 'H'){
addNodeFromHead(addNode(number));
i++;
}
else if (mode == 'M'){
int index = 0;
scanf("%i", &index);
addNodeFromMiddle(index, addNode(number));
i++;
}
else{
printf("Type T(tail), H(head) or M(middle) to insert the data!\n");
}
getchar();
}
scanDataFromHead();
printf("\n");
scanDataFromTail();
printf("\n\nHow many data you'd like to delete? ");
int numberDeletedData = 0;
scanf("%i", &numberDeletedData);
getchar();
printf("Format: mode\n");
printf("Middle deletion: M [space] index location data\n");
for (i = 0; i < numberDeletedData;){
printf("Operation %i : ", i+1);
scanf("%c", &mode);
if (mode == 'T'){
deleteDataFromTail();
i++;
}
else if (mode == 'H'){
deleteDataFromHead();
i++;
}
else if (mode == 'M'){
int index = 0;
scanf("%i", &index);
deleteDataFromMiddle(index);
i++;
}
else{
printf("Type T(tail), H(head) or M(middle) to delete the data!\n");
}
getchar();
}
scanDataFromHead();
printf("\n");
scanDataFromTail();
return 0;
}

Sample input (contoh masukan):
6
30 T
10 H
100 H 
200 T
500 M 3
1000 M 2
3
T
H
M 2

Demikianlah blog saya tentang circular, double, dan circular double linked list. Terima kasih karena telah mengunjungi blog saya dan semoga bermanfaat!

Nama pembuat: Anthony Kevin Oktavius

Comments

Post a Comment

Popular posts from this blog

Heap

Image
Halo semuanya, setelah kita belajar macam-macam balancing tree (AVL Tree, Red Black Tree, dan B-Tree), maka sekarang kita akan belajar tree yang direpresentasikan dalam bentuk array, yaitu heap. Apa itu heap? Heap adalah salah satu varian dari binary tree, namun Ia memiliki prinsip dan aturan sebagai berikut: Heap adalah binary tree yang direpresentasikan dalam bentuk array. Untuk melakukan traverse node dari heap, kita tidak menggunakan cara recursive, namun menggunakan proses iteratif. Berikut ini adalah contoh gambar dari heap: Sumber:   https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/1200px-Max-Heap.svg.png Jika direpresentasikan dalam bentuk array, maka terlihat sebagai berikut: Index 0 1 2 3 4 5 6 7 8 Value 100 19 36 17 3 25 1 2 7 Catatan: Heap selalu berupa balanced binary tree. Heap ini memiliki 3 varian, yaitu...
Read more

AVL Tree

Image
AVL Tree AVL Tree secara dasarnya sama seperti Binary Search Tree yang umumnya, namun tree ini memiliki perbedaan-perbedaan yang mendasar: Bisa dibilang bahwa tree ini hampir selalu berupa perfect binary tree. Hal ini terjadi karena AVL Tree mengoptimasi cabang-cabang anakannya sehingga cabangnya tidak terlalu ke kiri atau ke kanan Akibatnya, perbedaan ketinggian pada setiap cabang yang terdapat di tree ini tidak boleh lebih dari 1. Inilah yang kita sebut sebagai Balanced Binary Tree. Berikut ini adalah contoh perbandingan gambar AVL Tree dan yang bukan: Kiri – Bukan AVL Tree karena perbedaan ketinggian di node 8 dan 18 lebih dari 1, namun gambar kanan memenuhi persyaratan AVL Tree Sumber: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ Mengapa AVL Tree perlu dipakai? Bayangkan jika kita menggunakan binary search tree. Jika kita lihat, anakan yang lebih besar dari parentnya, maka nodenya ditaruh di kanan dan sebaliknya. Bagaimana jika data ya...
Read more

Binary Tree dan Hash Table

Image
Hash Table Apa itu hash table? Hash table adalah suatu tipe data structure yang meliputi: Array Linked List Bentuk umum hash table dalam bahasa C: Struct Node{                int data;                Node* left;                Node* right; } Struct HashTable{                Node* head;                Node* tail; } HashTable hash[10]; // Tentukan array sizenya terlebih dahulu Nah, suatu data ini bisa masuk ke suatu index dalam array dengan menggunakan rumus sebagai berikut: Size of array: bilangan % arraySize. Misal angka bilangan di dalam suatu data adalah 10 dan arraySize adalah 13, maka Ia aka...
Read more