Bağlı Liste
Son güncelleme
Bir bağlı liste, bir diziyi düğümler zinciri olarak saklar; her düğüm bir değer ve bir sonraki düğüme bir işaretçi tutar. Bir diziden farklı olarak düğümler bellekte bitişik değildir; listeyi dolaşmak için next işaretçilerini takip edersiniz. Düğümlerin başa ve sona bağlanmasını, zinciri dolaşarak bir değerin aranmasını ve bir işaretçinin yeniden bağlanmasıyla bir düğümün kaldırılmasını izlemek için yukarıdan oynat'a basın.
Başa ekleme veya silme O(1)'dir çünkü sadece başı yeniden işaret edersiniz. Ortadaki bir konuma veya sona ulaşmak O(n)'dir çünkü önce oraya kadar yürümeniz gerekir. Bu ödünleşim -ucuz uçlar, rastgele erişim yok- bir bağlı listeyi bir diziden ayıran şeydir.
Zaman karmaşıklığı
| İşlem | Karmaşıklık | Notlar |
|---|---|---|
| Başa ekleme | O(1) | Başı yeniden işaret et |
| Sona ekleme | O(n) | Önce sona kadar yürü (kuyruk işaretçisiyle O(1)) |
| Arama | O(n) | next işaretçilerini takip et |
| Başı silme | O(1) | Başı onun ötesine yeniden işaret et |
| İndeksle erişim | O(n) | Rastgele erişim yok |
Bağlı liste vs dizi
| Boyut | Bağlı liste | Dizi |
|---|---|---|
| Bellek | Dağınık düğümler + işaretçiler | Bitişik blok |
| Rastgele erişim | O(n) | O(1) |
| Önden ekleme/silme | O(1) | O(n) (kaydırma) |
| Önbellek dostluğu | Kötü | İyi |
Çözümlü örnek
[10, 20] listesini oluşturma, başına 5 ekleme, ardından 20'yi silme:
| Adım | Yapı | Eylem |
|---|---|---|
| Başlangıç | head -> null | Boş liste |
| Başa 10 ekle | head -> 10 -> null | Başı, next'i eski baş (null) olan yeni bir düğüme yeniden işaret et |
| Sona 20 ekle | head -> 10 -> 20 -> null | 10 düğümüne yürü, next'ini yeni bir 20 düğümüne ayarla |
| Başa 5 ekle | head -> 5 -> 10 -> 20 -> null | Yeni düğüm 5 eski baş 10'a işaret eder; baş artık 5'e işaret eder |
| 20'yi sil | head -> 5 -> 10 -> null | 10'a yürü, next'ini 20'den null'a ayarla; 20 düğümünün bağı kesilir |
Bağlı liste ne zaman kullanılır
| Şu durumda kullan | Şu durumda kaçın |
|---|---|
| Uçlarda (veya elinizde tuttuğunuz bir düğümde) indekslemekten çok daha fazla ekleme veya silme yaparsanız | Konuma göre hızlı rastgele erişime ihtiyacınız varsa (O(1) indeksleme) |
| Boyut çok değişir ve yeniden boyutlandırma/kopyalama maliyeti istemezseniz | Önbellek yerelliğinin performansa hakim olduğu sıkı döngülerde gezinirseniz |
| Bir kuyruk, yığın veya komşuluk listesi oluşturuyorsanız | Bellek kısıtlıysa: her düğüm eleman başına ekstra bir işaretçi öder |
| Başka yerlerdeki eklemelerden sağ çıkan düğümlere kararlı referanslara ihtiyacınız varsa | Çoğunlukla okur ve nadiren değiştirirseniz, bu durumda bir dizi daha basit ve hızlıdır |
Linked List kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Linked List uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Linked List kodu
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)JavaScript ile Linked List kodu
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(" -> "));Java ile Linked List kodu
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}C++ ile Linked List kodu
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}C ile Linked List kodu
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}Bağlı Liste SSS
Bağlı liste ile dizi arasındaki fark nedir?
Bir dizi elemanları tek bir bitişik blokta saklar, bu da
O(1) rastgele erişim ama elemanları kaydıran O(n) ekleme/silme sağlar. Bir bağlı liste, düğümleri bellekte herhangi bir yerde işaretçilerle bağlı olarak saklar, bu da bilinen bir konumda O(1) ekleme/silme ama zinciri dolaşmanız gerektiği için O(n) erişim sağlar.Bağlı listeyi ne zaman kullanmalıyım?
Bağlı listeler, uçlarda (veya zaten bir referansını tuttuğunuz bir düğümde) sık sık ekleme veya çıkarma yaptığınızda ve nadiren rastgele erişime ihtiyaç duyduğunuzda parlar; örneğin kuyruklar, yığınlar, komşuluk listeleri ve LRU önbellekleri. Hızlı indeksli erişime ihtiyacınız varsa, bir dizi veya dinamik dizi genellikle daha iyidir.
Bir bağlı listenin zaman karmaşıklığı nedir?
Başa ekleme veya silme
O(1)'dir. Arama veya kuyruk işaretçisi olmadan sona ulaşma O(n)'dir çünkü next işaretçilerini teker teker takip edersiniz. O(1) rastgele erişim yoktur: bir bağlı listeye indeksle erişmek O(n)'dir.Tek yönlü ve çift yönlü bağlı liste arasındaki fark nedir?
Tek yönlü bağlı liste düğüm başına yalnızca bir
next işaretçisi saklar, bu yüzden tek yönde dolaşabilirsiniz ve bir düğümü silmek öncülüne bir referans gerektirir. Çift yönlü bağlı liste bir prev işaretçisi ekler ve geriye doğru dolaşmayı ve elinizdeki bir düğümün O(1) silinmesini sağlar; bunun bedeli düğüm başına ekstra bir işaretçi ve her ekleme ve silmede daha fazla defter tutmadır.Başa ekleme O(1) ise neden sona ekleme O(n)?
Başa ekleme yalnızca
head işaretçisini yeniden bağlar, bu da sabit iştir. Sona ulaşmak, baştan sona kadar next işaretçilerini takip etmek anlamına gelir, bu da O(n)'dir. Ayrı bir tail işaretçisi tutmak sona eklemeyi de O(1) yapar, bu yüzden gerçek dünyadaki listeler genellikle her iki ucu da izler.Bağlı listelerde her yerde O(1) ekleme var mı?
Hayır, bu yaygın bir yanılgıdır. Eklemenin kendisi yalnızca sonrasına eklediğiniz düğüme zaten bir işaretçi tuttuğunuzda
O(1)'dir. O konumu değere veya indekse göre bulmak yine de O(n) maliyetindedir çünkü oraya ulaşmak için zinciri dolaşmanız gerekir.İlgili kaynaklar
Daha fazla görselleştirme
