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 verimli bellek yönetimi sağlar. Bağlı listedeki her düğüm iki ana bileşen içerir: 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 temellerine ayıracağız.

Neden Bağlı Listeler?

Bağlı listeler, aşağıda özetlendiği gibi, verilerin normal listeler ve dizilerde saklanmasıyla ilgili çeşitli sakıncaları gidermek için oluşturulmuştur:

Ekleme ve silme kolaylığı

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

Bağlı listeler ise farklı şekilde çalışır. Öğeleri farklı, bitişik olmayan bellek konumlarında saklar ve bunları sonraki düğümlere işaretçilerle birbirine bağlar. Bu yapı, bağlantıları değiştirerek yeni bir öğeyi dahil etmek veya silineni atlamak suretiyle, bağlı listelere herhangi bir konumda öğe ekleme veya kaldırma imkânı tanır.

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

Dinamik boyut

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

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

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 bitişik bir blokta bellek ayırır. Bir listenin başlangıç boyutunun ötesinde büyümesi gerektiğinde, bitişik daha büyük yeni bir bellek bloğu ayırmalı ve ardından 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 olduğundan büyük tahmin edilirse, kullanılmayan bellek israf olur.

Buna karşılık, bağlı listeler her öğe için ayrı ayrı bellek ayırır. Bu yapı, yeni öğeler eklendikçe bellek 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 listelere ve dizilere göre bazı faydalar sağlasa da, sınırlamaları da vardır. Her öğe için bir sonraki düğüme referans verecek işaretçilerin saklanması gerektiğinden, bağlı listelerde öğe başına bellek kullanımı daha yüksektir. Ayrıca, bu veri yapısı doğrudan veri erişimine izin vermez. Bir öğeye erişmek, listenin başından itibaren sıralı olarak dolaşım gerektirir ve bu da O(n) arama zaman karmaşıklığıyla sonuçlanır.

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

• Çok sayıda öğeyi sık sık eklemeniz ve silmeniz gerekiyorsa
• Veri boyutu öngörülemezse veya sık sık değişmesi muhtemelse
• Öğelere doğrudan erişim bir gereklilik değilse
• Veri kümesi büyük öğeler veya yapılardan oluşuyorsa

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ü (singly) bağlı listeler

Tek yönlü bağlı liste

Tek yönlü bağlı liste, her düğümün bazı veriler ve dizideki bir sonraki düğüme bir referans içerdiği en basit bağlı liste türüdür. 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 parçadan oluşur:

• Veri: Düğümde saklanan gerçek 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ında yalnızca tek yönde dolaşılabildiğinden, belirli bir öğeye değere veya indekse göre erişmek, baştan başlayıp istenen düğüm bulunana kadar düğümler arasında 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ı bir listenin başına bir düğüm eklemek ve silmek O(1) zaman karmaşıklığıyla son derece verimlidir. 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ı hâline getirir.

Çift yönlü (doubly) bağlı listeler

Çift yönlü bağlı liste

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

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

Dairesel bağlı listeler

Dairesel bağlı liste

Dairesel bağlı listeler, son düğümün ilk düğüme 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ı listelerden farklı olarak 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 ilkine geri dönülen kutu oyunları gibi sürekli olarak döngü halinde ilerlenmesi gereken 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ı bir bakışta görmek faydalıdır:

Ana çıkarım: Bağlı listeler başta yapılan ekleme ve silmelerde (O(1)) öne çıkar, ancak diğer her şeyde geride kalır. Veri yapınızın başında öğe ekleyip çıkarmayı sık yapmıyorsanız, normal 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 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 başınıza çalıştırırken sorunlarla karşılaşırsanız bu harika bir seçenektir!

Bir düğüm başlatma

Önceden öğrendiğimiz gibi, bir düğüm, verileri 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
        self.next = None

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

