C++ kullanarak bir liste içerisinde sondan ikinci düğümü nasıl bulabilirsiniz? Bu makaleden öğrenin ve kendi C++ uygulamanızı oluşturun İpuçları ve adımlar burada!

Bu makalede, bir bağlı listenin sonundan ikinci elemanının nasıl bulunacağı anlatılacaktır. Bağlı liste, her elemanın kendisinden sonraki elemanın bellekteki adresini (pointer) sakladığı bir veri yapısıdır. Bu yapının sonundan ikinci elemanını bulmak için iteratif ve recursive yaklaşımlar kullanılabilir.

Iteratif yaklaşımda bir döngü yardımıyla sırayla elemanlar gezilir ve sondan ikinci eleman bulunana kadar arama devam eder. Recursive yaklaşımda ise sondan ikinci eleman, son elemanın bir önceki düğümü olarak tanımlanır ve her adımda fonksiyon kendi kendini çağırır.

Bu algoritma C++ dilinde bir örnek uygulama ile gösterilecektir. Örnek kodlar, hem iteratif yaklaşım hem de recursive yaklaşım örnekleri içermektedir. Ayrıca, kodların açıklamaları ile birlikte sunulacaktır.

Bağlı Liste Nedir?

Bağlı liste, programlama dillerinde veri yapısı olarak kullanılan önemli bir yapıdır. Bu yapı, her bir elemanın bir sonraki elemanın bellekteki adresini (pointer) sakladığı bir veri yapısıdır. Bu sayede birbirleri arasında bağlantı oluşturularak liste şeklinde elemanlar düzenlenebilir.

Bağlı listenin farklı yapıları mevcuttur. Tek yönlü bağlı liste, çift yönlü bağlı liste gibi yapılar bulunmaktadır. Tek yönlü bağlı liste, her elemanın sadece bir sonraki elemanın bellek adresini tuttuğu bir yapıdır. Çift yönlü bağlı liste ise, her elemanın hem bir sonraki hem de bir önceki elemanın bellek adreslerini tuttuğu bir yapıdır.

Bağlı liste yapısı, işlemlerin hızlı bir şekilde yapılmasını sağlar. Özellikle, listeden eleman silme ve ekleme işlemlerinde avantajlıdır. Ayrıca, diğer veri yapılarına göre daha verimli bir şekilde bellek kullanımı yapar.

Bağlı Listede Sondan İkinci Düğüm Nasıl Bulunur?

Bağlı listede, sondan ikinci düğümü bulmak için birkaç adım izlenir. İlk olarak, listenin boyutu hesaplanır. Bunu yapmak için, listenin tüm elemanlarına tek tek erişilmesi gerekmektedir. Bu işlem için, listenin ilk elemanına erişilerek, sonraki elemanların adreslerine gidilir ve tüm elemanlar gezilerek listenin boyutu belirlenir.

Ardından, son elemanın adresi bulunur. Bunun için, bir döngü ile tüm elemanlara tek tek erişilerek, son elemanın adresi bulunur. Bu işlem sonunda, üzerinde işlem yapılacak bir pointer değerine sahip olunur.

Son olarak, sonundan ikinci elemanın adresi hesaplanır. Bunun için, son elemanın adresindeki pointer değeri kullanılarak, sonundan ikinci elemanın adresi belirlenir. Bu adres kullanılarak, sondan ikinci elemanın değerine erişilebilir.

İteratif Yaklaşım

İteratif yaklaşım, bir döngü kullanarak bağlı listenin sondan ikinci elemanını bulmak için kullanılan bir yöntemdir. İlk olarak, bağlı listenin boyutu hesaplanır ve son elemanın adresi bulunur. Daha sonra, döngü, listenin başlangıcından başlayarak sırayla elemanları gezer. Her adımda, geçerli elemanın adresi bir sonraki elemanın adresine güncellenir ve döngü devam eder. Sondan ikinci eleman bulunana kadar bu işlem tekrar edilir.

Bu yöntem, listenin boyutuna bağlı olarak zaman ve bellek açısından maliyetli olabilir. Ancak, bağlı listenin sonundan ikinci elemanını bulmanın neredeyse kesin bir yoludur.

Örnek Kod

Aşağıdaki C++ kod örneği, bağlı listenin sonundan ikinci elemanı bulmak için iteratif bir yaklaşım kullanmaktadır.

