Python'da Bağlantılı Listeler - Plato AiStream V2.1

Plato tarafından yeniden yayınlandı

İzleyiciler: 0

Giriş

Bağlantılı Liste, her biri bir değer ve dizideki bir sonraki düğüme referans içeren bir dizi düğümden oluşan bir veri yapısıdır. Dizilerden farklı olarak Bağlantılı Listeler, bitişik bellek tahsisi gerektirmez, bu da onları belirli işlemler için daha esnek ve verimli hale getirir. Bu yazıda Bağlantılı Listelerin avantajlarını ve dezavantajlarını ve bunların Python'da nasıl uygulanacağını inceleyeceğiz.

İçindekiler

Bağlantılı Listelerin Avantajları ve Dezavantajları

Bağlantılı Listeler diğer veri yapılarına göre çeşitli avantajlar sunar. İlk olarak, yalnızca komşu düğümlerin referanslarının güncellenmesini gerektirdiğinden, öğelerin etkili bir şekilde eklenmesine ve silinmesine olanak tanırlar. Bu, LinkedList'leri sık değişiklik yapılmasının beklendiği senaryolar için ideal kılar. Ek olarak, LinkedList'lerin boyutu sabit bir boyuta sahip olan dizilerin aksine dinamik olarak büyüyebilir veya küçülebilir.

Ancak Bağlantılı Listelerin bazı dezavantajları da vardır. Dizilerden farklı olarak Bağlantılı Listeler öğelere rastgele erişimi desteklemez; bu, belirli bir dizindeki bir öğeye erişmenin listenin başından itibaren geçilmesini gerektirdiği anlamına gelir. Bu, belirli işlemlerde performansın yavaşlamasına neden olabilir. Ayrıca Bağlantılı Listeler, sonraki düğümlere yapılan referansları depolamak için ekstra bellek gerektirir ve bu, küçük veri kümeleri için verimsiz olabilir.

Python'da Bağlantılı Listelerin Uygulanması

Python, Bağlantılı Listeleri uygulamak için esnek ve sezgisel bir yol sağlar. Üç ana Bağlantılı Liste türü vardır: Tek Bağlantılı Liste, Çift Bağlantılı Liste ve Dairesel Bağlantılı Liste. Her birini ayrıntılı olarak inceleyelim.

Tek Bağlantılı Liste

Tek Bağlantılı Liste, her düğümün bir değer ve sıradaki bir sonraki düğüme referans içerdiği düğümlerden oluşur. Python'da Tek Bağlantılı Listeyi şu şekilde oluşturabilirsiniz:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Linked List:
    def __init__(self):
        self.head = None

Tek Bağlantılı Liste Oluşturma

Tek Bağlantılı Liste oluşturmak için listedeki her düğümü temsil eden bir Node sınıfı tanımlamamız gerekir. Her düğüm bir değer ve bir sonraki düğüme referans içerir. Bağlantılı Liste sınıfı, düğümler için kapsayıcı görevi görür ve head özelliği listedeki ilk düğüme işaret eder.

Tek Bağlantılı Listeye Düğümler Ekleme

Tek Bağlantılı Listeye düğüm eklemek, komşu düğümlerin referanslarının güncellenmesini içerir. Aşağıda listenin başına düğüm eklemeye ilişkin bir örnek verilmiştir:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Tek Bağlantılı Listeden Düğümleri Silme

Tek Bağlantılı Listeden düğümlerin silinmesi, komşu düğümlerin referanslarının güncellenmesini gerektirir. Belirli bir değere sahip bir düğümün silinmesine bir örnek:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Tek Bağlantılı Listede Arama Yapmak

Tek Bağlantılı Listede belirli bir değerin aranması, değer bulunana veya listenin sonuna ulaşılıncaya kadar listede dolaşmayı içerir. Aşağıda bir değer aramaya ilişkin bir örnek verilmiştir:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Tek Bağlantılı Listeyi Tersine Çevirmek

