Linked List
Terakhir diperbarui
Linked list adalah struktur data yang menyimpan urutan data sebagai rantai node, dan setiap node menyimpan sebuah nilai serta pointer ke node berikutnya. Tidak seperti array, node-node itu tidak bersebelahan di memori: kamu mengikuti pointer next untuk menelusuri list. Tekan Putar di atas untuk melihat node ditautkan di head dan tail, sebuah nilai dicari dengan menyusuri rantai, dan sebuah node dihapus dengan menautkan ulang pointer.
Menyisipkan atau menghapus di head bernilai O(1) karena kamu cukup mengarahkan ulang head. Mencapai posisi di tengah atau di tail bernilai O(n) karena kamu harus menelusurinya dulu. Pertukaran itu, ujung yang murah tanpa akses acak, adalah pembeda linked list dari array.
Kompleksitas waktu
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Sisipkan di head | O(1) | Arahkan ulang head |
| Sisipkan di tail | O(n) | Telusuri sampai akhir dulu (O(1) dengan pointer tail) |
| Pencarian | O(n) | Ikuti pointer next |
| Hapus head | O(1) | Arahkan head melewatinya |
| Akses berdasarkan indeks | O(n) | Tidak ada akses acak |
Linked list vs array
| Aspek | Linked list | Array |
|---|---|---|
| Memori | Node tersebar + pointer | Satu blok bersebelahan |
| Akses acak | O(n) | O(1) |
| Sisipkan/hapus di depan | O(1) | O(n) (pergeseran) |
| Ramah cache | Buruk | Baik |
Contoh penerapan
Membangun list [10, 20], menambahkan 5 di depan, lalu menghapus 20:
| Langkah | Struktur | Aksi |
|---|---|---|
| Mulai | head -> null | List kosong |
| Sisipkan 10 di head | head -> 10 -> null | Arahkan head ke node baru yang next-nya adalah head lama (null) |
| Sisipkan 20 di tail | head -> 10 -> 20 -> null | Telusuri sampai node 10, atur next-nya ke node baru 20 |
| Sisipkan 5 di head | head -> 5 -> 10 -> 20 -> null | Node baru 5 menunjuk ke head lama 10; head kini menunjuk ke 5 |
| Hapus 20 | head -> 5 -> 10 -> null | Telusuri sampai 10, ubah next-nya dari 20 menjadi null; node 20 terlepas dari list |
Kapan memakai linked list
| Pakai saat | Hindari saat |
|---|---|
| Kamu jauh lebih sering menyisipkan atau menghapus di ujung (atau di node yang kamu pegang) daripada mengakses lewat indeks | Kamu butuh akses acak yang cepat berdasarkan posisi (pengindeksan O(1)) |
| Ukurannya sering berubah dan kamu tidak mau ada biaya resize/salin | Kamu menjalankan loop ketat yang performanya didominasi lokalitas cache |
| Kamu sedang membangun queue, stack, atau adjacency list | Memori terbatas: setiap node menanggung satu pointer tambahan per elemen |
| Kamu butuh referensi node yang stabil dan tetap berlaku meski ada penyisipan di tempat lain | Kamu lebih sering membaca dan jarang mengubah, jadi array lebih sederhana dan lebih cepat |
Kode Linked List
Implementasi Linked List yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Linked List dalam Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Kode Linked List dalam JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Kode Linked List dalam Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Kode Linked List dalam C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Kode Linked List dalam C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}FAQ Linked List
Apa perbedaan linked list dan array?
Array menyimpan elemen dalam satu blok yang bersebelahan, sehingga memberi akses acak
O(1) tetapi penyisipan/penghapusan O(n) karena elemen harus digeser. Linked list menyimpan node di mana saja di memori dan menghubungkannya dengan pointer, sehingga memberi penyisipan/penghapusan O(1) di posisi yang sudah diketahui tetapi akses O(n) karena kamu harus menyusuri rantainya.Kapan sebaiknya memakai linked list?
Linked list unggul saat kamu sering menyisipkan atau menghapus di ujung (atau di node yang referensinya sudah kamu pegang) dan jarang butuh akses acak, misalnya untuk queue, stack, adjacency list, dan LRU cache. Jika kamu butuh akses cepat berdasarkan indeks, array atau dynamic array biasanya lebih baik.
Berapa kompleksitas waktu linked list?
Menyisipkan atau menghapus di head bernilai
O(1). Mencari, atau mencapai tail tanpa pointer tail, bernilai O(n) karena kamu mengikuti pointer next satu per satu. Tidak ada akses acak O(1): mengakses linked list lewat indeks bernilai O(n).Apa perbedaan singly dan doubly linked list?
Singly linked list hanya menyimpan pointer
next per node, jadi kamu bisa menelusuri ke satu arah saja dan menghapus sebuah node membutuhkan referensi ke node pendahulunya. Doubly linked list menambahkan pointer prev, sehingga memungkinkan penelusuran mundur dan penghapusan O(1) untuk node yang kamu pegang, dengan harga satu pointer tambahan per node dan pencatatan yang lebih banyak pada setiap penyisipan dan penghapusan.Mengapa menyisipkan di tail bernilai O(n) jika menyisipkan di head bernilai O(1)?
Menyisipkan di head hanya menautkan ulang pointer
head, yang merupakan kerja konstan. Mencapai tail berarti mengikuti pointer next dari head sampai ke ujung, yang bernilai O(n). Menyimpan pointer tail terpisah membuat penyisipan di tail juga O(1), itulah sebabnya list di dunia nyata sering mencatat kedua ujungnya.Apakah linked list punya penyisipan O(1) di mana saja?
Tidak, ini salah kaprah yang umum. Penyisipannya sendiri hanya bernilai
O(1) jika kamu sudah memegang pointer ke node tempat kamu akan menyisipkan setelahnya. Mencari posisi itu berdasarkan nilai atau indeks tetap berbiaya O(n) karena kamu harus menyusuri rantai untuk sampai ke sana.Sumber terkait
Visualisasi lainnya
