Python Bağlı Listeler: Örneklerle Eğitim

Bağlı liste, veri organizasyonu ve yönetiminde kritik rol oynayan bir veri yapısıdır. Bellekte rastgele konumlarda saklanan bir dizi düğüm içerir ve bu sayede bellek yönetimi verimli olur. Bağlı listedeki her düğüm iki ana bileşen barındırır: veri kısmı ve dizideki bir sonraki düğüme referans.

Bu kavram ilk bakışta karmaşık geliyorsa endişelenmeyin!

Bağlı listelerin ne olduğunu, neden kullandığımızı ve sundukları benzersiz avantajları açıklamak için konuyu temellerine ayıracağız.

Neden Bağlı Listeler?

Bağlı listeler, aşağıda özetlendiği gibi, verileri normal listeler ve dizilerde saklamanın çeşitli sakıncalarını gidermek için oluşturulmuştur:

Ekleme ve silme kolaylığı

Listelerde, sondan farklı bir konuma bir öğe eklemek veya silmek, izleyen tüm öğelerin konumlarının kaydırılmasını gerektirir. Bu işlemin zaman karmaşıklığı O(n)’dir ve özellikle listenin boyutu büyüdükçe performansı önemli ölçüde düşürebilir. Listelerin nasıl çalıştığına veya nasıl uygulandığına zaten aşina değilseniz, Python listeleriyle ilgili eğitimimizi okuyabilirsiniz.

Bağlı listeler ise farklı şekilde çalışır. Öğeleri ardışık olmayan, çeşitli bellek konumlarında saklar ve bunları bir sonraki düğümü işaret eden göstergelerle birbirine bağlar. Bu yapı, bağlı listelerin yalnızca bağlantıları değiştirerek yeni bir öğeyi dahil etmesini veya silineni atlamasını sağlayarak herhangi bir konumda öğe ekleyip çıkarmasına olanak tanır.

Öğenin konumu belirlendiğinde ve ekleme veya silme noktasına doğrudan erişim olduğunda, düğüm ekleme veya kaldırma işlemleri O(1) sürede gerçekleştirilebilir.

Dinamik boyut

Python listeleri dinamik dizilerdir; bu da boyutu değiştirmenize olanak tanır.

Ancak bu süreç, dizinin daha büyük bir bellek bloğuna yeniden ayrılması gibi bir dizi karmaşık işlemi içerir. Böyle bir yeniden ayırma verimsizdir; çünkü öğeler yeni bloğa kopyalanır ve hemen gerekenden daha fazla alan ayrılabilir.

Buna karşılık, bağlı listeler yeniden ayırma veya yeniden boyutlandırmaya gerek kalmadan dinamik olarak büyüyüp küçülebilir. Bu da onları yüksek esneklik gerektiren görevler için tercih edilir kılar.

Bellek verimliliği

Listeler, tüm öğeleri için belleği bitişik bir blokta ayırır. Bir liste ilk boyutunun ötesine geçecekse, yeni ve daha büyük bir bitişik bellek bloğu ayırmalı ve mevcut tüm öğeleri bu yeni bloğa kopyalamalıdır. Bu süreç özellikle büyük listeler için zaman alıcı ve verimsizdir. Öte yandan, listenin başlangıç boyutu fazla tahmin edilirse, kullanılmayan bellek boşa gider.

Buna karşılık, bağlı listeler her öğe için belleği ayrı ayrı ayırır. Bu yapı, yeni öğelere bellek eklenirken ayrılabildiği için daha iyi bellek kullanımına yol açar.

Bağlı Listeleri Ne Zaman Kullanmalısınız?

Bağlı listeler, dinamik boyut ve bellek verimliliği gibi normal listeler ve diziler karşısında bazı avantajlar sağlasa da, sınırlamaları da vardır. Her öğe için bir sonraki düğüme referans veren göstergelerin saklanması gerektiğinden, bağlı listelerde öğe başına bellek kullanımı daha yüksektir. Ayrıca bu veri yapısı veriye doğrudan erişime izin vermez. Bir öğeye erişmek, listenin başından itibaren sıralı olarak dolaşmayı gerektirir ve bu da O(n) arama zaman karmaşıklığına yol açar.

Bağlı liste veya dizi kullanma tercihi, uygulamanın özel ihtiyaçlarına bağlıdır. Bağlı listeler en çok şu durumlarda kullanışlıdır:

• Birçok öğeyi sık sık ekleyip silmeniz gerekiyorsa
• Veri boyutu öngörülemezse veya sık sık değişecekse
• Öğelere doğrudan erişim bir gereklilik değilse
• Veri kümesi büyük öğeler veya yapılar içeriyorsa

