Bilgi her yerdedir.

Yazılım dünyasında, bilgilerimizi organize etmek için seçtiğimiz yollar savaşın yarısıdır. Yine de bir şey var: Bir problemi çözmenin pek çok yolu var . Verilerimizi düzenlemek söz konusu olduğunda, iş için işe yarayabilecek birçok araç var. İşin püf noktası, hangi aracın doğru araç olduğunu bilmektir .

Hangi dilde kodlamaya başladığımızdan bağımsız olarak, karşılaştığımız ilk şeylerden biri, verilerimizi organize etmenin farklı yolları olan veri yapılarıdır ; değişkenler , diziler , karmalar ve nesneler tüm veri yapıları türleridir. Ancak veri yapıları söz konusu olduğunda bunlar hala buzdağının görünen kısmı; çok daha fazlası var, bazıları onlar hakkında ne kadar çok şey duyarsanız çok karmaşık gelmeye başlıyor.

Benim için bu karmaşık şeylerden biri her zaman bağlantılı listeler olmuştur . Bağlantılı listeleri birkaç yıldır biliyorum, ancak onları asla kafamda tam olarak tutamıyorum. Sadece teknik bir röportaj için hazırlanırken (veya bazen ortasında) onları gerçekten düşünüyorum ve biri bana onları soruyor. Biraz araştırma yapacağım ve neyle ilgili olduklarını anladığımı düşüneceğim, ancak birkaç hafta sonra onları tekrar unutuyorum. Her şey oldukça verimsiz ve hepsi var olduklarını bildiğim gerçeğinden kaynaklanıyor, ancak temelde onları anlamıyorum ! Öyleyse, bunu değiştirmenin ve şu soruyu cevaplamanın zamanı geldi: Bağlantılı liste nedir ki?

Doğrusal veri yapıları

Bağlantılı listelerin temellerini gerçekten anlamak istiyorsak, ne tür veri yapısı olduklarından bahsetmemiz önemlidir .

Bağlantılı listelerin bir özelliği, doğrusal veri yapıları olmalarıdır; bu , bunların nasıl yapılandırıldıklarına ve geçtiklerine dair bir sıra ve bir sıra olduğu anlamına gelir. Bir seksek oyunu gibi doğrusal bir veri yapısı düşünebiliriz : Listenin sonuna gelmek için, listedeki tüm öğeleri sırayla veya sırayla gözden geçirmeliyiz . Doğrusal yapılar, doğrusal olmayan yapıların tersidir. Olarak doğrusal olmayan veri yapıları , ürün Veri yapısı geçiş olabilir, bu araçların, sıra ile düzenlenmiş olması gerekmez olmayan sekans .

Her zaman fark etmeyebiliriz, ancak hepimiz her gün doğrusal ve doğrusal olmayan veri yapılarıyla çalışıyoruz! Verilerimizi karmalar halinde düzenlediğimizde (bazen sözlük olarak adlandırılır ), doğrusal olmayan bir veri yapısı uygularız. Ağaçlar ve grafikler de farklı şekillerde geçtiğimiz doğrusal olmayan veri yapılarıdır, ancak yıl içinde onlar hakkında daha derinlemesine konuşacağız.

Benzer şekilde, kodumuzda diziler kullandığımızda , doğrusal bir veri yapısı uyguluyoruz! Dizilerin ve bağlantılı listelerin verileri sıralama şeklimiz açısından benzer olduğunu düşünmek yardımcı olabilir. Her iki yapıda da düzen önemlidir . Peki dizileri ve bağlantılı listeleri farklı kılan nedir?

Hafıza yönetimi

Diziler ve bağlantılı listeler arasındaki en büyük fark, makinelerimizde belleği kullanma biçimleridir. Ruby, JavaScript veya Python gibi dinamik olarak yazılmış dillerle çalışanlarımız, günlük olarak kodumuzu yazarken bir dizinin ne kadar bellek kullandığını düşünmek zorunda değiliz çünkü sonuçta birkaç soyutlama katmanı var. bellek ayırma konusunda endişelenmemize gerek kalmaz.

Ancak bu, bellek tahsisinin gerçekleşmediği anlamına gelmez! Soyutlama sihir değildir, sadece görmeniz veya her zaman uğraşmanız gerekmeyen şeyleri saklamanın basitliğidir. Kodu yazarken bellek tahsisi hakkında düşünmemize gerek kalmasa bile, bağlantılı bir listede neler olup bittiğini ve onu neyin güçlü kıldığını gerçekten anlamak istiyorsak, temel seviyeye inmeliyiz.