Yukarıdaki kod, iki temel işlem gerçekleştirerek bir düğümü başlatır: Düğümün “data” özniteliğine, düğümün içermesi amaçlanan gerçek bilgiyi temsil eden bir değer atanır. “next” özniteliği, bir sonraki düğümün adresini temsil eder. Bu şu anda None olarak ayarlanmıştır; bu da listede başka hiçbir düğüme bağlanmadığı anlamına gelir. 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ş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 hiç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ının 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 verilerle yeni bir düğüm oluşturulur. Bu yeni düğümün sonraki işaretçisi, listenin mevcut başına ayarlanır; bu da bu 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 şimdi bu bağlı listeyi bir dizi kelimeyle dolduracağız. Bunu gerçekleştirmek için, 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 kelime dizisiyle doldurmaya devam edelim: “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ında, 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 takdirde, listenin mevcut son düğümüne 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 ve 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 dahil edip, listemizin sonuna bir kelime eklemek için kullanalım. Bunu gerçekleştirmek 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, “jumps” kelimesini listenin sonuna 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ı bir listenin ilk düğümünü silmek kolaydır; çünkü yalnızca listenin başını ikinci düğüme işaret edecek şekilde ayarlamayı gerektirir. Bu şekilde ilk düğüm artık listenin parçası olmaz. Bunu gerçekleştirmek için, aşağıdaki yöntemi LinkedList sınıfına 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ı bir listenin son düğümünü silmek için, ikinci son düğümü bulmak üzere listeyi dolaşmalı ve onun sonraki işaretçisini None yapmalıyız. Bu şekilde son düğüm artık listenin parçası olmaz. Bunu gerçekleştirmek 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, listede tek bir düğüm varsa o düğüm kaldırılır. Birden fazla düğümlü listelerde ise yöntem, sondan bir önceki düğümü bulur ve onun bir sonraki düğüm referansını None olacak şekilde günceller.

Şimdi ana fonksiyonu, bağlı listenin başından ve sonundan öğeler 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 listeyi silmeden önce ve sonra 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

Belirli bir değeri bağlı listede arama

Bu bölümde öğreneceğimiz son işlem, bağlı listede belirli bir değeri bulmaktır. Bunu gerçekleştirmek için yöntem, listenin başından başlamalı ve her bir düğümü dolaşarak düğümün verilerinin arama değeriyle eşleşip eşleşmediğini kontrol etmelidir. 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 konumda yer aldığı için bağlı liste içinde başarıyla bulunmuştur. Ancak “lazy” kelimesi listenin parçası değildir; bu yüzden bulunamamıştır.

Son Düşünceler

Buraya kadar geldiyseniz tebrikler! Bağlı listelerin temel ilkeleri, yapıları, türleri, nasıl öğe eklenip çıkarıldığı ve nasıl dolaşıldığı dâhil olmak üzere sağlam bir anlayış kazandınız.

Ancak yolculuk burada bitmiyor. Bağlı listeler, veri yapıları ve algoritmalar dünyasının sadece başlangıcıdır. Konuya dair bilginizi 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 tablolar (hash table) oluşturmak ve hatta GPS navigasyon sistemleri ile kutu oyunları yapmak 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ı öğrenin

Ağaçlar, yığınlar (stack) ve kuyruklar (queue) gibi diğer veri yapılarını öğrenmek, bağlı listeleri anlamaktan doğal bir ilerlemedir. Bu yapılar, bağlı listelerin ilkeleri üzerine inşa edilerek daha geniş bir yelpazede hesaplamalı sorunları verimli şekilde çözmenize yardımcı olur. Örneğin ağaçlar ve ikili arama ağaçları, her düğümün veri yapısındaki birden çok öğeye bağlanabildiği hiyerarşik bir forma bağlı liste kavramını genişletir.

Bu kavramlar size yabancı geliyorsa endişelenmeyin! Datacamp’in Python’da veri yapıları ve algoritmalar üzerine tamamı bu konuları daha ayrıntılı şekilde ele alan bir kursu var. Önce yığınlar, ağaçlar, karma tablolar, kuyruklar ve grafikler gibi veri yapıları hakkında bilgi edineceksiniz. Kurs boyunca 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 bağlı liste kavramlarını keşfetme

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

Bu bilgiyi, çift yönlü ve dairesel bağlı listelerin uygulanışını öğrenerek bir adım öteye taşıyabilirsiniz. Skip listeler, öğelere daha hızlı erişim sağlayarak daha hızlı arama işlemlerine imkân tanıyan 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ştirecek; veri bilimi, yazılım geliştirme ve makine öğrenimi mühendisliği gibi alanlardaki daha karmaşık zorluklara hazırlanmanızı sağlayacaktır.

Bu ileri düzey konulara geçmeden önce programlamaya daha yeni başlayanlar için uygun bir giriş isterseniz, Python Programlama beceri yolumuzu keşfedin. Dilin temellerini öğretecek bir dizi ders sunar.