Bağlı liste türleri

Farklı senaryolar için benzersiz avantajlar sunan üç tür bağlı liste vardır. Bu türler şunlardır:

Tek yönlü bağlı listeler

Tek yönlü bağlı liste

Tek yönlü bağlı liste, en basit bağlı liste türüdür; her düğüm bazı veriler ve dizideki bir sonraki düğüme referans içerir. Yalnızca tek bir yönde—baş düğümden (ilk düğüm) son düğüme (son düğüm)—dolaşılabilir.

Tek yönlü bağlı listedeki her düğüm tipik olarak iki bölümden oluşur:

• Veri: Düğümde saklanan gerçek bilgi.
• Sonraki Gösterge: Bir sonraki düğüme referans. Son düğümün sonraki göstergesi genellikle null olarak ayarlanır.

Bu veri yapılarında yalnızca tek yönde dolaşılabildiği için, belirli bir öğeye değeri veya indeksiyle erişmek, baştan başlayıp istenen düğüm bulunana kadar düğümler boyunca sıralı olarak ilerlemeyi gerektirir. Bu işlemin zaman karmaşıklığı O(n)’dir ve büyük listeler için daha az verimlidir.

Tek yönlü bağlı listenin başına bir düğüm eklemek veya buradan silmek son derece verimlidir ve O(1) zaman karmaşıklığına sahiptir. Ancak, ortada ya da sonda ekleme ve silme işlemleri, o noktaya kadar listeyi dolaşmayı gerektirdiğinden O(n) zaman karmaşıklığına yol açar.

Tek yönlü bağlı listelerin tasarımı, listenin başında gerçekleşen işlemler için onları kullanışlı bir veri yapısı yapar.

Çift yönlü bağlı listeler

Çift yönlü bağlı liste

Tek yönlü bağlı listelerin bir dezavantajı, yalnızca tek yönde dolaşabilmemiz ve gerektiğinde önceki düğüme geri dönemememizdir. Bu kısıt, çift yönlü gezinme gerektiren işlemleri yapma becerimizi sınırlar.

Çift yönlü bağlı listeler, her düğüme ek bir gösterge ekleyerek bu sorunu çözer ve listenin her iki yönde de dolaşılmasını sağlar. Çift yönlü bağlı listedeki her düğüm üç öğe içerir: veri, bir sonraki düğüme gösterge ve önceki düğüme gösterge.

Dairesel bağlı listeler

Dairesel bağlı liste

Dairesel bağlı listeler, son düğümün ilk düğümü işaret ettiği, böylece dairesel bir yapı oluşturan özel bir bağlı liste türüdür. Bu, şimdiye kadar gördüğümüz tek ve çift yönlü bağlı listelerin aksine, dairesel bağlı listenin bitmediği; bunun yerine döngü yaptığı anlamına gelir.

Dairesel bağlı listelerin döngüsel doğası, son oyuncudan ilk oyuncuya geri dönülen kutu oyunları veya round-robin zamanlama gibi hesaplama algoritmaları gibi, sürekli döngü gerektiren senaryolar için idealdir.

Python’da Bağlı Liste Nasıl Oluşturulur

Artık bağlı listelerin ne olduğunu, neden kullandığımızı ve varyasyonlarını anladığımıza göre, bu veri yapılarını Python’da uygulamaya geçelim. Bu eğitime ait not defteri bu DataLab çalışma kitabında da mevcuttur; bir kopya oluşturursanız kodu düzenleyip çalıştırabilirsiniz. Kodu kendi ortamınızda çalıştırırken sorun yaşarsanız bu harika bir seçenektir!

Bir düğüm başlatma

Daha önce öğrendiğimiz gibi, düğüm; veriyi ve dizideki bir sonraki düğüme referansı saklayan, bağlı listedeki bir öğedir. Python’da bir düğümü şu şekilde tanımlayabilirsiniz:

class Node:
    def __init__(self, data):
        self.data = data  # Assigns the given data to the node
        self.next = None  # Initialize the next attribute to null

Yukarıdaki kod, iki temel işlem yaparak bir düğümü başlatır: Düğümün “data” niteliğine, düğümün içermesi amaçlanan gerçek bilgiyi temsil eden bir değer atanır. “next” niteliği ise bir sonraki düğümün adresini temsil eder. Bu, şu anda None olarak ayarlanmıştır; bu da listede başka bir düğüme bağlanmadığı anlamına gelir. Bağlı listeye yeni düğümler eklemeye devam ettikçe bu nitelik, bir sonraki düğümü gösterecek şekilde güncellenecektir.

Bağlı liste sınıfı oluşturma

