Bağlantılı Listeler

Bağlantılı listeler, Bilgisayar Biliminde yaygın kullanılan bir veri yapısıdır. Bağlantılı bir listeyi kullanarak bir müzik çalma listesini gösterebilir veya eylem geçmişini takip edebilirsin.

Genel Bakış

Bağlantılı liste, her bir öğenin listedeki bir sonraki öğeye ait referansı depoladığı doğrusal bir veri yapısıdır. Bağlantılı listede yer alan her öğeye düğüm adı verilir. Düğüm, bazı verilerin yanı sıra bir sonraki düğüme ait referans barındıran bir kapsayıcıdır.

Farklı düğümler bir dizi halinde birbirine bağlandığında bir bağlantılı liste oluşur. Listedeki birinci düğüme baş düğümü, son düğüme ise kuyruk düğümü adı verilir. Listede gezinmek için Baş kısmından başlanır ve her bir düğümdeki referansı kullanarak bir sonraki öğeye gidilir.

Ne zaman kullanılır?

Bağlantılı listeler; yığınlar veya kuyruklar gibi diğer veri yapılarını uygulamak için iyi bir başlangıç noktasıdır. Bağlantılı listeler, sıralı erişim için verileri depolamanın kolay bir yoludur ve yeni öğelerin hızlıca eklenmesini desteklerler. Dizilerin aksine bağlantılı listeler bellekte bitişik (birbirinin yanında) durmaz. Bu, bir düğümün bellekte herhangi bir yerde olabileceği anlamına gelir. Bir sonraki düğümün referansı, konumu belirtir. Bağlantılı listeye düğüm eklemek veya listeden düğüm silmek için tüm yapman gereken, bir sonraki düğümün referanslarını değiştirmektir.

Ne zaman kullanılmaz?

Programın öğelere rastgele erişim gerektiriyorsa (bir listeden rastgele bir oyuncu seçmek gibi), bağlantılı listelerde bu fonksiyon bulunmaz. Listenin ortasındaki belirli bir düğüme erişmen gerekiyorsa bağlantılı listeler dizilerden daha az verimlidir çünkü baş düğümünden başlayarak ihtiyaç duyduğun belirli bir düğüme kadar gitmen gerekir.

Verse’te Uygulama

Verse API’ı, bağlantılı listelerin yerleşik bir uygulamasına sahip değildir ancak kendi başına bir tane oluşturabilirsin.

Bağlantılı listeler, düğümlerden oluşur ve onları göstermek için bir sınıf tanımlaman gerekir. Genel bir düğüm türünün örneği aşağıdaki gibidir:

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

Burada Next seçenek değişkeni, listede bir sonraki düğümün list_node türünde referansını depolar. Next, bir option değişkeni olmalıdır çünkü bir düğüm her zaman bir sonraki düğüme işaret etmeyebilir (bağlantılı bir listenin kuyruk düğümü gibi). Listenin bağlantısını dinamik bir şekilde değiştirmek istersen Next değişkeninin var olması gerekir. Düğüm de Data içinde depolanan bir değer içerir. Bu, bir genel düğüm türü olduğundan Data değişkeni any türündedir ve düğüm herhangi bir veri türünü içerebilir. Bu genel bir tür, bir kapsayıcı, hatta başka bir bağlantılı liste olabilir!

