Linked List - ifzahri/cpp GitHub Wiki
Linked list adalah struktur data yang disusun secara linear. Tidak seperti array, elemen dari linked list tidak disimpan dalam lokasi yang kontinu, melainkan elemen tersebut dihubungkan menggunakan pointers.
Linked list terdiri dari beebrapa struktur, yang mana tidak seharusnya bergantung pada memori. Setiap struktur terdiri dari elemen dan pointer ke struktur yang berisi sebuah suksesor, atau pointer berikutnya.
- Simple Linked List
Jenis ini dapat bergerak melalui list yang dibuat secara searah yang mengarahkan ke pointer berikutnya dari setiap node ke node lainnya. Namun, pointer yang ada pada node terakhir akan menghasilkan NULL. Jenis ini dapat dikatakan sebagai "Singly Linked List"
- Doubly Linked List
Pergerakan yang ada pafa jenis ini dapat bergerak secara dua arah (maju dan mundur)
- Circular Linked List
Pada jenis ini, node terakhir pada list berisi link kepada node pertama pada list tersebut.
- Doubly Circular Linked List
Doubly Circular adalah Circular Linked List yang bisa bergerak secara dua arah. Pada jenis ini, pointernya terdiri dari node setelahnya dan sebelumnya.
- Header Linked List
Linked List ini memiliki header node pada awal list.
Linked List terdiri dari pointer kepada node pertama dari list. Node pertama memiliki isitlah head dari linked list. Apabila linked list kosong, maka value dari head adalah NULL. Setiap ndoe pada list terdiri dari dua bagian
- Data Item (tempat menyimpan data (char, string, integer)
- Pointer/Reference di node berikutnya (untuk menghubungkan node ke node lainnya) atau alamat ke node lainnya.
Linked List pada C
struct Node {
int data;
struct Node* next;
};Linked List pada C++
class Node {
public:
int data;
Node* next;
};Berikut adalah contoh program simple linked list menggunakan tiga node (C++)
#include<bits/stdc++.h>
using namespace std;
class Node
{
private:
public:
int data;
Node* next;
};
void printList(Node* n)
{
while (n != NULL) {
cout<<n->data<<" ";
n = n->next;
}
}
int main(int argc, char const *argv[])
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printList(head);
return 0;
}Dasar operasi yang dapat dilakukan di Linked List ini adalah
Metode insertion pada node dapat dilakukan dengan tiga cara, yaitu
- Di depan list
Node baru akan selalu berada di depan head dari List, dan node baru akan menjadi head baru dari list tersebut. Apabila diberikan List 10->15->20->25 dan node 5 ditambahkan di depan, maka List akan menjadi 5->10->15->20->25 dan 5 akan menjadi head baru di list tersebut. Apabila diasumsikan sebuah function untuk menambahkan node di depan list adalah push(), maka push() harus menerima sebuah pointer ke head pointer karena push() harus merubah head pointer sebelumnya untuk diarahkan ke node yang baru. Untuk selengkapnya, Baca di sini
Berikut adalah salah satu contoh penggunaan metode menambahkan node di depan (C++)
void push(Node** head_ref, int new_data)
{
// inisialisasi node
Node* new_node = new Node();
// masukkan data
new_node->data = new_data;
// next pada node baru sebagai head
new_node->next = (*head_ref);
// pindahkan head untuk diarahkan ke node baru
(*head_ref) = new_node;
}- Setelah node tertentu
Dalam menggunakan metode ini, diperlukan langkah-langkah sebagai berikut
- Cek apakah node sebelumnya adalah NULL atau tidak
- Inisialisasikan atau alokasikan node baru
- Masukkan data pada node yang baru
- Buat node setelah node baru menjadi node setelah node sebelumnya
- Ubah node sebelumnya sebagai node baru
void insertAfter(Node* prev_node, int new_data)
{
// cek apakah node sebelumya adalah NULL atau tidak
if (prev_node == NULL) {
cout << "The given previous node cannot be NULL";
return;
}
// inisialisasikan node baru
Node* new_node = new Node();
// masukkan data
new_node->data = new_data;
// buat node setelah node baru menjadi lanjutan dari node ebelumnya
new_node->next = prev_node->next;
// pindahkan lanjutan dari node sebelumnya sebagai node bari
prev_node->next = new_node;
}- Di belakang list
Node baru akan selalu ditambahkan setelah node terakhir apa sebuah list, apabila kita ingin menambahkan 30 pada list 5->10->15->20->25, maka listnya akan menjadi 5->10->15->20->25->30. Karena Linked List biasa direpresentasikan oleh head list tersebut, maka, algoritma perlu mengeksplorasi hingga ujung list dan merubah node sebelum node terakhir menjadi node baru
void append(Node** head_ref, int new_data)
{
// inisialisasi node
Node* new_node = new Node();
// inisialisasi eksplorasi list
Node *last = *head_ref;
// memasukkan data
new_node->data = new_data;
// karena node ini akan menjadi node terakhir
// maka jadikan node selanjutnya sebagai NULL
new_node->next = NULL;
// apabila list kosong, maka buat node baru sebagai head
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
// selain itu, eksplorasi list sampai node terakhir
while (last->next != NULL)
{
last = last->next;
}
// ubah node lanjutan dari node terakhir
last->next = new_node;
return;
} Dalam menghaps node, maka dapat dilakukan dengan cara
- Cari terlebih dahulu node di depan node yang akan dihapus
- Ubah lanjutan dari node tersebut
- Manfaatkan
freeuntuk menghapus node
#include <bits/stdc++.h>
using namespace std;
struct Node {
int number;
Node* next;
};
void Push(Node** head, int A)
{
Node* n = (Node*)malloc(sizeof(Node));
n->number = A;
n->next = *head;
*head = n;
}
void deleteN(Node** head, int position)
{
Node* temp;
Node* prev;
temp = *head;
prev = *head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
*head = (*head)->next;
free(temp);
}
else {
if (i == position - 1 && temp) {
prev->next = temp->next;
free(temp);
}
else {
prev = temp;
// Position was greater than
// number of nodes in the list
if (prev == NULL)
break;
temp = temp->next;
}
}
}
}
void printList(Node* head)
{
while (head) {
if(head->next == NULL)
cout << "[" << head->number << "] " << "[" << head << "]->" << "(nil)" << endl;
else
cout << "[" << head->number << "] " << "[" << head << "]->" << head->next << endl;
head = head->next;
}
cout << endl << endl;
}
// Driver code
int main()
{
Node* list = (Node*)malloc(sizeof(Node));
list->next = NULL;
Push(&list, 1);
Push(&list, 2);
Push(&list, 3);
printList(list);
// Delete any position from list
deleteN(&list, 1);
printList(list);
return 0;
}Dalam mencari elemen pada list, maka dapat memanfaatkan fitur looping dengan algoritma:
- Jadikan head sebagai titik awal
- Jalankan looping sampai list tersebut memunculkan NULL
- Pada setiap iterasi looping, lakukan pengecekan apakah node tersebut sama dengan apa yang kita cari. Apabila cocok, maka return true. Dan sebaliknya, lakukan return false.
bool searchNode(struct Node** head_ref, int key) {
struct Node* current = *head_ref;
while (current != NULL) {
if (current->data == key) return true;
current = current->next;
}
return false;
}Kita bisa melakukan kombinasi algoritma bubble sort untuk melakukan sortir pada elemen atau node dari linked list.
- Jadikan head sebagai node awal dan buat node lain, bernama index
- Apabila head berisi NULL, maka return
- Selain itu, jalankan loop sampai NULL (node terakhir)
- Pada setiap iterasi, simpan node berikutnya pada index
- Lakukan pengecekan node untuk menentukan mana yang lebih besar. Kalau lebih besar, tukar node saat ini dan index
// Sort the linked list
void sortLinkedList(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;
if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}