Şimdi bağlı liste sınıfını oluşturmamız gerekiyor. Bu sınıf, ekleme ve kaldırma gibi düğümleri yönetmeye yönelik tüm işlemleri kapsayacaktır. Bağlı listeyi başlatarak başlayacağız:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

self.head’i None olarak ayarlayarak, bağlı listenin başlangıçta boş olduğunu ve işaret edilecek herhangi bir düğüm bulunmadığını belirtmiş oluyoruz. Şimdi yeni düğümler ekleyerek listeyi doldurmaya devam edeceğiz.

Bağlı listenin başına yeni bir düğüm ekleme

LinkedList sınıfı içinde, yeni bir düğüm oluşturup liste başına yerleştirecek bir yöntem ekleyeceğiz:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Yukarıdaki yöntemi her çağırdığınızda, belirttiğiniz veriye sahip yeni bir düğüm oluşturulur. Bu yeni düğümün next göstergesi, listenin mevcut başına ayarlanır; bu da düğümü mevcut düğümlerin önüne yerleştirir. Son olarak, yeni oluşturulan düğüm listenin başı yapılır.

Ekleme işleminin nasıl çalıştığını daha iyi anlamak için bu bağlı listeyi bir dizi kelimeyle dolduracağız. Bunu başarmak için önce liste içeriğini dolaşmak ve yazdırmak üzere tasarlanmış bir yöntem oluşturalım:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Yukarıdaki yöntem bağlı listemizin içeriğini yazdıracaktır. Şimdi tanımladığımız yöntemleri kullanarak listemizi şu kelime dizisiyle dolduralım: “the quick brown fox”.

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Yukarıdaki kod satırları aşağıdaki çıktıyı üretmelidir:

"the quick brown fox"

Bağlı listenin sonuna yeni bir düğüm ekleme

LinkedList sınıfı içinde, listenin sonuna yeni bir düğüm oluşturmak için insertAtEnd adlı bir yöntem oluşturacağız. Liste boşsa yeni düğüm listenin başı olur. Aksi halde, listeyi mevcut son düğüme ekler. Bunun pratikte nasıl çalıştığını görelim:

def insertAtEnd(self, new_data):
        new_node = Node(new_data)  # Create a new node
        if self.head is None:
            self.head = new_node  # If the list is empty, make the new node the head
            return
        last = self.head 
        while last.next:  # Otherwise, traverse the list to find the last node
            last = last.next
        last.next = new_node  # Make the new node the next node of the last node

Yukarıdaki yöntem yeni bir düğüm oluşturarak başlar. Ardından listenin boş olup olmadığını kontrol eder; boşsa yeni düğüm o listenin başı olarak atanır. Aksi halde, son düğümü bulmak için listeyi dolaşır ve bu düğümün göstergesini yeni düğüme ayarlar.

Şimdi bu yöntemi LinkedList sınıfımıza eklememiz ve listemizin sonuna bir kelime eklemek için kullanmamız gerekiyor. Bunu başarmak için ana fonksiyonunuzu şu şekilde değiştirin:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Dikkat ederseniz, listenin sonuna “jumps” kelimesini yazdırmak için yalnızca insertAtEnd yöntemini çağırdık. Yukarıdaki kod şu çıktıyı üretmelidir:

"the quick brown fox jumps"

Bağlı listenin başından bir düğüm silme

Bağlı listenin ilk düğümünü silmek kolaydır; çünkü yalnızca listenin başını ikinci düğümü gösterecek şekilde işaretlemeyi içerir. Bu şekilde ilk düğüm artık listenin parçası olmayacaktır. Bunu başarmak için LinkedList sınıfına aşağıdaki yöntemi ekleyin:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Bağlı listenin sonundan bir düğüm silme

Bağlı listenin son düğümünü silmek için, ikinci son düğümü bulmak üzere listeyi dolaşmalı ve onun next göstergesini None yapmalıyız. Bu şekilde son düğüm artık listenin parçası olmayacaktır. Bunu başarmak için aşağıdaki yöntemi LinkedList sınıfınıza kopyalayıp yapıştırın:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Yukarıdaki yöntem önce bağlı listenin boş olup olmadığını kontrol eder; boşsa kullanıcıya bir mesaj döndürür. Aksi halde, listede tek bir düğüm varsa o düğüm kaldırılır. Birden fazla düğüm içeren listeler için yöntem, ikinci son düğümü bulur ve bir sonraki düğüm referansını None olacak şekilde günceller.

