Linked List

Linked list adalah suatu tipe data yang berupa suatu rantaian. Rantaian yang dimaksud adalah pointer yang menghubungkan antara data yang satu dengan yang lainnya. Bila direpresentasikan dalam bentuk kehidupan nyata, linked list ini bisa direpresentasikan dalam bentuk orang-orang yang saling berjabat tangan antara orang yang satu dengan yang lainnya, sehingga bisa mengenali orang yang disampingnya.

Linked list ini merupakan dasar agar kita bisa memahami data structure lanjutan seperti tree dan hash tables.

Gambar linked list:

Linked list ini memiliki 2 bagian (umumnya):

• Data-data di dalamnya (bisa berupa kumpulan integer, char array, dan lain-lain)
• Pointer yang menunjuk ke data selanjutnya

Contoh bentuk umum Node Linked List:

struct Node{
     char name[40];
     int age;
     struct Node* next;
} typedef Node;

Linked list ini memiliki keunggulan dibandingkan dengan array dengan alasan sebagai berikut:

• Linked list bisa kita atur jumlah memori yang digunakan secara runtime
• Linked list kita bisa hapus memori yang sudah kita tidak perlukan lagi sehingga memori yang telah dihapus datanya sehingga bisa digunakan lagi di dalam program kita

Linked list memiliki kelemahan dibandingkan array dengan alasan sebagai berikut:

• Linked list tidak bisa kita akses secara random lokasi datanya sehingga harus kita akses terlebih dahulu dari head atau tail.
• Lokasi data di linked list bisa saja letaknya berjauhan, sehingga kecepatan untuk mencari datanya pun juga lebih lama dibandingkan dengan array yang lokasi datanya lebih terstruktur

Nah, linked list ini bisa memiliki pointer lebih dari satu, sehingga bisa memiliki varian yang lebih banyak lagi, seperti:

• Double linked list: memiliki 2 pointer, yaitu prev dan next
• Circular linked list: memiliki pointer next saja, namun Ia bisa kembali ke data awal ketika sudah mencapai data akhir

Linked list ini memiliki 3 operasi dasar yang bisa kita lakukan, yaitu:

• Insertion: penambahan suatu data
• Searching: pencarian suatu data
• Deletion: menghapus suatu data

Contoh kode dalam bahasa C++ yang di dalamnya sudah termasuk operasi-operasi dasar di atas:

#include <stdio.h>
#include <stdlib.h>
struct Node{
int number;
struct Node* next;
};
Node* head= NULL;
Node* tail= NULL;
Node* oneNode(int number){
Node* temp = (Node* ) malloc(sizeof(Node));
temp->number = number;
temp->next = NULL;
return temp;
}

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

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

void searchNode(){
Node* temp = head;
printf("You have these data: ");
int length = 0;
while (temp != NULL){
length++;
printf(" %i ", temp->number);
temp = temp->next;
}
printf("Current length is: %i\n",length);
}
void popHead(){
Node* oldHead = head;
head = head->next;
oldHead->next = NULL;
free(oldHead);
}
void popTail(){
Node* temp = head;
while (temp->next->next != NULL){
temp = temp->next;
}
tail = temp;
free(tail->next);
tail->next = NULL;
}

int main(){
int size = 0;
printf("Enter the number of elements you'd like to add: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H [number], T[number]) to insert the data: ");
int number = 0;
char letter;
scanf("%c %i", &letter, &number);
if (letter == 'H'){
pushFront(oneNode(number));
}
else if (letter == 'T'){
pushTail(oneNode(number));
}
getchar();
}
searchNode();
printf("Enter the number of elements you'd like to delete: ");
scanf("%i", &size);
getchar();
for (int i = 0; i < size; i++){
printf("Type H (head), or T(tail) (H , T) to delete the data: ");
char letter;
scanf("%c", &letter);
if (letter == 'H'){
popHead();
}
else if (letter == 'T'){
popTail();
}
searchNode();
getchar();
}
}

Anda bisa membaca varian-varian linked list di link berikut untuk lebih jelasnya: https://anthonykevinoktaviusdatastructure.blogspot.com/2020/02/variasi-linked-list.html

Demikianlah pembahasan tentang linked list. Semoga bermanfaat!