Günlük Kodlama Sorunu: K'inci Dizini Tek Geçişte Bağlantılı Listeden Kaldırma

K-th Dizinini Bağlantılı Listeden Tek Geçişte Kaldırma

Çözülmesi gereken başka bir sorunla tekrar hoş geldiniz! Bugün bağlantılı listeler ve bunların elemanlarının kaldırılmasıyla ilgileniyoruz. Bağlantılı listelerin ne olduğu hakkında biraz tartışacağız, bir tane oluşturacağız ve ondan öğeleri nasıl kaldıracağımızı göreceğiz.

Başlamadan önce olağan sorumluluk reddi beyanları:

• Bu sorunlar, abone olabileceğiniz harika Günlük Kodlama Sorunu haber bülteni tarafından sağlanmaktadır. Burada . Şuna bir göz atın ve karşılaştığınız zorlukları da çözmeye çalışın!

• Ben uzman bir programcı değilim: Sadece çekimlerini paylaşmayı seven bir adam! Bir algoritma için daha iyi veya daha hızlı bir çözümünüz varsa, lütfen bunu yorumlarda gönderin! Bu konuda biraz daha fazlasını öğrenmeyi çok isterim!

  
  

Yeterince uzatma; hadi soruna geçelim!

Bağlantılı bir liste ve k tam sayısı verildiğinde, listenin sonundaki k'inci düğümü kaldırın ve listenin başına dönün.

k listenin uzunluğundan daha küçük olması garanti edilir.

Bunu tek geçişte yapın.

Tamam o zaman, burada neler olduğunu biraz açıklayalım: bize bağlantılı bir liste ve listeden çıkarmamız için bir k indeks elemanı veriliyor. Bundan sonra bağlantılı listenin başını döndürmeliyiz.

Son olarak, tüm bunları tek geçişte yapmalıyız, bu da liste üzerinde birden fazla döngü yapamayacağımız anlamına gelir.

Ayrıca k indeksinin listede yer aldığı da garanti edilir, dolayısıyla listenin gerçek uzunluğunun ötesine geçip geçmediğini kontrol etmemize gerek kalmaz.

Sözdiziminin bu tür bir iş için harika olması ve aynı zamanda anlaşılması oldukça basit olması nedeniyle bugün algoritmayı oluşturmak için Go'yu kullanacağız.

En baştan başlayalım: basit bir bağlantılı liste oluşturmak.

Bağlantılı Liste

Bağlantılı listenin arkasındaki kavram oldukça basittir: nesnelerden (genellikle düğümler olarak adlandırılır) oluşan bir listedir ve her düğümün en az iki özelliğe sahip olması gerekir: bir değer (gerçekte düğümün içerdiği bir şey) ve bir sonraki düğüme bir bağlantı .

Genellikle bir işaretçi , bir düğümden diğerine atlamak için bağlantı olarak kullanılır.

Ayrıca listenin ilk düğümüne genellikle listenin başı denir ve bu aynı zamanda problemin bize geri döndürmesini istediği düğümdür.

İşte grafiksel bir örnek:

Soldaki ilk düğüm, v₀ değerini ve listeyi bir sonraki n₁ düğümüne yönlendiren bir bellek işaretçisi P(n₁) içeren listenin başıdır . Aşağıdaki n₁ düğümü, değerini ve sonraki düğüme yönelik bir P(n₂) işaretçisini içerecektir ve bu şekilde devam eder.

Son düğümün elbette işaret edecek hiçbir şeyi olmayacak, dolayısıyla işaretçisinin değeri null olacaktır.

Bir tane oluşturmak için kodu görelim!

Kod oldukça basit: biri iç düğüm için, diğeri bağlantılı liste için olmak üzere iki yapı oluşturuyoruz.

• Düğümün, az önce gördüğümüz gibi, iki özelliği olacaktır; Value özelliği ve bir sonraki düğüme işaretçi olarak *Node türünü tutan Next özelliği.

• Bağlı liste, bağlantılı listeyi "başlatmak" için kullanılan ve yalnızca tek bir özelliğe sahip olan, listenin Head olan bir yapı.

  
  

Bundan sonra, listeyi ana fonksiyonda başlatıyoruz ve başına rastgele değeri 10 olan bir düğüm veriyoruz.

