LinkedList Veri Yapısı

Bu eğitimde, bağlantılı liste veri yapısı ve Python, Java, C ve C ++ 'da uygulanması hakkında bilgi edineceksiniz.

Bağlantılı liste veri yapısı, bir dizi bağlı düğüm içerir. Burada her düğüm, verileri ve sonraki düğümün adresini depolar. Örneğin,

LinkedList Veri Yapısı

Bir yerden başlamalısınız, bu yüzden ilk düğümün adresine HEAD adında özel bir ad veriyoruz.

Ayrıca, bağlantılı listedeki son düğüm, bir sonraki bölümü NULL'a işaret ettiği için tanımlanabilir.

Her ipucunun bir sonraki ipucuyla ilgili bilgileri içerdiği Treasure Hunt oyununu oynamış olabilirsiniz. Bağlantılı liste bu şekilde işler.

LinkedList'in Temsili

LinkedList'in her bir düğümünün nasıl temsil edildiğini görelim. Her düğüm şunlardan oluşur:

  • Bir veri öğesi
  • Başka bir düğümün adresi

Hem veri öğesini hem de sonraki düğüm referansını bir yapıda şu şekilde sarıyoruz:

 struct node ( int data; struct node *next; );

Bağlantılı bir liste düğümünün yapısını anlamak, onu kavramanın anahtarıdır.

Her yapı düğümünün bir veri öğesi ve başka bir yapı düğümüne bir işaretçisi vardır. Bunun nasıl çalıştığını anlamak için üç öğeli basit bir Bağlantılı Liste oluşturalım.

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;

Yukarıdaki satırlardan hiçbirini anlamadıysanız, ihtiyacınız olan tek şey işaretçiler ve yapılar hakkında tazeleme yapmaktır.

Sadece birkaç adımda, üç düğümlü basit bir bağlantılı liste oluşturduk.

LinkedList Gösterimi

LinkedList'in gücü, zinciri kırıp yeniden birleştirme yeteneğinden gelir. Örneğin, 1 ile 2 arasına bir 4 öğesi koymak isterseniz, adımlar şöyle olacaktır:

  • Yeni bir yapı düğümü oluşturun ve ona bellek ayırın.
  • Veri değerini 4 olarak ekleyin
  • Bir sonraki işaretçisini, veri değeri olarak 2 içeren yapı düğümünün üzerine getirin
  • Bir sonraki "1" işaretçisini yeni oluşturduğumuz düğüme değiştirin.

Bir dizide benzer bir şey yapmak, sonraki tüm öğelerin konumlarını değiştirmeyi gerektirecekti.

Python ve Java'da, bağlantılı liste aşağıdaki kodlarda gösterildiği gibi sınıflar kullanılarak uygulanabilir.

Bağlantılı Liste Yardımcı Programı

Listeler, C, C ++, Python, Java ve C # gibi her programlama dilinde uygulanabilen en popüler ve verimli veri yapılarından biridir.

Bunun dışında bağlantılı listeler, işaretçilerin nasıl çalıştığını öğrenmenin harika bir yoludur. Bağlantılı listeleri nasıl değiştireceğinizi uygulayarak, kendinizi grafikler ve ağaçlar gibi daha gelişmiş veri yapılarını öğrenmeye hazırlayabilirsiniz.

Python, Java, C ve C ++ Örneklerinde Bağlantılı Liste Uygulamaları

Python Java C C + 
 # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next 
 // Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
 // Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
 // Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )

Bağlantılı Liste Karmaşıklığı

Zaman Karmaşıklığı

En kötü durumda Ortalama Vaka
Arama O (n) O (n)
Ekle O (1) O (1)
Silme O (1) O (1)

Uzay Karmaşıklığı: O (n)

Bağlantılı Liste Uygulamaları

  • Dinamik bellek ayırma
  • Yığın ve kuyrukta uygulanır
  • Gelen geri alma yazılımların işlevselliği
  • Karma tablolar, Grafikler

Önerilen Okumalar

1. Eğiticiler

  • LinkedList İşlemleri (Travers, Insert, Delete)
  • LinkedList Türleri
  • Java LinkedList

2. Örnekler

  • LinkedList'in orta öğesini tek bir yinelemede alın
  • LinkedList'i bir Diziye dönüştürün ve tersini yapın
  • LinkedList içinde döngü algılama

Ilginç makaleler...