#include <iostream>using namespace std;struct Node {    int data;    Node* next;};void printNthFromLast(Node *head, int n){    Node *main_ptr = head;    Node *ref_ptr = head;    int count = 0;    if (head != NULL) {        while (count < n) {            if (ref_ptr == NULL) {                cout << n << " greater than total"                        " no of nodes";                return;            }            ref_ptr = ref_ptr->next;            count++;        }        while (ref_ptr != NULL) {            main_ptr = main_ptr->next;            ref_ptr = ref_ptr->next;        }        cout<data;    }}int main(){    Node* head = NULL;    Node* second = NULL;    Node* third = NULL;    Node* fourth = NULL;    Node* fifth = NULL;    head = new Node();    second = new Node();    third = new Node();    fourth = new Node();    fifth = new Node();    head->data = 11;    head->next = second;    second->data = 22;    second->next = third;    third->data = 33;    third->next = fourth;    fourth->data = 44;    fourth->next = fifth;    fifth->data = 55;    fifth->next = NULL;    printNthFromLast(head, 2);    return 0;}

Bu kod örneğinde, 'printNthFromLast' fonksiyonu, başlangıç düğümü 'head' ve sonundan kaçıncı elemanın bulunacağı 'n' parametreleriyle çağrılır. Döngü içinde 'ref_ptr' n kadar ilerletilir ve 'main_ptr' geri kalan kısım boyunca ilerler. Sonunda, 'main_ptr'nin gösterdiği elemanın değeri ekrana yazdırılır.

Kod Açıklaması

Bu örnek kodda, öncelikle bir bağlı liste tanımlanır ve son elemana kadar döngü devam eder. Her adımda, mevcut düğümün bellekteki adresi, bir sonraki düğümün bellekteki adresiyle güncellenir. Son elemana ulaşıldığında, sonundan ikinci elemanın bellekteki adresi elde edilir ve bu düğümün değeri ekrana yazdırılır.

Aşağıdaki tabloda, örnek kodda kullanılan değişkenler ve işlemler açıklanmaktadır:

Recursive Yaklaşım

Recursive yaklaşım, sondan ikinci elemanın son elemanın bir önceki düğümü olarak tanımlandığı bir yöntemdir. Bu yöntemde, fonksiyon her adımda kendi kendini çağırarak ilerler ve her seferinde son elemanın bir önceki elemanı kontrol eder. Yani, son elemanın adresi üzerinden, her adımda bir önceki elemanın adresi elde edilir.

Recursive yaklaşımın bir avantajı, kodun daha kısa ve düzenli olmasıdır. Ayrıca, özyinelemeli bir işlev kullanarak bunun yerine bir döngü kullanmaktan daha az bilgi saklar. Ancak, bu yöntem her zaman en hızlı yöntem olmayabilir, çünkü her adımda fonksiyon bir kez daha çağrılır ve bellekte daha fazla yer kaplar.

Aşağıdaki örnek kodda, bağlı liste üzerinde recursive bir yaklaşım kullanarak sondan ikinci düğümü bulmaktadır:

node* recursiveSecondLast(node* head){    if (head == NULL || head->next == NULL)        return NULL;    if (head->next->next == NULL)        return head;    node* second_last = recursiveSecondLast(head->next);    return second_last;}

Bu kodda, özyinelemeli bir işlev kullanılarak bağlı listenin son elemanı bulunur. Daha sonra, fonksiyon, bağlı listenin son elemanının bir önceki düğümünü döndürür ve bu sayede sondan ikinci düğüm elde edilir.

Örnek Kod

Bağlı liste üzerinde recursive bir yaklaşım kullanarak sondan ikinci düğümü bulmak için C++ programlama dilinde şu kod örneği kullanılabilir:

Bu örnekte, 5 elemanlı bir bağlı liste tanımlanmıştır. Recursive fonksiyon ise şu şekildedir:

int recursive_second_last(node* head) {    if (head == NULL || head->next == NULL) {        return -1;    }    if (head->next->next == NULL) {        return head->data;    }    return recursive_second_last(head->next);}

Bu kod, başlangıçta listenin ilk düğümünün adresini alır ve eğer liste boşsa veya sadece bir elemana sahipse -1 değerini döndürür. Eğer listede en az iki eleman varsa, head->next->next NULL olana kadar recursive şekilde çağrılır ve listenin sondan ikinci elemanının değeri geriye döndürülür.

Kod Açıklaması

Bu örnek kodda, öncelikle bağlı listenin oluşturulması ve son elemana kadar recursive olarak ilerlenmesi sağlanır. Recursive fonksiyon her özyinelemeli çağrıda sonraki elemana hareket ederek ilerler ve listenin sonuna ulaştığında, fonksiyon son elemanın bir önceki elemanını geriye döndürür. Bu eleman listenin sondan ikinci elemanıdır.

Kodun daha açıklayıcı olması için, bir adım adım gösterim yapılabilir:

Görüldüğü gibi, son elemana kadar recursive bir şekilde ilerlemek, sondan ikinci elemanın değerini bulmak için oldukça etkili bir yoldur. Bu yöntem, özellikle büyük boyutlu bağlı listeler üzerinde arama yaparken daha hızlı sonuçlar verir.