Bağlantılı listeyi anlamanın ardındaki anahtar, artık Head düğümünün , Node türünde olduğundan , doğası gereği bir sonraki düğümü içerecek bir Next özelliğine sahip olmasıdır . Bu son düğüm daha sonra bir sonraki düğüme atlamak için Next özelliğine sahip olacak ve bu şekilde devam edecek.

Listeye birkaç düğüm eklediğimizde her şey daha netleşecek, o halde hadi yapalım! İki seçeneğimiz var: Ya bunu manuel olarak yaparız, gerçekten sıkıcı bir iş, ya da bağlantılı liste sınıfına biraz daha düğüm eklemek için bir yöntem yazarız. Hadi kontrol edelim!

Düğüm Ekleme: Kılık Değiştirilebilir Liste

Çok az programlama deneyiminiz olsa bile hemen hemen her programlama dilinde duymanız gereken ilk kavramlardan biri değişken ve değişmez listeler arasındaki farktır.

İsimlerinden de anlaşılabileceği gibi değişken listeler, değiştirebileceğiniz ve öğeler ekleyebileceğiniz listelerdir . Bunun yerine değişmezlerin sabit bir boyutu vardır ve yeni öğelerle eklenemezler . Ama neden böyle?

Değişmez listeler bellekte bitişiktir , yani öğeleri bellekte sırayla saklanır : 3 öğeli bir liste için, eğer ilk öğe 0x00'de saklanırsa, ikincisi 0x01'de ve sonuncusu 0x02'de olacaktır.

Bu nedenle Python'da sabit bir dizi, değişmez bir liste veya bir demet üzerinde yineleme yapmak çok hızlıdır çünkü CPU, bellek dizinlerini birer birer geri çağırır.

Öte yandan, değiştirilebilir listeler yalnızca ilk başlatıldığında bellekte bitişiktir: bu noktada, öğeler eklenirse artık sıralı olmayacaklardır. Peki bunların üzerinden nasıl geçiş yapabiliriz?

Çünkü ilk başlatmanın son elemanı, kendisinden sonra eklenen elemanın bir işaretçisine sahip olacak , bu da bize eklenen elemanı getirecek ve bu şekilde devam edecek. Yani evet, değiştirilebilir listeler genellikle kılık değiştirmiş bağlantılı listelerdir!

Şimdi kodu görelim:

Bağlantılı listemizin yöntemlerine AddNode yöntemini ekledik. Düğüm ekleme süreci şu şekilde gerçekleşir:

• Öncelikle Head değerini current adı verilen bir değişkende saklıyoruz.

• Daha sonra, bir sonraki düğüm boş olana kadar current değişkeni her seferinde bir sonraki düğümle güncelleyen bağlantılı liste üzerinde döngü yaparız. Şu anda bulunduğumuz düğüm bir boş göstericiye sahip olduğunda listenin son düğümünde olduğumuzu biliyoruz.

• Son olarak bu son düğümü yeni bir düğüm ve yeni bir değerle güncelliyoruz (Bu yeni düğümün Next işaretçisi boş bırakırsak null olarak ayarlanacaktır)

  
  

Grafiksel olarak bu süreç şuna benzer:

Bağlantılı listedeki düğümlerin değerlerini yazdırarak ana fonksiyonda bu yöntemin doğru çalışıp çalışmadığını kontrol edebiliriz.

Düğümün Çıkarılması

Şimdi sorunumuzun son kısmı ve çözümüne geçelim: Doğru indekse sahip bir düğümü kaldırmak. Öncelikle bağlantılı bir listeden bir düğümü kaldırmak ne anlama gelir? Düşünürsek, bağlantılı listedeki bir düğüm ancak bir öncekine bağlıysa var olur , değil mi?

Örneğin, n-1ᵗʰ'ye bir Next değeri null verirsek, nᵗʰ değerinin listeden bağlantısını kesebiliriz.

Peki ya kaldırmak istediğimiz öğe son öğe değilse? Bir öncekini bir sonrakine bağlayarak öğenin bağlantısını kaldırabiliriz !

Yani kᵗʰ öğesini kaldırmak için k-1ᵗʰ öğesini bulmalı ve onu k+1ᵗʰ düğümüne bağlamalıyız. Önceki düğümü (k-1ᵗʰ) saklamamız gerekecek.