İkili ve verilerin nasıl bit ve baytlara bölünebileceğini zaten öğrendik . Karakterlerin, sayıların, kelimelerin, cümlelerin kendilerini temsil etmek için bayt bellek gerektirmesi gibi, veri yapıları da öyle.

Bir dizi oluşturulduğunda, belirli bir miktarda belleğe ihtiyaç duyar. Bir dizide saklamamız gereken 7 harf olsaydı, bu diziyi temsil etmek için 7 bayt belleğe ihtiyacımız olurdu. Ancak, tüm bu hafızanın tek bir bitişik blokta olması gerekir . Diğer bir deyişle, bilgisayarımızın 7 baytlık boş belleği bir bayt diğerinin yanına, hep birlikte tek bir yerde bulması gerekir.

Öte yandan, bağlantılı bir liste doğduğunda, tek bir yerde 7 bayt belleğe ihtiyaç duymaz. Bir bayt bir yerde yaşarken, sonraki bayt tamamen bellekte başka bir yerde saklanabilir! Bağlı listelerin tek bir bellek bloğu almasına gerek yoktur; bunun yerine kullandıkları hafıza baştan aşağı dağılabilir .

Diziler ve bağlantılı hale getirilmiş listeler arasındaki temel fark dizileri olmasıdır olan statik veri yapıları ise, bağlı listeler olan dinamik veri yapıları . Statik bir veri yapısı, yapı oluşturulurken tüm kaynaklarının tahsis edilmesini gerektirir; bu, yapının boyut olarak büyümesi veya küçülmesi ve elemanların eklenmesi veya çıkarılması durumunda bile, her zaman belirli bir boyut ve miktarda belleğe ihtiyaç duyduğu anlamına gelir. Statik bir veri yapısına daha fazla öğenin eklenmesi gerekiyorsa ve yeterli belleğe sahip değilse, örneğin o dizinin verilerini kopyalamanız ve daha fazla bellekle yeniden oluşturmanız gerekir, böylece öğeler eklenebilir. o.

Öte yandan, dinamik bir veri yapısı küçülüp bellekte büyüyebilir. Var olması için tahsis edilecek belirli miktarda belleğe ihtiyacı yoktur ve boyutu ve şekli değişebilir ve ihtiyaç duyduğu bellek miktarı da değişebilir.

Şimdiye kadar, diziler ve bağlantılı listeler arasında bazı önemli farklılıkları görmeye başlayabiliriz. Ancak bu şu soruyu akla getiriyor: bağlantılı bir listenin hafızasının her yere dağılmasına izin veren nedir? Bu soruyu cevaplamak için bağlantılı bir listenin yapılandırılma şekline bakmamız gerekir.

Bağlantılı bir listenin bölümleri

Bağlantılı bir liste küçük veya çok büyük olabilir, ancak boyutu ne olursa olsun, onu oluşturan parçalar aslında oldukça basittir. Bağlantılı bir liste, listenin öğeleri olan bir dizi düğümden oluşur.

Listenin başlangıç ​​noktası, baş olarak adlandırılan ilk düğüme bir referanstır . Neredeyse tüm bağlantılı listelerin bir başlığı olmalıdır, çünkü bu, listeye ve tüm öğelerine etkin bir şekilde tek giriş noktasıdır ve onsuz, nereden başlayacağınızı bilemezsiniz! Listenin sonu bir düğüm değil, null veya boş bir değere işaret eden bir düğümdür .

Tek bir düğüm de oldukça basittir. Yalnızca iki bölümden oluşur: veriler veya düğümün içerdiği bilgi ve sonraki düğüme başvuru .

Kafamızı bunun etrafında toplayabilirsek, yolun yarısına ulaşmış oluruz. Düğümlerin çalışma şekli çok önemlidir ve çok güçlüdür ve şu şekilde özetlenebilir:

Bir düğüm yalnızca hangi verileri içerdiğini ve komşusunun kim olduğunu bilir.

Tek bir düğüm, bağlantılı listenin ne kadar uzun olduğunu bilmez ve nerede başladığını veya nerede bittiğini bile bilmeyebilir. Bir düğümün ilgilendiği tek şey, içerdiği veriler ve işaretçisinin hangi düğüme - listedeki bir sonraki düğüme başvurduğudur.

Ve bağlantılı bir listenin bitişik bir bellek bloğuna ihtiyaç duymamasının nedeni de budur . Tek bir düğüm bir sonraki düğüme "adres" veya referansa sahip olduğundan, bir dizideki öğelerin olması gerektiği gibi, yan yana yaşamaları gerekmez. Bunun yerine, bir sonraki düğüme işaretçi referanslarına dayanarak listemizde gezinebileceğimiz gerçeğine güvenebiliriz, bu, makinelerimizin listemizi temsil etmek için tek bir bellek parçasını bloke etmesine gerek olmadığı anlamına gelir.