Tek Bağlantılı Listeyi tersine çevirmek, her düğümün referanslarının bir önceki düğüme işaret edecek şekilde güncellenmesini gerektirir. Tek Bağlantılı Listeyi tersine çevirmenin bir örneği:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Çift Bağlantılı Liste

Çift Bağlantılı Liste, Tek Bağlantılı Listeye benzer, ancak her düğüm, dizideki hem sonraki düğüme hem de önceki düğüme bir referans içerir. Bu, her iki yönde de verimli geçişe olanak tanır. Python'da Çift Bağlantılı Listeyi nasıl oluşturabileceğiniz aşağıda açıklanmıştır:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.previous = None

class DoublyLinked List:
    def __init__(self):
        self.head = None

Çift Bağlantılı Liste Oluşturma

Çift Bağlantılı Liste oluşturmak için bir değer, bir sonraki düğüme bir referans ve bir önceki düğüme bir referans içeren bir Node sınıfı tanımlarız. DoublyLinked List sınıfı, düğümler için kapsayıcı görevi görür ve head özelliği listedeki ilk düğüme işaret eder.

Çift Bağlantılı Listeye Düğümler Ekleme

Çift Bağlantılı Listeye düğüm eklemek, komşu düğümlerin referanslarının güncellenmesini içerir. Aşağıda listenin başına düğüm eklemeye ilişkin bir örnek verilmiştir:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Çift Bağlantılı Listeden Düğümleri Silme

Çift Bağlantılı Listeden düğümlerin silinmesi, komşu düğümlerin referanslarının güncellenmesini gerektirir. Belirli bir değere sahip bir düğümün silinmesine bir örnek:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Çift Bağlantılı Listede Arama Yapmak

Çift Bağlantılı Listede belirli bir değeri aramak, değer bulunana veya listenin sonuna ulaşılana kadar listeyi her iki yönde de hareket ettirmeyi içerir. Aşağıda bir değer aramaya ilişkin bir örnek verilmiştir:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Çift Bağlantılı Listeyi Tersine Çevirmek

Çift Bağlantılı Listeyi tersine çevirmek, sonraki ve önceki işaretçileri değiştirmek için her düğümün referanslarının güncellenmesini gerektirir. İşte Çift Bağlantılı Listeyi tersine çevirmenin bir örneği:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Dairesel Bağlantılı Liste

Dairesel Bağlantılı Liste, son düğümün ilk düğüme işaret ettiği ve dairesel bir yapı oluşturduğu Tek Bağlantılı Liste'nin bir varyasyonudur. Bu, listedeki herhangi bir düğümden verimli geçiş yapılmasına olanak tanır. Python'da Döngüsel Bağlantılı Listeyi şu şekilde oluşturabilirsiniz:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinked List:
    def __init__(self):
        self.head = None

Dairesel Bağlantılı Liste Oluşturma

Dairesel Bağlantılı Liste oluşturmak için bir değer ve bir sonraki düğüme referans içeren bir Node sınıfı tanımlarız. CircularLinked List sınıfı, düğümler için kapsayıcı görevi görür; head özelliği listedeki ilk düğüme işaret eder. Ek olarak son düğümün bir sonraki referansı başa ayarlanarak dairesel bir yapı oluşturulur.

Dairesel Bağlantılı Listeye Düğümler Ekleme

Dairesel Bağlantılı Listeye düğüm eklemek, komşu düğümlerin referanslarının güncellenmesini içerir. Aşağıda listenin başına düğüm eklemeye ilişkin bir örnek verilmiştir:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Dairesel Bağlantılı Listeden Düğümleri Silme

Dairesel Bağlantılı Listeden düğümlerin silinmesi, komşu düğümlerin referanslarının güncellenmesini gerektirir. Belirli bir değere sahip bir düğümün silinmesine bir örnek:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Dairesel Bağlantılı Listede Arama Yapmak