Açıkçası, listeyi doğrudan indeksleyemeyiz : linkedlist[n] gibi bir şey deneyin, sadece bir hata ortaya çıkacaktır. Ancak bu göz önüne alındığında, listenin başını dizin 0, sonraki düğümü ise dizin 1 olarak düşünebiliriz ve daha önce yaptığımız gibi düğümler üzerinde döngü de yapabiliriz.

O zaman yapabileceğimiz şey, bulunduğumuz düğümü takip etmek için bir sayaç uygulamaktır!

O zaman kodlayalım.

Bir index niteliğini kabul eden RemoveNode fonksiyonuna bakalım. Bundan sonra üç değişkeni başlatıyoruz:

• previousNode önceki düğümü tutacak

• current , döngü sırasında bulunduğumuz düğümü tutacak

• counter başlangıçta 0'a eşittir, bu da listedeki konumumuzu koruyacaktır

  
  

Şimdilik ilk if bloğunu atlayalım ve bunun yerine for döngüsüne odaklanalım. counter değişkenimiz index kesinlikle küçük olana kadar döngüye başlarız: her döngü daha sonra önceki düğümü mevcut düğümle günceller ve mevcut düğümü ve sayacı güncellemeye devam eder.

Döngü bozulduğunda, bu , istediğimiz indeksten hemen önceki düğümde olduğumuz anlamına gelir: sadece önceki düğümün işaretçisini, prev.Next , içinde bulunduğumuz bu düğümden listedeki bir sonraki düğümle güncellememiz gerekir. current.Next olacak.Sonraki . Son olarak bağlantılı listenin başını döndürüyoruz.

Şimdi kaldırılacak indeks, indeksi 0 olan kafa ise ne olur? Döngü hiçbir zaman başlamayacaktır çünkü counter = 0 ve index = 0 ile başlayacaktır ve koşul anında yanlış olacaktır. Bu ilk durumu üstteki if bloğu ile yönetebiliriz.

Temel olarak, eğer indeks 0 ise bağlantılı listenin başlığını yanındaki düğümle doğrudan güncelleyebilir ve geri döndürebiliriz. Dikkatinizi özellikle 31. satıra çekmek istiyorum: Go, diğer birçok dilde olduğu gibi, işlevlere nitelikleri değere göre aktarır ; bu, işlevin , ilettiğiniz gerçek nesnenin değil , aktarılan nesnenin bir kopyasını tuttuğu anlamına gelir. .

Bu kavram şu örnekte açıkça görülmektedir:

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

Öznitelik olarak iletilen değerin bellek adresini yazdıracak bir fonksiyon oluşturuyoruz. Daha sonra ana fonksiyonda bir a değişkeni yaratıp onun hafıza adresini yazdırıyoruz. Daha sonra aynı değişkeni fonksiyona aktarıp hafıza adresini yazdırıyoruz.

Gördüğünüz gibi, denerseniz sonuçlar farklı olacaktır: bunun nedeni, niteliklerin işlevlere değer olarak aktarılmasıdır; bu, a bir kopyasının, onu işleve aktarmak amacıyla oluşturulduğu anlamına gelir.

Bağlantılı listemize dönersek, yukarıdaki aynı sorunun gerçek nedenini bulmak için işaretçileri kullanmalıyız. Dolayısıyla “gerçek” ll.Node ulaşmak için onun işaretçisini *ll.Node hatırlamalı ve onu *ll.Node = *ll.Node.Next ile daha ileriye taşımalıyız .

Ana fonksiyonda, çağrıları yönteme ekleriz, örneğin ll.RemoveNode(0) ve ll.RemoveNode(2) çağrılarını yaparak, düğüm 0 ve düğüm 2'nin eksik olacağı sonucu kontrol edebiliriz.

Çözüm

Sonuna kadar ulaştık!

Buraya kadar okursanız tüm minnettarlığım size gider. Bir veya iki beğeni bırakıp makaleyi paylaşmaya istekliyseniz, bu benim günümü güzelleştirecek ve bu makaleleri yazmaya devam etmeme yardımcı olacak!

Bir sonraki makalede görüşmek üzere ve her zaman olduğu gibi okuduğunuz için teşekkürler.

Nicola