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

Bağlı liste, veri düzenleme 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önetimini verimli kılar. Bağlı listedeki her düğüm iki ana bileşen barındırır: veri kısmı ve sıradaki 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 temellerine indirgeme yapacağı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 silmenin kolaylığı

Listelerde, sondan farklı herhangi bir konuma bir öğe eklemek veya bir öğeyi silmek, onu izleyen tüm öğelerin yer değiştirmesini 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 henüz aşina değilseniz, Python listeleri hakkındaki eğitimimizi okuyabilirsiniz.

Bağlı listeler ise farklı şekilde çalışır. Öğeleri bitişik olmayan çeşitli bellek konumlarında saklar ve bunları sonraki düğümlere işaretçilerle birbirine bağlar. Bu yapı, bağlı listelerin herhangi bir konuma öğe eklemesini veya silmesini, bağlantıları yeni öğeyi dahil edecek ya da silineni atlayacak şekilde değiştirerek mümkün kılar.

Ekleme veya silme noktasındaki düğüme doğrudan referansınız olduğunda, işlemin kendisi O(1)’dir. Yine de o konumu bulmak O(n) dolaşım gerektirir; dolayısıyla O(1) avantajı yalnızca ilgili düğüme zaten işaretçiniz varsa (örneğin listenin başında çalışırken) geçerlidir.

Dinamik boyut

Python listeleri dinamik dizilerdir; bu da boyutu değiştirme esnekliği sundukları anlamına gelir.

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. Bu tür bir yeniden ayırma verimsizdir; çünkü öğeler yeni bloğa kopyalanır ve hemen gereksinim duyulandan daha fazla alan tahsis edilebilir.

Buna karşılık, bağlı listeler yeniden ayırma veya yeniden boyutlandırma gerektirmeden 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 başlangıç boyutunu aşacak şekilde büyümesi gerektiğinde, daha büyük yeni 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 israf edilir.

Buna karşılık, bağlı listeler her öğe için belleği ayrı ayrı ayırır. Bu yapı, yeni öğeler eklendikçe bellek tahsis edilebildiğinden 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 sıradan liste ve dizilere göre bazı avantajlar sunsa da, sınırlamaları da vardır. Her öğe için sıradaki düğüme referans veren bir işaretçi 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ı dolaşım gerektirir ve bu da O(n) arama zaman karmaşıklığıyla sonuçlanır.

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

• Sık sık çok sayıda öğe ekleyip silmeniz gerekiyorsa
• Veri boyutu öngörülemezse veya sık değişme olasılığı varsa
• Öğ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üğümde bazı veriler ve dizideki bir sonraki düğüme referans bulunur. Yalnızca tek bir yönde — baştan (ilk düğüm) sona (son düğüm) — dolaşılabilirler.

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

• Veri: Düğümde saklanan asıl bilgi.
• Sonraki İşaretçi: Bir sonraki düğüme referans. Son düğümün sonraki işaretçisi genellikle null olarak ayarlanır.

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

Tek yönlü bağlı bir listenin başına düğüm eklemek ve baştan silmek O(1) zaman karmaşıklığıyla oldukça etkilidir. Ancak ortada veya sonda ekleme ve silme, o noktaya kadar listeyi dolaşmayı gerektirir ve 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şılabilmeleri ve gerektiğinde önceki düğüme geri dönemememizdir. Bu kısıt, çift yönlü gezinim gerektiren işlemleri yapma yeteneğimizi sınırlar.

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

Döngüsel bağlı listeler

Döngüsel bağlı liste

Döngüsel bağlı listeler, son düğümün ilk düğüme işaret ettiği özel bir bağlı liste biçimidir ve dairesel bir yapı oluşturur. Bu, şimdiye kadar gördüğümüz tek ve çift yönlü bağlı listelerin aksine, döngüsel bağlı listenin bitmediği; bunun yerine döndüğü anlamına gelir.

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

Zaman karmaşıklığı özeti

Bağlı listelerin Python listeleriyle karşılaştırmasını hızlıca görmek faydalıdır:

Ana çıkarım: Bağlı listeler başta yapılan ekleme ve silmelerde (O(1)) üstün, diğer her şeyde zayıftır. Veri yapınızın başında sık sık öğe ekleyip çıkarmıyorsanız, sıradan bir Python listesi muhtemelen daha iyi bir seçimdir.

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

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

Bir düğümü başlatma

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

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

    def __repr__(self):
        return f"Node({self.data})"