Dairesel Bağlantılı Listede belirli bir değerin aranması, değer bulunana veya listenin tamamı geçilene kadar listenin geçilmesini içerir. Aşağıda bir değer aramaya ilişkin bir örnek verilmiştir:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Dairesel Bağlantılı Listeyi Tersine Çevirmek

Dairesel Bağlantılı Listeyi tersine çevirmek, dairesel yapıyı tersine çevirmek için her düğümün referanslarının güncellenmesini gerektirir. İşte Dairesel Bağlantılı Listeyi tersine çevirmenin bir örneği:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Bağlantılı Listelerdeki Ortak İşlemler

Bağlantılı Listeler, öğeler üzerinde gerçekleştirilebilecek çeşitli ortak işlemleri destekler. Bu işlemlerden bazılarını inceleyelim:

Bağlantılı Listedeki Öğelere Erişim

Bağlantılı Listedeki öğelere erişmek için, baş düğümden başlayarak listeyi dolaşabilir ve istenen konuma ulaşana kadar bir sonraki düğüme gidebiliriz. Belirli bir dizindeki bir öğeye erişmenin bir örneği:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Bağlantılı Listedeki Öğeleri Değiştirme

Bağlantılı Listedeki öğeleri değiştirmek, istenen öğeyi bulmak için listeyi dolaşmayı ve değerini güncellemeyi içerir. Belirli bir dizindeki bir öğeyi değiştirmenin bir örneği:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Bağlantılı Listenin Uzunluğunu Bulma

Bağlantılı Listenin uzunluğunu bulmak için listeyi dolaşabilir ve düğüm sayısını sayabiliriz. Bağlantılı Listenin uzunluğunu bulmanın bir örneğini burada bulabilirsiniz:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Bağlantılı Listenin Boş olup olmadığını kontrol etme

Bağlantılı Listenin boş olup olmadığını kontrol etmek için baş düğümün Yok olup olmadığını kontrol edebiliriz. Bağlantılı Listenin boş olup olmadığını kontrol etmeye bir örnek:

def is_empty(self):
    return self.head is None

Bağlantılı Listeleri Birleştirme

İki Bağlantılı Listeyi birleştirmek için, ilk listeyi geçerek son düğümü bulabilir ve bir sonraki referansını ikinci listenin başına güncelleyebiliriz. İki Bağlantılı Listeyi birleştirmenin bir örneğini burada bulabilirsiniz:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Bağlantılı Liste ve Dizi

Bağlantılı Listeler ve diziler yaygın olarak kullanılan veri yapılarıdır ancak onları farklı senaryolara uygun kılan farklı özelliklere sahiptirler. Bağlantılı Listeleri ve dizileri bellek verimliliği, ekleme ve silme verimliliği ve rastgele erişim verimliliği açısından karşılaştıralım.

Bellek Verimliliği

Bağlantılı Listeler, bitişik bellek tahsisi gerektirmedikleri için dizilerden daha fazla bellek verimlidir. Bağlantılı Listedeki her düğümün yalnızca değeri ve bir sonraki düğüme referansı saklaması gerekirken dizilerin, kullanılmasalar bile tüm öğeler için bellek ayırması gerekir.

Ekleme ve Silme Verimliliği

Bağlantılı Listeler, özellikle öğelerin sık sık listenin ortasına eklendiği veya listenin ortasından kaldırıldığı durumlarda, ekleme ve silme işlemlerinde mükemmeldir. Bağlantılı Listeye bir öğe eklemek veya silmek yalnızca komşu düğümlerin referanslarının güncellenmesini gerektirir; oysa diziler, değişikliğe uyum sağlamak için öğelerin kaydırılmasını gerektirebilir.

Rastgele Erişim Verimliliği

Diziler, doğrudan bellek adreslemesine izin verdikleri için indekslerine dayalı olarak öğelere verimli rastgele erişim sağlar. Bunun aksine, Bağlantılı Listeler, belirli bir dizindeki bir öğeye erişmek için listenin başından itibaren geçilmesini gerektirir, bu da rastgele erişim işlemleri için daha yavaş performansa neden olur.