Şimdi ana fonksiyonu, bağlı listenin başından ve sonundan öğeleri silecek şekilde güncelleyelim:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Yukarıdaki kod, bağlı listelerde ekleme ve silme işlemlerinin nasıl çalıştığını göstermek için, silme öncesi ve sonrası listeyi yazdıracaktır. Bu kodu çalıştırdıktan sonra aşağıdaki çıktıyı görmelisiniz:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Bağlı listede belirli bir değeri arama

Bu bölümde öğreneceğimiz son işlem, bağlı listedeki belirli bir değerin elde edilmesidir. Bunu başarmak için yöntem, listenin başından başlamalı ve her düğümün verisinin aranan değerle eşleşip eşleşmediğini kontrol ederek düğümler boyunca yinelemelidir. Bu işlemin pratik bir uygulaması şöyledir:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Oluşturduğumuz bağlı listede belirli değerleri bulmak için, az önce oluşturduğumuz arama yöntemini içerecek şekilde ana fonksiyonunuzu güncelleyin:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Yukarıdaki kod şu çıktıyı üretecektir:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

“quick” kelimesi, listenin ilk konumunda yer aldığı için bağlı liste içinde başarıyla bulunmuştur. Ancak “lazy” kelimesi listenin parçası değildir; bu nedenle bulunamamıştır.

Son Düşünceler

Buraya kadar geldiyseniz tebrikler! Bağlı listelerin yapısı, türleri, nasıl öğe ekleyip çıkardıkları ve nasıl dolaşıldıkları dahil olmak üzere temel ilkeleri artık sağlam bir şekilde anlıyorsunuz.

Ancak yolculuk burada bitmiyor. Bağlı listeler, veri yapıları ve algoritmalar dünyasının yalnızca başlangıcıdır. Konuya ilişkin bilginizi derinleştirmek için atabileceğiniz bazı sonraki adımlar şunlardır:

Kendi projenizi oluşturun

Bağlı listelerin pratik uygulamalarına, onları bir kodlama veya veri bilimi projesine entegre ederek dalın. Bağlı listeler dosya sistemleri geliştirmek, hash tabloları inşa etmek ve hatta GPS navigasyon sistemleri ile kutu oyunları oluşturmak için kullanılır. Kendi projelerinize başlamak için, Python, R ve SQL ile gerçek dünya problemlerini nasıl çözeceğinizi öğreten ücretsiz, rehberli veri bilimi projelerimize göz atın.

Veri yapıları ve algoritmalar hakkında bilgi edinin

Ağaçlar, yığınlar ve kuyruklar gibi diğer veri yapıları hakkında öğrenmek, bağlı listeleri anlamaktan doğal bir ilerlemedir. Bu yapılar, bağlı listelerin ilkeleri üzerine inşa edilerek daha geniş bir yelpazedeki hesaplama problemlerini verimli bir şekilde çözmenize yardımcı olur. Örneğin ağaçlar ve ikili arama ağaçları, bağlı listelerin kavramını hiyerarşik bir forma genişleterek her düğümün veri yapısındaki birden fazla öğeye bağlanmasına olanak tanır.

Bu kavramlar size yabancı geliyorsa endişelenmeyin! Datacamp’in Python’da veri yapıları ve algoritmalar üzerine tüm bir kursu var ve bu kavramları daha ayrıntılı şekilde ele alıyor. Önce yığınlar, ağaçlar, hash tabloları, kuyruklar ve grafikler gibi veri yapıları hakkında bilgi edineceksiniz. Kurs ilerledikçe, daha verimli bir programcı ve problem çözücü olmanıza yardımcı olacak arama ve sıralama algoritmalarını anlayacaksınız.

İleri düzey bağlı liste kavramlarını keşfetme

Bu eğitimde tek yönlü bağlı listeleri uyguladık; ekleme, silme ve dolaşma gibi işlemleri ele aldık.

Bu bilgiyi, çift yönlü ve dairesel bağlı listelerin uygulamasını öğrenerek bir adım ileri taşıyabilirsiniz. Skip listeleri, öğelere daha hızlı erişimi kolaylaştırarak arama işlemlerini hızlandıran bağlı listelerin bir başka uzantısıdır.

Bu gelişmiş veri yapıları hakkında bilgi edinmek, teknik becerilerinizi bir üst seviyeye taşıyacak ve programlama yeteneklerinizi önemli ölçüde geliştirecektir; sizi veri bilimi, yazılım geliştirme ve makine öğrenimi mühendisliği gibi alanlardaki daha karmaşık zorluklara hazırlayacaktır.

Bu ileri düzey konulara geçmeden önce daha başlangıç düzeyinde bir programlama tanıtımı isterseniz, Python Programmer kariyer yolumuzu keşfedin. Dilin temellerini öğretecek bir dizi kurs sunar.