Yukarıdaki kod, bir düğümü iki temel işlemle başlatır: Düğümün “data” özniteliğine, düğümün içerdiği asıl bilgiyi temsil eden bir değer atanır. “next” özniteliği, sıradaki düğümün adresini temsil eder. Bu, şu anda listedeki başka hiçbir düğüme bağlanmadığını belirtmek için None olarak ayarlanmıştır. Bağlı listeye yeni düğümler eklemeye devam ettikçe bu öznitelik bir sonraki düğümü gösterecek şekilde güncellenecektir.

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

Sırada bağlı liste sınıfını oluşturmak var. 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 düğüm bulunmadığını belirtmiş oluruz. Şimdi yeni düğümler ekleyerek listeyi doldurmaya geçeceğiz.

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

LinkedList sınıfı içinde, yeni bir düğüm oluşturup onu listenin 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 sonraki işaretçisi, listenin mevcut başına ayarlanır; böylece bu düğüm mevcut düğümlerin önüne yerleşir. Son olarak, yeni oluşturulan düğüm listenin başı yapılır.

Şimdi, 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, listenin 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 kelimelerle 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ı şu çıktıyı üretmelidir:

"the quick brown fox"

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

LinkedList sınıfı içinde, liste 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şı olacaktır. Aksi durumda, mevcut son düğümün ardına eklenecektir. Bunun pratikte nasıl çalıştığına bakalım:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Yukarıdaki yöntem, önce 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, listeyi son düğümü bulmak için dolaşır ve bu düğümün işaretçisini 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 bu listenin başını ikinci düğüme işaret edecek şekilde ayarlamayı içerir. Bu şekilde ilk düğüm artık listenin bir 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, listeyi dolaşıp sondan bir önceki düğümü bulmalı ve onun sonraki işaretçisini None yapmalıyız. Bu şekilde, son düğüm artık listenin bir 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 takdirde, liste tek bir düğüm içeriyorsa o düğüm kaldırılır. Birden fazla düğüm içeren listelerde yöntem, sondan bir önceki düğümü bulur ve onun sonraki düğüm referansını None olacak şekilde günceller.

Şimdi, bağlı listenin başından ve sonundan öğeleri silmek için ana fonksiyonu 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üğümde, düğümün verisinin aranan değerle eşleşip eşleşmediğini kontrol ederek 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 ana fonksiyonunuza ekleyin:

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, listede ilk pozisyonda yer aldığı için bağlı liste içinde başarıyla bulunmuştur. “lazy” ise listenin bir parçası olmadığından bulunamamıştır.

Son Düşünceler

Buraya kadar geldiyseniz tebrikler! Bağlı listelerin temel ilkelerini; yapısını, türlerini, öğe ekleme ve kaldırmayı ve nasıl dolaşıldıklarını artık sağlam biçimde anlıyorsunuz.

Ancak yolculuk burada bitmiyor. Bağlı listeler, veri yapıları ve algoritmalar dünyasının sadece başlangıcıdır. Konuya hakimiyetinizi derinleştirmek için bazı olası 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, karma tablo (hash table) inşa etmek ve hatta GPS navigasyon sistemleri ile masa oyunları oluşturmak için kullanılır. Kendi projelerinize başlamak için, Python, R ve SQL ile gerçek dünya sorunlarını nasıl çözeceğinizi öğreten ücretsiz rehberli veri bilimi projelerimize göz atın.

Veri yapıları ve algoritmaları öğrenin

Ağaçlar, yığınlar (stack) ve kuyruklar (queue) gibi diğer veri yapılarını öğrenmek, bağlı listeleri anlamanın doğal bir devamıdır. Bu yapılar, bağlı listelerin ilkelerini temel alır ve daha geniş bir yelpazede hesaplamalı sorunları verimli şekilde çözmenize yardımcı olur. Örneğin ağaçlar ve ikili arama ağaçları, bağlı liste kavramını hiyerarşik bir forma genişleterek her düğümün veri yapısında birden çok elemana 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ı bir şekilde ele alıyor. Önce yığınlar, ağaçlar, karma tablolar, kuyruklar ve grafikler gibi veri yapıları hakkında öğreneceksiniz. Kurs boyunca ilerledikçe arama ve sıralama algoritmalarını anlayacak, bu sayede daha verimli bir programcı ve problem çözücü olacaksınız.

İleri 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 döngüsel bağlı listelerin uygulamasını öğrenerek bir adım öteye taşıyabilirsiniz. Skip listeleri, öğelere daha hızlı erişim sağlayarak arama işlemlerini hızlandıran, bağlı listelerin bir başka uzantısıdır.

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

Bu ileri konulara geçmeden önce daha başlangıç düzeyinde bir programlama girişine ihtiyacınız varsa, Python Programcısı kariyer yolumuzu keşfedin. Dilin temellerini öğreten bir dizi kurs sunar.