Doğru Veri Yapısını Seçmek

Bağlantılı Listeler ve diziler arasındaki seçim, uygulamanın özel gereksinimlerine bağlıdır. Sık sık değişiklik yapılması ve dinamik yeniden boyutlandırma bekleniyorsa Bağlantılı Listeler daha iyi bir seçimdir. Öte yandan, rastgele erişim ve bellek verimliliği önemliyse diziler daha uygundur.

Bağlantılı Liste Uygulamaları

Artık bağlantılı listeleri ve nasıl çalıştıklarını iyi anladığımıza göre, bağlantılı listelerin etkili bir şekilde kullanılabileceği bazı pratik uygulamaları inceleyelim.

Ayrıca kayıt olabilirsiniz Ücretsiz Kurslar Bugün!

Yığınları ve Kuyrukları Uygulama

Bağlantılı listelerin en yaygın uygulamalarından biri yığınları ve kuyrukları uygulamaktır. Hem yığınlar hem de kuyruklar, bağlantılı listeler kullanılarak kolayca uygulanabilen soyut veri türleridir.

Yığın, Son Giren İlk Çıkar (LIFO) ilkesini izleyen bir veri yapısıdır. Öğeler, yığının tepesi olarak bilinen aynı uçtan eklenir ve çıkarılır. Bağlantılı listeler, listenin başına kolayca öğe ekleyebildiğimiz veya kaldırabildiğimiz için yığınları uygulamak için etkili bir yol sağlar.

Python'da bağlantılı bir liste kullanarak bir yığının uygulanmasına bir örnek:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

Öte yandan bir kuyruk, İlk Giren İlk Çıkar (FIFO) ilkesini izler. Öğeler arka olarak bilinen bir uçtan eklenir ve ön olarak bilinen diğer uçtan çıkarılır. Bağlantılı listeler, kuyrukları verimli bir şekilde uygulamak için de kullanılabilir.

Python'da bağlantılı bir liste kullanarak kuyruk uygulamaya bir örnek:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Büyük Veri Kümelerini İşleme

Bağlantılı listeler aynı zamanda büyük veri kümeleriyle uğraşırken de faydalıdır. Dizilerden farklı olarak bağlantılı listeler, bitişik bellek tahsisine ihtiyaç duymaz. Bu, bağlantılı listelerin, yeniden boyutlandırmaya veya yeniden tahsis etmeye gerek kalmadan, değişen boyutlardaki veri kümelerini verimli bir şekilde işleyebileceği anlamına gelir.

Örneğin milyonlarca kayıttan oluşan bir veri setimiz olduğunu ve ekleme, silme, geçiş gibi işlemleri yapmamız gerektiğini varsayalım. Bu görev için bir dizi kullanmak, ekleme veya silme sırasında öğelerin değiştirilmesini gerektirdiğinden verimsiz olabilir. Ancak bağlantılı bir listeyle işaretçileri güncelleyerek öğeleri kolayca ekleyebilir veya silebiliriz, bu da işlemlerin daha hızlı olmasını sağlar.

Grafik Geçiş Algoritmaları

Genişlik öncelikli arama (BFS) ve derinlik öncelikli arama (DFS) gibi grafik geçiş algoritmaları, bağlantılı listeler kullanılarak da uygulanabilir. Grafik geçişinde, bir grafikteki her köşeyi veya düğümü belirli bir sırayla ziyaret ederiz.

Bağlantılı listeler, bir grafiğin bitişiklik listesini temsil etmek için kullanılabilir; burada bağlantılı listedeki her düğüm bir tepe noktasını temsil eder ve bitişik köşeleri bağlantılı liste düğümleri olarak depolanır. Bu gösterim, grafiğin verimli bir şekilde geçişine ve araştırılmasına olanak tanır.

Polinom Gösterimi