Node1 := list_node{ Next := false, Data := 1 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

<unique> belirleyicisi list_node sınıfının karşılaştırılabilir olmasını sağlar. Böylece düğümünün bir listede baş veya kuyruk düğüm olduğunu kontrol etmek gibi işlemlerle bir düğümün başka bir düğüme eşit olup olmadığını kontrol edebilirsin.

Yalnızca sayıları veya dizeleri işleyen bir düğüm gibi daha spesifik bir uygulama gerekirse Data türünü uygun şekilde değiştirdiğinden emin ol. Data değişkeni, comparable türündeyse Data içindeki değeri başka bir değerle karşılaştırarak belirli bir düğümü bulabilirsin.

# A container node that contains integer data and a reference
# to the next node in the list.
list_node_int := class(list_node):
    # Reference to the next node in the list.
    var Next<override>:?list_node = false
    Data<override>:int

# A container node that contains string data and a reference
# to the next node in the list.
list_node_string := class(list_node):

Tek Bağlantılı Listeler

En temel bağlantılı liste türü, her düğümün bir sonraki düğümün referansını (tek bağlantı) içerdiği tek bağlantılı listedir. Düğümlerini bir listeye dönüştürmek için her bir düğümdeki Next referanslarını kullanarak düğümleri birbirine bağla.

# Link each Node to the next Node in the list
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

Düğümlerin bağlantılı olsa da bağlantılı listelerini bir sınıfta tanımlaman gerekir. Bunu yapmak, her defasında birinci düğüme referans vermek yerine listeni kullanarak fonksiyonları gerçekleştirmeyi kolaylaştırır.

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

Temel bir linked_list sınıfı yalnızca baş düğümün referansını içerir. linked_list sınıfının bir örneğini oluşturmak için düğümlerini birbirine bağla ardından baş düğümü kullanarak listenin bir örneğini oluştur.

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

Listede dolaşmak için baş düğümden başla ve listede ilerleyerek kuyrukta dur. Bunu bir harici fonksiyonda veya linked_list sınıfının içindeki bir sınıf fonksiyonunda yapabilirsin. Baştan kuyruğa tüm listeyi dolaşan örnek bir fonksiyonu aşağıda görebilirsin:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node
        Print("Starting at the Head Node...")
        # If the current node has a next node, set the current node to
        # the next node in the list

Burada TraverseList() fonksiyonu, CurrentNode değerinin bir Next referansı içerip içermediğini kontrol eder ve NextNode içinde depolar. Referans içeriyorsa kuyruk düğüme ulaşana kadar CurrentNode değerini tekrarlayarak NextNode değerine ayarlar. Kuyruk düğüm bir Next referansına sahip olmadığından döngü burada durur.

Çift Bağlantılı Listeler

Tek bağlantılı listelerin aksine çift bağlantılı liste aynı zamanda kendisinden önce gelen önceki adlı düğüme referans içerir.

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

Tek bağlantılı düğümlerde olduğu gibi yalnızca belirli veri türlerini işleyen daha spesifik bir uygulama gerekirse Data türünü uygun şekilde değiştirdiğinden emin ol.

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

Bu durum, çift bağlantılı bir listedeki düğümlerde hem ileriye hem de geriye doğru dolaşabileceğin anlamına gelir. Bu işlem, bir harici fonksiyonda veya bir sınıf fonksiyonunda yapılabilir. Baştan kuyruğa ve kuyruktan başa doğru tüm listeyi dolaşan örnek bir fonksiyonu aşağıda görebilirsin:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses doubly linked nodes which contain references to both the next and previous nodes.
doubly_linked_list := class():
    var Head:doubly_linked_node

    # Traverse a LinkedList, but both backward and forward!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")

Dairesel Bağlantılı Listeler

Dairesel bağlantılı listede yer alan baş düğüm, kuyruk düğümle bağlantılıdır. Bu durum, kuyruk düğümden sonra tüm listeyi dolaşabileceğin ve tekrar baş düğüme ulaşabileceğin anlamına gelir. Dairesel bağlantılı listeler tek veya çift bağlantılı olabilir. Tek şart, baş düğümün kuyruğa veya kuyruk düğümün başa bağlanmasıdır.

Yineleyiciler

Yineleyici, bir kapsayıcı üzerinde yineleme yapmana ve yol boyunca işlemleri gerçekleştirmene olanak tanır. Bunu yolcularla dolu bir tren vagonu gibi düşünebilirsin. Tren bir yol boyunca ilerler ve yol üzerindeki her istasyonda durur. Her istasyonda tren, yolcuları bindirme veya indirme gibi bir görevi yerine getirir. Bağlantılı listelerde her istasyon, listedeki bir düğümdür. Tren (yineleyici) listede dolaşarak her bir düğüme uğrar ve uğradığı yerlerde işlemler gerçekleştirir.

Yineleyiciler, bağlantılı listeler için kullanışlıdır çünkü sadece baş veya kuyruk düğüm yerine belirli noktalarda işlemler gerçekleştirmene olanak tanır.

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

Burada yineleyici, üzerinde yineleme yaptığı listenin referansını ve yineleyicinin o anda durduğu CurrentNode düğümünü içerir. Next() fonksiyonu, CurrentNode düğümünden sonra bir düğüm olup olmadığını kontrol eder ve sonra o düğüme atlar. Buradaki Next() fonksiyonunun <transacts> ve <decides> belirleyicilerini içerdiğini unutma. Fonksiyon, <transacts> olmalıdır çünkü CurrentNode var değerini günceller. Ayrıca Next() fonksiyonunu başarısız olabilir hale getirerek bir sonraki düğümü yineleyip yinelemediğini bilmeni sağladığından, <decides> belirleyicisini dahil etmen gerekir.

Bir yineleyicinin, listenin baş düğümünden başlaması gerekiyormuş gibi görünse de aslında baştan önce başlar. Bunun nedeni, yineleyicinin baş düğümde başın önüne düğüm ekleme veya başı tamamen silme gibi işlemleri gerçekleştirebilmesine imkan vermektir.

Baş düğümden önce yineleyiciyi başlatmak için CurrentNode değerini bir geçici düğümde, listenin başı bir sonraki düğüm olacak şekilde başlatabilirsin. Verse’te CurrentNode değerini başlatırken List fonksiyonuna erişemezsin çünkü sınıf üyeleri değişkenine aynı kapsamdan erişilemez. Yalnızca bir fonksiyonun içindeki farklı kapsamlardan erişilebilir.

linked_list_iterator := class:
    List:linked_list
    # The below line will fail because you can't access List from this scope
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

Bir yineleyici örneği oluşturmak için bunun yerine bir oluşturucu fonksiyonu kullanabilirsin. Oluşturucu, ilişkili olduğu sınıfın bir örneğini oluşturan bileşik bir türdür. Oluşturucu, bir objenin başlangıç değerlerini ayarlar ve Liste değerine erişerek baş düğümüne CurrentNode atamana olanak tanır.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

Çift bağlantılı bir listenin yineleyicisini başlatmak son derece benzerdir, tek fark çift bağlantılı liste düğümleri kullanarak başlatılmasıdır.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

Düğümler Arasında Yineleme

Yineleyiciyi listenin bağlantı şekline göre ileriye veya geriye doğru taşıyabilirsin. Tek bağlantılı bir listedeki yineleyiciler yalnızca ileriye doğru hareket edebilirken çift bağlantılı bir listedeki yineleyiciler her iki yöne hareket edebilir. Bu işlevsellik, Next() ve Previous() olmak üzere iki fonksiyonla tanımlanır. Tek bağlantılı listelerde Previous() fonksiyonu bulunmadığını unutma. Dairesel bağlantılı listeler, tek veya çift bağlantılı olmasına bağlı olarak iki fonksiyondan birine sahip olabilir.

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

Düğüm Ekleme

Yineleyicileri kullanarak bağlantılı listedeki belirli yerlere düğümler ekleyebilirsin. Bir düğüm eklerken düğümün nereye ekleneceğini seçmek önemlidir. Düğümü geçerli düğümün önüne veya sonrasına ekleyebilirsin ancak bu da listenin yapısına bağlıdır. Tek bağlantılı bir listede düğümleri yalnızca diğer düğümlerin sonrasına ekleyebilirsin çünkü referans alacağın bir Previous düğümü yoktur. Çift bağlantılı bir listede düğümleri diğer düğümlerin öncesine veya sonrasına ekleyebilirsin.

# Adds a new node after CurrentNode.
AddNextNode(NewNode:list_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

Burada AddNode fonksiyonu, CurrentNode ile sonrasındaki düğümün arasında bir düğüm ekler. Bunu şekilde yapar:

• CurrentNode düğümünün Next referansını NewNode olarak ayarlar.

• NewNode düğümünün Next referansını NextNode olarak ayarlar. Bir NextNode yoksa (örn. listenin kuyruğundayken), fonksiyon NewNode düğümünü yalnızca bir sonraki düğüm olarak ayarlar.

Çift bağlantılı bir listede CurrentNode düğümünün öncesine veya sonrasına düğüm ekleme seçeneğin vardır. Bu işlevselliği AddNodeAfter() ve AddNodeBefore() olmak üzere iki fonksiyona ayırabilirsin. Bunların uygulanması tek bağlantılı listedekiyle son derece benzerdir ancak bu kez her bir düğüm için Previous referansını da ayarlamayı unutmamalısın.

# Adds a new node after CurrentNode.
AddNodeAfter(NewNode:doubly_linked_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set NewNode.Previous = option{CurrentNode}
        set CurrentNode.Next = option{NewNode}
        set NextNode.Previous = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}

Düğümleri Kaldırma

Düğümleri kaldırmak için listenin sırasını korurken ilgili düğümün tüm referanslarını silmen gerekir. Bunu yapmak için, kaldırmak istediğin düğümden sonra herhangi bir düğüm varsa, kaldırılan düğümden önceki tüm düğümleri ondan sonra gelen düğümlere bağlaman gerekir. Tek bağlantılı bir listede Previous referansın olmadığı için yalnızca CurrentNode düğümünden sonraki düğümleri kaldırabilirsin.

# Remove the next node after CurrentNode. If the next node
# has a Next reference, set that node to the next node of CurrentNode.
RemoveNextNode():void=
    if(RemovedNode := CurrentNode.Next?):
        if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
            set CurrentNode.Next = option{NodeAfter}
            Print("Removed the node between CurrentNode and the node after it")
            # If the removed node is the Head node, set the next node as the new Head.
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")

Baş düğümünü kaldırırken özel bir durumun olmalıdır. Bu durumda baş düğümden sonraki düğümü yeni baş düğüm olarak ayarlaman gerekir. Aksi takdirde bağlantılı listenin bir başlangıç noktası olmaz.

Çift bağlantılı bir listede düğüm eklerken olduğu gibi düğümleri kaldırırken de işlemi, geçerli düğümden önceki veya sonraki düğümleri kaldırma şeklinde bölebilirsin.

# Remove the node after CurrentNode
RemoveNodeAfter():void=
    if(RemovedNode := CurrentNode.Next?):
        if:
            NodeAfter := RemovedNode.Next?
            set RemovedNode.Next = false
            set RemovedNode.Previous = false
            set NodeAfter.Previous = option{CurrentNode}
            set CurrentNode.Next = option{NodeAfter}
        then:

Tam Kod

Bu örnekteki sınıfların her biri için tam kod aşağıdaki gibidir.

list_node

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    # Reference to the next node in the list.
    var Next:?list_node = false
    Data:any = {}


# A container node that contains integer data and a reference
# to the next node in the list.

linked_list

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.
linked_list := class:
    # The first node in the list.
    var Head:list_node
 
    # Traverses the linked list forward starting from the CurrentNode.
    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node.

linked_list_iterator

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node.
    Next()<transacts><decides>:list_node=
        NextNode := CurrentNode.Next?
        set CurrentNode = NextNode

Kendi Kendine Yapabileceklerin

Bağlantılı listeleri geliştirmenin çok sayıda yolu vardır ve işlevsellik eklemenin farklı yollarını araştırmalısın. Bağlantılı listelerini geliştirmek için kullanabileceğin yöntemlerden bazıları şunlardır:

• Her Liste aynı zamanda kuyruk düğümün bir referansını depolasaydı ne olurdu?

• Düğümlerinin içeriklerini yazdırmak için bir ToString() yöntemi uygulayabilir misin?

• Bir listeyi tersine çevirmek nasıl olurdu? Bir Length() fonksiyonu uygulayabilir misin?

• Yeni işlemler gerçekleştirmek için yineleyiciye daha fazla yöntem ekleyebilir misin?