Doubly Linked List
Terakhir diperbarui
Doubly linked list adalah linked list yang setiap node-nya menyimpan dua pointer: next (ke node berikutnya) dan prev (ke node sebelumnya). Tautan mundur tambahan itu membuatmu bisa menelusuri list ke dua arah dan menghapus sebuah node dalam O(1) jika kamu sudah punya referensinya, karena kamu bisa langsung mencapai node pendahulunya tanpa berjalan dari head. Tekan Putar di atas untuk melihat node ditautkan dan ditautkan ulang ke dua arah.
Harganya adalah satu pointer tambahan per node dan pencatatan yang lebih banyak: setiap penyisipan dan penghapusan harus memperbarui next dan prev pada node tetangganya. Struktur ini menjadi dasar banyak deque dan LRU cache, yang membutuhkan penghapusan cepat dari kedua ujung.
Kompleksitas waktu
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Sisipkan di head/tail | O(1) | Dengan pointer head dan tail |
| Hapus node yang sudah diketahui | O(1) | Langsung mencapai prev, tanpa menelusuri |
| Pencarian | O(n) | Tetap pemindaian linear |
| Akses berdasarkan indeks | O(n) | Tidak ada akses acak |
Singly vs doubly linked list
| Aspek | Singly | Doubly |
|---|---|---|
| Pointer per node | 1 (next) | 2 (next + prev) |
| Menelusuri mundur | Tidak | Ya |
| Hapus node yang sudah diketahui | O(n) (cari prev) | O(1) |
| Beban memori | Lebih rendah | Lebih tinggi |
Contoh penerapan
Membangun [10, 20, 30] dengan menambahkan di akhir, lalu menghapus node 20:
| Langkah | Struktur | Aksi |
|---|---|---|
| Mulai | null | List kosong: head dan tail sama-sama null |
| Tambahkan 10 | 10 | Node pertama; head dan tail sama-sama menunjuk ke node ini, prev = next = null |
| Tambahkan 20 | 10 <-> 20 | Atur 10.next = 20 dan 20.prev = 10; tail = 20 |
| Tambahkan 30 | 10 <-> 20 <-> 30 | Atur 20.next = 30 dan 30.prev = 20; tail = 30 |
| Hapus 20 | 10 <-> 30 | Dengan 20.prev dan 20.next: atur 10.next = 30 dan 30.prev = 10 dalam O(1) |
Kapan memakai doubly linked list
| Pakai saat | Hindari saat |
|---|---|
| Kamu perlu menelusuri atau menyambung list ke dua arah | Kamu hanya pernah bergerak maju: singly linked list lebih ringan |
Kamu menghapus node sembarang yang referensinya sudah kamu pegang (O(1)) | Kamu lebih sering mengakses berdasarkan posisi: pakai array untuk akses O(1) |
| Kamu mengimplementasikan deque, LRU cache, atau riwayat undo di layar | Memori terbatas: pointer prev tambahan menggandakan beban tautan |
| Penyisipan dan penghapusan sering terjadi di kedua ujung | Datanya kecil dan jarang berubah: menyalin array lebih murah |
Kode Doubly Linked List
Implementasi Doubly Linked List yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Doubly Linked List dalam Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Kode Doubly Linked List dalam JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Kode Doubly Linked List dalam Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Kode Doubly Linked List dalam C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Kode Doubly Linked List dalam C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}FAQ Doubly Linked List
Apa perbedaan singly dan doubly linked list?
Singly linked list punya satu pointer per node (
next), jadi kamu hanya bisa bergerak maju. Doubly linked list menambahkan pointer prev, sehingga kamu bisa menelusuri mundur dan menghapus node yang referensinya kamu pegang dalam O(1), dengan harga satu pointer tambahan per node dan pembaruan dua tautan pada setiap perubahan.Kapan doubly linked list sepadan dengan memori tambahannya?
Saat kamu butuh penelusuran mundur atau penghapusan
O(1) untuk node sembarang yang sudah kamu referensikan. Contoh klasiknya adalah deque (double-ended queue) dan LRU cache, yang entrinya sering dipindahkan dan dikeluarkan dari kedua ujung.Mengapa doubly linked list bisa menghapus node dalam O(1)?
Untuk menghapus sebuah node, kamu harus menyambungkan node pendahulunya dengan node penerusnya. Pada singly linked list, kamu harus berjalan dari head untuk menemukan pendahulunya (
O(n)); pada doubly linked list, pointer prev milik node itu langsung memberimu pendahulunya, jadi penautan ulangnya O(1).Doubly linked list vs array: mana yang sebaiknya dipakai?
Pakai array saat kamu butuh akses
O(1) berdasarkan indeks dan iterasi yang ramah cache, serta saat penyisipan kebanyakan terjadi di akhir. Pakai doubly linked list saat kamu sering menyisipkan atau menghapus di tengah atau di kedua ujung berdasarkan referensi node, karena itu bernilai O(1) dibandingkan pergeseran O(n) pada array. Array unggul dalam memori dan lokalitas; list unggul dalam perubahan struktur.Apa itu sentinel node pada doubly linked list?
Sentinel node (atau dummy node) adalah node pengganti yang berada sebelum head dan/atau setelah tail sehingga list tidak pernah benar-benar kosong. Node ini menghilangkan pengecekan
null untuk head, tail, serta penyisipan/penghapusan di batas list, sehingga setiap operasi mengikuti alur kode penautan ulang yang sama. Banyak implementasi LRU cache di produksi memakai dua sentinel untuk menghindari penanganan khusus di kedua ujung.Apa bug paling umum saat menghapus dari doubly linked list?
Lupa memperbarui
head atau tail saat menghapus node pertama atau terakhir, sehingga tersisa pointer menggantung ke node yang sudah dibebaskan. Selalu periksa apakah node.prev bernilai null (perbarui head) atau node.next bernilai null (perbarui tail) sebelum menautkan ulang node tetangganya.Sumber terkait
Visualisasi lainnya