Bağlı listeler polinomları verimli bir şekilde temsil etmek için kullanılabilir. Matematikte polinomlar değişkenlerden ve katsayılardan oluşan ifadelerdir. Bir polinomdaki her terim, katsayı ve üssün veri olarak saklandığı bağlantılı listedeki bir düğüm olarak temsil edilebilir.

Bağlantılı listeleri kullanarak polinomlar üzerinde toplama, çıkarma, çarpma gibi işlemleri kolaylıkla gerçekleştirebiliriz. Düğümler bu işlemleri gerçekleştirmek için manipüle edilebilir, bu da polinomların kısa ve etkili bir şekilde temsil edilmesini sağlar.

Müzik ve Video Oynatma Listeleri

Bağlantılı listeler genellikle müzik ve video oynatıcılarda oynatma listelerini uygulamak için kullanılır. Her şarkı veya video, verilerin medya dosyası hakkında bilgi içerdiği ve işaretçinin çalma listesindeki bir sonraki şarkıyı veya videoyu işaret ettiği bağlantılı bir listede bir düğüm olarak temsil edilebilir.

Çalma listeleri için bağlantılı listelerin kullanılması, şarkılar veya videolar arasında kolay gezinmeye olanak tanır. Sorunsuz bir kullanıcı deneyimi sağlayarak işaretçileri güncelleyerek çalma listesine kolayca şarkı ekleyebilir veya kaldırabiliriz.

Sonuç

Sonuç olarak bağlantılı listeler, çeşitli alanlarda uygulama bulan çok yönlü veri yapılarıdır. Yığınları ve kuyrukları uygulamak, büyük veri kümelerini yönetmek, grafik geçişi gerçekleştirmek, polinomları temsil etmek ve çalma listeleri oluşturmak için kullanılabilirler. Bağlantılı listeler, dinamik bellek tahsislerinden ve düğümlerin kolay manipülasyonundan yararlanarak bu sorunlara etkili çözümler sunar.

Bağlantılı listelerin uygulamalarını anlayarak programlarımız için veri yapılarını seçerken bilinçli kararlar verebiliriz. Verileri yönetmek, algoritmaları uygulamak veya kullanıcı dostu arayüzler oluşturmak olsun, bağlantılı listeler programcının araç setinde değerli bir araç sunar.

Bu nedenle, bir dahaki sefere verimli ekleme, silme veya geçiş gerektiren bir sorunla karşılaştığınızda, çözümünüzü basitleştirmek ve kodunuzu optimize etmek için bağlantılı listeleri kullanmayı düşünün.

Ayrıca Python Listeleri ile ilgili daha fazla makaleyi buradan okuyabilirsiniz:

Sık Sorulan Sorular

S1: Bağlantılı Liste nedir?

C: Bağlantılı Liste, her düğümün bir değer ve sıradaki bir sonraki düğüme bir referans (veya bağlantı) içerdiği düğümlerden oluşan bir veri yapısıdır.

S2: Bağlantılı Listeleri kullanmanın avantajları nelerdir?

C: Bağlantılı Listeler etkili ekleme ve silme işlemleri, dinamik yeniden boyutlandırma sunar ve bitişik bellek tahsisi gerektirmez.

S3: Bağlantılı Listelerin dezavantajları nelerdir?

C: Bağlantılı Listelerde rastgele erişim yoktur ve öğe erişimi için geçiş yapılması gerekir. Ayrıca referansları depolamak için fazladan bellek tüketirler ve bu da küçük veri kümeleri için verimsiz olabilir.

S4: Python'daki ana Bağlantılı Liste türleri nelerdir?

C: Bağlantılı Listelerin ana türleri Tek Bağlantılı Liste, Çift Bağlantılı Liste ve Dairesel Bağlantılı Listedir.

S5: Bağlantılı Listeler hangi senaryolarda dizilerden daha verimli bellek kullanır?

C: Bağlantılı Listeler, dinamik yeniden boyutlandırma ve sık ekleme veya silme işlemleriyle uğraşırken, bitişik bellek tahsisi gerektirmedikleri için bellek açısından dizilerden daha verimlidir.