Bu aynı zamanda, bir programın yürütülmesi sırasında bağlantılı listelerin neden dinamik olarak büyüyüp küçülebileceğinin açıklamasıdır. Bağlantılı bir listeye sahip bir düğümü eklemek veya kaldırmak, bir dizinin öğelerini kopyalamak yerine bazı işaretçileri yeniden düzenlemek kadar basit hale gelir! Bununla birlikte, bağlantılı listelerin henüz size bahsetmediğim bazı dezavantajları da var - ancak önümüzdeki hafta bunlarda daha fazlası var.

Şimdilik, bağlantılı listelerin ne kadar havalı olduğunun tadını çıkaracağız!

Tüm şekiller ve boyutlar için listeler

Bağlantılı bir listenin parçaları değişmez olsa da, bizim bağlı listeler yapısı bu şekilde olabilir oldukça farklı olabilir. Yazılımdaki çoğu şey gibi, çözmeye çalıştığımız soruna bağlı olarak, bir tür bağlantılı liste, iş için diğerinden daha iyi bir araç olabilir.

Tek bağlantılı listeler , yalnızca tek bir yöne gittikleri gerçeğine dayanan en basit bağlantılı liste türüdür. Bir yoktur tek parça biz listeyi geçebilmesini; Baş düğümdebaşlıyoruzve kökten son düğümekadarilerliyoruz, bu da boş bir boş değerlebitecek.

Ancak bir düğümün sonraki komşu düğümüne başvurabilmesi gibi, aynı zamanda önceki düğümüne de bir referans işaretçisine sahip olabilir! Bu, çift ​​bağlantılı liste dediğimiz şeydir , çünkü her düğümde iki referans vardır : bir sonraki düğüme ve ayrıca önceki düğüme bir başvuru . Bu, veri yapımızı yalnızca tek bir yolda veya yönde değil, aynı zamanda geriye doğru da geçebilmek istiyorsak faydalı olabilir.

Örneğin , listenin en başına geri dönmek zorunda kalmadan bir düğüm ile önceki düğüm arasında atlama yapabilmek istiyorsak , çift bağlantılı bir liste, tek bağlantılı bir listeden daha iyi bir veri yapısı olacaktır. Bununla birlikte, her şey alan ve bellek gerektirir, bu nedenle düğümümüzün sadece bir yerine iki referans işaretçisi depolaması gerekirse, bu dikkate alınması gereken başka bir şey olur.

Bir dairesel bağlantılı liste bir boş değer bir düğüm işaret ile bitmez biraz garip. Bunun yerine, listenin kuyruğu olarak hareket eden bir düğüme sahiptir (geleneksel baş düğüm yerine) ve kuyruk düğümünden sonraki düğüm listenin başlangıcıdır. Bu organizasyon yapısı, listenin sonuna bir şeyler eklemeyi gerçekten kolaylaştırır, çünkü ilk öğe ve son öğe birbirini gösterdiği için, onu kuyruk düğümünden geçmeye başlayabilirsiniz . Dairesel bağlantılı listeler gerçekten çıldırmaya başlayabilir çünkü hem tekil bağlantılı bir listeyi hem de çift bağlantılı bir listeyi döngüsel bağlantılı bir listeye dönüştürebiliriz !

Ancak bağlantılı bir liste ne kadar karmaşık olursa olsun, bir düğümün temellerini, nasıl çalıştığını ve listemizdeki farklı işaretçi referanslarının nasıl yapılandırıldığını hatırlayabilirsek, üstesinden gelemeyeceğimiz bağlantılı bir liste yoktur!

Önümüzdeki hafta, bu dizinin 2. bölümünde, bağlantılı listelerin uzay-zaman karmaşıklığına ve kuzenleri olan diziye kıyasla nasıl olduklarına dişlerimizi batıracağız. Söz veriyorum, aslında göründüğünden çok daha eğlenceli!

Kaynaklar

Bağlantılı listelerin çok havalı olduğunu düşünüyorsanız, bu yararlı kaynaklara göz atın.

1. Diziler ve Bağlantılı Listeler arasındaki farklar , Damien Wintour
2. Veri Yapıları: Diziler ve Bağlantılı Listeler , mycodeschool
3. Bağlantılı Listeler: Temel Bilgiler , Dr.Edward Gehringer
4. Bağlantılı Listelere Giriş , Dr. Victor Adamchik
5. Veri Yapıları ve Uygulamalar , Dr. Jennifer Welch
6. Statik Veri Yapıları ve Dinamik Veri Yapıları , Ayoma Gayan Wijethunga