Çift Bağlantılı Listeler ve Bunların Python 3'te Uygulanması

Bağlantılı listeler veri depolamanın doğrusal bir yoludur. Veri içeren düğümlerin yanı sıra bir sonraki verilere nasıl ulaşılacağına dair işaretçilerden oluşur. Düğümleri bir zincirin üyesi olarak düşünün. Her zincir, güçlü bir bağ kurmak için birbirine bağlıdır. Örneğin, ortadaki bağlantı başarısız olduktan sonra her şeyi kaçırıyorsa. Artık tam bir zincir değil! Bu bağlantılı listelere nasıl çevrilir? İşaretçilerden biri eksik veya yanlışsa, verilerin geri kalanı artık okunamaz.

Geçerli bir zincir değil! Bu bağlantılı bir listeyi kıracak!

Bununla birlikte, bu makalenin konusu, bağlantılı listelerin çok yönlü bir versiyonundadır - iki kat bağlantılı liste. Düzenli (veya tek tek) bağlantılı bir listeyle karşılaştırıldığında, iki kat bağlantılı bir liste daha önce adı verilen başka bir işaretçiyi içerir. Tahmin edebileceğiniz gibi, bu düğümün önceki düğümün nerede olduğunu bilmesini sağlar. Buna karşılık, tek bir bağlı liste, aynı noktaya ulaşmak için listenin tamamını bir önceki noktaya kadar ilerletmek zorunda kalacaktır.

Tek tek bağlantılı listeler hakkında bilgi için lütfen sınıf arkadaşımın makalesini ziyaret edin:

Daha önce belirtildiği gibi, düğümler bellekteki diğer konumlara işaret eder. Bu ne anlama geliyor? Peki, bitişik konumlarda depolanan dizilerin aksine, bağlantılı listelerde yalnızca işaretçiler bulunur. Aşağıdaki şemada her bellek bloğunun (kırmızı) kendisine işaret eden iki ucu vardır. Sonraki işaretçiye (siyah) bakarak bu bilgilere erişir. Ondan önceki bloğu bulmak istiyorsa, Önceki işaretçiye (beyaz) bakacaktır.

Öyleyse, nasıl iki kat bağlantılı bir liste uygulanmaktadır? Ereİşte Python 3’te nasıl

Düğüm sınıfınıza bir .prev ekleyin. Artık uygulamaya başlamaya hazırsınız!

Avantajları - Python 3 kodu ile!

İki bağlantılı bir listenin, tek bağlantılı bir listeye göre avantajları nelerdir? İki kat bağlantılı bir listeyle, düğümleriniz arasında ileri ve geri gidebilirsiniz. Bu, ekleme işlemini gerçekten çok kolaylaştırır. İki kat bağlantılı listelerde, yalnızca bağlı listenizi istediğiniz düğüme geçirir ve ardından önceki düğümü çağırırsınız.

Dezavantajları

Bağlantılı listeler hakkında harika şeyler olsa da, her şey yolunda bir çözüm değil. Birçok veri yapısında ve algoritmada olduğu gibi bu, cephaneliğinizde bir araç olmalı. Tek bağlantılı bir listedeki dezavantajlardan biri, iki bağlantılı bir listedeki her bağlantının önceki işaretçiyi izlemesi gerektiği için daha fazla bellek tüketimi olduğudur. Ek olarak, söz konusu işaretçiyi takip etmek zor.

Aslında hala uygulamalarını uygulama sürecinde yaşıyorum. Bu, bu makalenin yazılmasından bu yana benim ikinci başarılı uygulamam olacak (Nisan 2019). Her seferinde biraz daha kolaylaşıyor ama yine de önceki işaretçinin diğer tüm işlevlerimle nasıl etkileşimde bulunduğunu gösteren diyagramlar çizmem gerekiyor.

Ama bu ne için kullanılacak?

Sorduğunu duydum. Bir önceki ve bir sonraki gördüğünüz zaman düşünün. Uygulanabilecek bazı açık ve ince yollar var.

Kaynak: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

Peki ya müzik çalar gibi bir durumda? Bir sonraki ve bir önceki düğmede çok açık bir özelliği var. Bu iki şarkı arasında geçiş yapmak için iki kat bağlantılı bir liste kullanılabilir.

Ya da bir tarayıcı? Bunların ayrıca ziyaret ettiğiniz web sayfaları arasında ileri ve geri gitmenin açık yolları vardır.

Şimdi kelime işlem yazılımınızı veya tercih ettiğiniz fotoğraf editörünü düşünün. Hata yaptığınız zaman, bu son işlemi geri almak için CTRL (Mac için CMD) + Z tuşlarına basabilirsiniz. Aynı şekilde, CTRL (Mac için CMD) + Y ile yaptığınız işlemi de yeniden yapabilirsiniz. Şimdi bu ses neden tanıdık geliyor? Ayrıca iki kat bağlantılı bir listeyle uygulanabilir! Önceki işaretçi, çok fazla geri alırsanız eylemleri yinelemek için yapılırken yapılan eylemlere işaret eder.

Kaynak: https://gfycat.com/brilliantbeautifuldassieKaynak: https://www.solitairecardgames.com/how-to-play-solitaire

Düşündüğüm daha az belirgin bir uygulama Solitaire oyundaydı. Tarafım, amacımı açıklamaya yardımcı olan Solitaire terminolojilerinin bir görüntüsüdür.

Oyun, önceki ya da sonraki kartları tabloda ya da atık yığınında görmek için sürekli olarak görmeniz gereken parlak bir örnektir. Atık yığınından tabloya kadar bir kart oynadığınızda, atık yığın önceki kartla birlikte güncellenir.

İki kat bağlantılı listelerdeki kullanımların daha canlı bir tartışması için stackoverflow hakkındaki bu tartışmaya bir göz atmanızı tavsiye ederim:

Öyleyse, bir sonraki bağlantılı listeyi uyguladığınızda neden iki kat bağlantılı bir liste denemiyorsunuz? Bağlantılı bir listenin tepesinde fazla kod yok ve çok büyük avantajlar var!

Ek kaynaklar

Python 3'ün iki kat bağlantılı bir listedeki uygulamasının tam bağlantısı Github depomda bulunabilir.

İkili bağlantılı listelerden oluşan bir 3B yazdırılabilir zinciri istiyorsanız, onu Thingiverse'ye yükledim.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