Bağlantılı liste - Linked list

Düğümleri iki alan içeren bağlantılı bir liste: bir tamsayı değeri ve bir sonraki düğüme bağlantı. Son düğüm, listenin sonunu belirtmek için kullanılan bir sonlandırıcıya bağlanır.

Gelen bilgisayar bilimleri , bir bağlantılı liste sırası bellekte fiziksel yerleşim tarafından verilmediği veri elemanlarının doğrusal topluluğudur. Bunun yerine, her öğe bir sonrakine işaret eder. Birlikte bir diziyi temsil eden düğümler koleksiyonundan oluşan bir veri yapısıdır . En temel biçiminde, her düğüm şunları içerir: data ve bir referans (başka bir deyişle, bir bağlantı) sıradaki bir sonraki düğüme. Bu yapı, yineleme sırasında dizideki herhangi bir konumdan öğelerin verimli bir şekilde yerleştirilmesine veya çıkarılmasına izin verir. Daha karmaşık varyantlar, ek bağlantılar ekleyerek, düğümlerin isteğe bağlı konumlarda daha verimli eklenmesine veya çıkarılmasına izin verir. Bağlantılı listelerin bir dezavantajı, erişim süresinin doğrusal olmasıdır (ve ardışık düzene geçirilmesi zordur ). Rastgele erişim gibi daha hızlı erişim mümkün değildir. Diziler , bağlantılı listelere kıyasla daha iyi önbellek konumuna sahiptir .

Bağlantılı listeler, en basit ve en yaygın veri yapıları arasındadır. Listeler , yığınlar , kuyruklar , ilişkisel diziler ve S-ifadeleri dahil olmak üzere diğer birçok ortak soyut veri türünü uygulamak için kullanılabilirler , ancak bu veri yapılarını temel olarak bağlantılı bir liste kullanmadan doğrudan uygulamak nadir değildir.

Bağlantılı bir listenin geleneksel bir diziye göre başlıca yararı , liste öğelerinin, bir dizi yeniden yapılandırılırken veri öğelerinin bitişik olarak bellekte veya diskte depolanması gerekmediğinden, tüm yapının yeniden tahsisi veya yeniden düzenlenmesi gerekmeden kolayca eklenip çıkarılabilmesidir . çalışma zamanı çok daha pahalı bir işlemdir. Bağlantılı listeler, listenin herhangi bir noktasında düğümlerin eklenmesine ve çıkarılmasına izin verir ve bunu, liste geçişi sırasında bağlantıyı, eklenen veya kaldırılan bağlantıdan önceki bağlantıyı tutarak sabit sayıda işlemle yapmaya izin verir.

Öte yandan, basit bağlantılı listeler kendi başlarına verilere rastgele erişime veya herhangi bir verimli indeksleme biçimine izin vermediğinden , listenin son düğümünü elde etmek, belirli bir veriyi içeren bir düğümü bulmak veya yeni bir düğümün eklenmesi gereken yeri bulmak—liste öğelerinin çoğu veya tamamı boyunca yinelemeyi gerektirebilir. Bağlantılı listeleri kullanmanın avantajları ve dezavantajları aşağıda verilmiştir.

Tarih

Bağlantılı listeler, 1955–1956'da, RAND Corporation'da Allen Newell , Cliff Shaw ve Herbert A. Simon tarafından Bilgi İşlem Dili için birincil veri yapısı olarak geliştirildi . IPL, yazarlar tarafından Mantık Teorisi Makinesi, Genel Problem Çözücü ve bir bilgisayar satranç programı dahil olmak üzere birçok erken yapay zeka programı geliştirmek için kullanıldı . Çalışmalarıyla ilgili raporlar, 1956'da Bilgi Teorisi Üzerine IRE İşlemlerinde ve 1957 ve 1958'deki Batı Ortak Bilgisayar Konferansı Bildirileri ve Bilgi İşleme (ilk UNESCO Uluslararası Bilgi İşleme Konferansı Bildirileri) dahil olmak üzere 1957'den 1959'a kadar olan birkaç konferans bildirisinde yer aldı. Ardışık liste düğümlerini gösteren oklarla liste düğümlerini temsil eden bloklardan oluşan şimdi klasik olan diyagram, Newell ve Shaw tarafından Proc. WJCC, Şubat 1957. Newell ve Simon, "yapay zekaya, insan bilişinin psikolojisine ve liste işlemeye temel katkılarda bulundukları" için 1975'te ACM Turing Ödülü'ne layık görüldüler . Doğal dil işleme için makine çevirisi sorunu , Massachusetts Teknoloji Enstitüsü'nden (MIT) Victor Yngve'yi , dilbilim alanındaki bilgisayar araştırmaları için COMIT programlama dilinde veri yapıları olarak bağlantılı listeleri kullanmaya yöneltti . Bu dil hakkında "Mekanik çeviri için bir programlama dili" başlıklı bir rapor 1958'de Mekanik Çeviri'de yayınlandı.

Bağlantılı listelerin bir başka erken görünümü, Ocak 1953'te zincirleme karma tablolarında bağlantılı listelerin kullanılmasını öneren dahili bir IBM memorandumu yazan Hans Peter Luhn tarafından yapıldı.

Liste işlemcisi anlamına gelen LISP , John McCarthy tarafından 1958'de MIT'deyken yaratıldı ve 1960'da ACM'nin Communications dergisinde "Recursive Functions of Symbolic Expressions and They Computation by Machine, Part" başlıklı bir makalede yayınladı. BEN". LISP'in ana veri yapılarından biri bağlantılı listedir.

1960'ların başlarında, hem bağlantılı listelerin hem de bu yapıları birincil veri temsilleri olarak kullanan dillerin faydası iyice yerleşmişti. MIT Lincoln Laboratuvarı'ndan Bert Green, Mart 1961'de Elektronikte İnsan Faktörleri Üzerine IRE İşlemlerinde, bağlantılı liste yaklaşımının avantajlarını özetleyen "Sembol manipülasyonu için bilgisayar dilleri" başlıklı bir inceleme makalesi yayınladı. Daha sonra Bobrow ve Raphael tarafından yazılan "Liste işleyen bilgisayar dillerinin bir karşılaştırması" adlı bir inceleme makalesi, Communications of the ACM'de Nisan 1964'te yayınlandı.

Teknik Sistem Danışmanları (başlangıçta West Lafayette Indiana ve daha sonra Chapel Hill, Kuzey Karolina) tarafından geliştirilen birkaç işletim sistemi , dosya yapıları olarak tek tek bağlantılı listeleri kullandı. Bir dizin girişi, bir dosyanın ilk sektörünü işaret etti ve dosyanın sonraki bölümleri, işaretçiler arasında geçiş yaparak bulundu. Bu tekniği kullanan sistemler arasında Flex ( Motorola 6800 CPU için), mini-Flex (aynı CPU) ve Flex9 (Motorola 6809 CPU için) bulunur. California'da Smoke Signal Broadcasting için TSC tarafından geliştirilen ve pazarlanan bir varyant , aynı şekilde çift bağlantılı listeler kullandı.

IBM tarafından System 360/370 makineleri için geliştirilen TSS/360 işletim sistemi, dosya sistemi kataloğu için çift bağlantılı bir liste kullandı. Dizin yapısı, bir dizinin dosyaları ve diğer dizinleri içerebileceği ve herhangi bir derinliğe uzanabileceği Unix'e benziyordu.

Temel kavramlar ve adlandırma

Bağlantılı bir listenin her kaydı genellikle bir "eleman" veya " düğüm " olarak adlandırılır.

Her düğümün bir sonraki düğümün adresini içeren alanı genellikle 'sonraki bağlantı' veya 'sonraki işaretçi' olarak adlandırılır. Kalan alanlar 'veri', 'bilgi', 'değer', 'kargo' veya 'yük' alanları olarak bilinir.

Bir listenin 'kafası' onun ilk düğümüdür. Bir listenin 'kuyruğu', ya baştan sonra listenin geri kalanına ya da listedeki son düğüme atıfta bulunabilir. Gelen Lisp ve bazı türetilmiş dil, bir sonraki düğümün denebilir CDR (telaffuz ' olabilir-er kafa düğümün yükü 'araba' olarak adlandırılan olabilir iken, listenin).

Tek bağlantılı liste

Tek başına bağlantılı listeler, bir veri alanına ve ayrıca düğümler sırasında bir sonraki düğüme işaret eden 'sonraki' alana sahip düğümleri içerir. Tek bağlantılı listelerde gerçekleştirilebilecek işlemler, ekleme, silme ve geçişi içerir.

Düğümleri iki alan içeren tek bağlantılı bir liste: bir tamsayı değeri ve bir sonraki düğüme bağlantı

Aşağıdaki kod, tek başına bağlantılı bir listenin sonuna "değer" verisine sahip yeni bir düğümün nasıl ekleneceğini gösterir:

node addNode(node head, int value) {
    node temp, p; // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL.
    temp->data = value; // add element's value to data part of node
    if (head == NULL) {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points to NULL.
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}

Çift bağlantılı liste

'Çift bağlantılı listede', her düğüm, sonraki düğüm bağlantısının yanı sıra, dizideki 'önceki' düğümü işaret eden ikinci bir bağlantı alanı içerir. İki bağlantı 'ileri('ler') ve 'geri' veya 'sonraki' ve 'önceki'('önceki') olarak adlandırılabilir.

Düğümleri üç alan içeren çift bağlantılı bir liste: bir tamsayı değeri, sonraki düğüme giden bağlantı ve önceki düğüme giden bağlantı

XOR-bağlama olarak bilinen bir teknik , her düğümde tek bir bağlantı alanı kullanılarak çift bağlantılı bir listenin uygulanmasına izin verir. Ancak bu teknik, adresler üzerinde bit işlemleri yapabilmeyi gerektirir ve bu nedenle bazı yüksek seviyeli dillerde bulunmayabilir.

Birçok modern işletim sistemi, etkin süreçlere, iş parçacıklarına ve diğer dinamik nesnelere referansları korumak için çift bağlantılı listeler kullanır. Rootkit'lerin algılanmaktan kaçınması için yaygın bir strateji, kendilerini bu listelerden ayırmaktır.

Bağlantılı listeyi çoğalt

'Çarpma bağlantılı liste'de, her düğüm iki veya daha fazla bağlantı alanı içerir, her alan aynı veri kayıtlarını aynı kümenin farklı bir sırasına bağlamak için kullanılır (örn. ada göre, departmana göre, doğum tarihine göre, vesaire.). Çift bağlantılı listeler, çoklu bağlantılı listelerin özel durumları olarak görülebilirken, iki ve daha fazla sıranın birbirine zıt olması, daha basit ve daha verimli algoritmalara yol açar, bu nedenle genellikle ayrı bir durum olarak ele alınır.

Dairesel bağlantılı liste

Listenin son düğümünde, bağlantı alanı genellikle boş bir referans içerir , başka düğümlerin olmadığını belirtmek için özel bir değer kullanılır. Daha az yaygın bir kural, listenin ilk düğümüne işaret etmesini sağlamaktır; bu durumda listenin 'dairesel' veya 'dairesel olarak bağlantılı' olduğu söylenir; aksi takdirde 'açık' veya 'doğrusal' olduğu söylenir. Son işaretçinin ilk düğümü gösterdiği bir listedir.

Dairesel bağlantılı liste

Dairesel çift bağlantılı liste durumunda, ilk düğüm ayrıca listenin son düğümüne işaret eder.

Nöbetçi düğümler

Bazı uygulamalarda, ilk veri kaydından önce veya sonuncusundan sonra fazladan bir 'nöbetçi' veya 'kukla' düğüm eklenebilir. Bu kural, tüm bağlantıların güvenli bir şekilde başvurunun kaldırılabilmesini ve her listenin (hiçbir veri öğesi içermese bile) her zaman bir "ilk" ve "son" düğüme sahip olmasını sağlayarak bazı liste işleme algoritmalarını basitleştirir ve hızlandırır.

Boş listeler

Boş bir liste, veri kaydı içermeyen bir listedir. Bu genellikle sıfır düğümü olduğunu söylemekle aynıdır. Nöbetçi düğümler kullanılıyorsa, yalnızca nöbetçi düğümleri olduğunda listenin genellikle boş olduğu söylenir.

karma bağlama

Bağlantı alanlarının fiziksel olarak düğümlerin bir parçası olması gerekmez. Veri kayıtları bir dizide saklanıyorsa ve indeksleri tarafından referans veriliyorsa, link alanı veri kayıtlarıyla aynı indekslere sahip ayrı bir dizide saklanabilir.

Liste tutamaçları

İlk düğüme yapılan bir başvuru tüm listeye erişim sağladığından, bu başvuruya genellikle listenin 'adres', 'işaretçi' veya 'tutamaç' adı verilir. Bağlantılı listeleri işleyen algoritmalar genellikle bu tür tutamaçları giriş listelerine alır ve tutamaçları sonuç listelerine döndürür. Aslında, bu tür algoritmalar bağlamında, "liste" kelimesi genellikle "liste tutamacı" anlamına gelir. Ancak bazı durumlarda, ilk ve son düğümlerine işaret eden iki bağlantıdan oluşan bir tanıtıcı ile bir listeye başvurmak uygun olabilir.

Alternatifleri birleştirmek

Yukarıda listelenen alternatifler, hemen hemen her şekilde keyfi olarak birleştirilebilir, bu nedenle, nöbetçisiz dairesel çift bağlantılı listeler, nöbetçili dairesel tek bağlantılı listeler vb. olabilir.

ödünleşimler

Bilgisayar programlama ve tasarımındaki çoğu seçenekte olduğu gibi, hiçbir yöntem tüm koşullara uygun değildir. Bağlantılı bir liste veri yapısı bir durumda iyi çalışabilir, ancak başka bir durumda sorunlara neden olabilir. Bu, bağlantılı liste yapılarını içeren bazı ortak ödünleşimlerin bir listesidir.

Bağlantılı listeler ve dinamik diziler

Bir dinamik bir dizi bitişik bellekte tüm elemanları tahsis eden bir veri yapısıdır ve elemanların mevcut sayısının bir tutar. Dinamik dizi için ayrılan alan aşılırsa, yeniden tahsis edilir ve (muhtemelen) kopyalanır, bu da pahalı bir işlemdir.

Bağlantılı listelerin dinamik dizilere göre birçok avantajı vardır. Düğüme (kaldırılacak olandan önce veya ekleme noktasından önce) bir işaretçi indekslediğimizi varsayarsak, bir listenin belirli bir noktasına bir öğenin eklenmesi veya silinmesi, zaten sabit zamanlı bir işlemdir (aksi takdirde bu olmadan) referansı O(n)) iken, rastgele konumlarda dinamik bir diziye ekleme, ortalama olarak öğelerin yarısının ve en kötü durumda tüm öğelerin taşınmasını gerektirecektir. Bir diziden bir öğe, yuvasını bir şekilde "boş" olarak işaretleyerek sabit zamanda "silinebilir", ancak bu , yinelemenin performansını engelleyen parçalanmaya neden olur .

Ayrıca, keyfi olarak birçok öğe, yalnızca mevcut toplam bellekle sınırlı olarak bağlantılı bir listeye eklenebilir; dinamik bir dizi sonunda temeldeki dizi veri yapısını dolduracak ve yeniden tahsis etmek zorunda kalacak - pahalı bir işlem, bellek parçalanmışsa bile mümkün olmayabilir, ancak yeniden tahsis maliyeti eklemelere göre ortalanabilir ve maliyeti yeniden tahsis nedeniyle bir ekleme yine de itfa edilecektir O(1). Bu, dizinin sonuna öğelerin eklenmesine yardımcı olur, ancak orta konumlara ekleme (veya çıkarma) yine de bitişikliği korumak için veri taşınması nedeniyle yüksek maliyetler taşır. Çok fazla alan israfını önlemek için birçok elemanın kaldırıldığı bir dizinin de yeniden boyutlandırılması gerekebilir.

Öte yandan, dinamik diziler (aynı zamanda sabit boyutlu dizi veri yapıları ) sabit zamanlı rastgele erişime izin verirken, bağlantılı listeler yalnızca öğelere sıralı erişime izin verir . Tek başına bağlantılı listeler, aslında, yalnızca bir yönde kolayca geçilebilir. Bu, heapsort gibi bir öğeyi indeksine göre hızlı bir şekilde aramanın yararlı olduğu uygulamalar için bağlantılı listeleri uygunsuz hale getirir . Dizilere ve dinamik dizilere sıralı erişim, birçok makinedeki bağlantılı listelerden daha hızlıdır, çünkü bunlar en uygun referans konumuna sahiptirler ve bu nedenle veri önbelleğini iyi kullanırlar.

Bağlantılı listelerin bir başka dezavantajı, referanslar için gereken ekstra depolamadır, bu da onları karakterler veya boole değerleri gibi küçük veri öğelerinden oluşan listeler için genellikle pratik değildir , çünkü bağlantılar için depolama yükü, bağlantıların boyutunu iki veya daha fazla kat aşabilir. veri. Buna karşılık, dinamik bir dizi yalnızca verinin kendisi için alan (ve çok az miktarda kontrol verisi) gerektirir. Ayrıca yavaş olabilir ve saf bir ayırıcıyla, her yeni öğe için ayrı ayrı bellek ayırmak israfa neden olabilir; bu genellikle bellek havuzları kullanılarak çözülen bir sorundur .

Bazı hibrit çözümler, iki gösterimin avantajlarını birleştirmeye çalışır. Unrolled bağlantılı listeler , her bir liste düğümünde birkaç öğe depolayarak, referanslar için bellek yükünü azaltırken önbellek performansını artırır. CDR kodlaması , referansları referans kaydının sonuna kadar uzanan referans verilen gerçek verilerle değiştirerek her ikisini de yapar.

Dinamik dizileri bağlantılı listelere karşı kullanmanın artılarını ve eksilerini vurgulayan iyi bir örnek, Josephus sorununu çözen bir program uygulamaktır . Josephus sorunu, bir grup insanın bir daire içinde durmasıyla işleyen bir seçim yöntemidir. Önceden belirlenmiş bir kişiden başlayarak, dairenin etrafında n kez sayılabilir . Bir kez n inci kişi ulaşıldığında, bir dairenin bunları kaldırmak ve üyeleri çemberi kapatmak olmalıdır. İşlem tek kişi kalana kadar tekrarlanır. O kişi seçimi kazanır. Bu, dinamik bir diziye karşı bağlantılı bir listenin güçlü ve zayıf yönlerini gösterir, çünkü insanlar dairesel bağlantılı bir listede bağlı düğümler olarak görülüyorsa, bağlantılı listenin düğümleri ne kadar kolay silebildiğini gösterir (çünkü yalnızca bağlantıları farklı düğümlere yeniden düzenleyin). Bununla birlikte, bağlantılı liste, kaldırılacak bir sonraki kişiyi bulmakta zayıf olacak ve o kişiyi bulana kadar listede arama yapması gerekecek. Öte yandan, dinamik bir dizi, tüm öğeleri tek tek listeden yukarı kaydırmadan bir düğümü kaldıramayacağından düğümleri (veya öğeleri) silmede zayıf olacaktır. Bununla birlikte, dizideki konumlarına göre doğrudan referans vererek dairedeki n. kişiyi bulmak son derece kolaydır .

Liste sıralaması sorun, bir diziye bağlanmış liste temsili etkin dönüşüm ile ilgilidir. Geleneksel bir bilgisayar için önemsiz olmasına rağmen, bu problemi paralel bir algoritma ile çözmek karmaşıktır ve birçok araştırmanın konusu olmuştur.

Bir dengeli ağaç bir rastgele erişim için O (log n) yerine O (n) 'nin bir zaman alan, çok daha verimli indeksleme izin verecek şekilde bağlı bir listeye benzer bir bellek erişim desenleri ve uzay yükü vardır. Bununla birlikte, dengeyi korumak için ağaç manipülasyonlarının ek yükü nedeniyle ekleme ve silme işlemleri daha pahalıdır. Ağaçların kendilerini otomatik olarak dengeli bir durumda tutmaları için şemalar mevcuttur: AVL ağaçları veya kırmızı-siyah ağaçlar .

Tek başına bağlantılı doğrusal listeler ve diğer listeler

Çift bağlantılı ve dairesel listeler, tek bağlantılı doğrusal listelere göre avantajlara sahipken, doğrusal listeler, bazı durumlarda onları tercih edilir kılan bazı avantajlar sunar.

Tek başına bağlantılı bir doğrusal liste, aynı türden daha küçük bir nesneye bir işaretçi içerdiğinden, özyinelemeli bir veri yapısıdır . Bu nedenle, tek başına bağlantılı doğrusal listelerdeki ( iki listeyi birleştirmek veya öğeleri ters sırada sıralamak gibi) birçok işlem, yinelemeli komutları kullanan herhangi bir çözümden çok daha basit, genellikle çok basit özyinelemeli algoritmalara sahiptir . Bu özyinelemeli çözümler çift bağlantılı ve dairesel bağlantılı listeler için uyarlanabilirken, prosedürler genellikle ekstra argümanlara ve daha karmaşık temel durumlara ihtiyaç duyar.

Doğrusal tek başına bağlantılı listeler ayrıca , iki farklı listenin uç kısmı olarak alt listenin ortak bir son bölümünün kullanılması olan kuyruk paylaşımına da izin verir . Özellikle, bir listenin başına yeni bir düğüm eklenirse, eski liste yenisinin kuyruğu olarak mevcut kalır - kalıcı bir veri yapısının basit bir örneği . Yine, bu diğer varyantlar için doğru değildir: bir düğüm asla iki farklı döngüsel veya çift bağlantılı listeye ait olamaz.

Özellikle, uç-nöbetçi düğümler, tek tek bağlı dairesel olmayan listeler arasında paylaşılabilir. Bu tür her liste için aynı uç-nöbetçi düğümü kullanılabilir . In Lisp , örneğin, özel bir düğüme bir bağlantı ile her öz liste uçları ile belirtilen nilveya ()kimin CARve CDRbağlantılar kendine işaret. Böylece bir Lisp prosedürü , herhangi bir listenin CARveya listesini güvenle alabilir . CDR

Fantezi varyantların avantajları, genellikle verimliliklerinde değil, algoritmaların karmaşıklığı ile sınırlıdır. Özellikle dairesel bir liste, genellikle hiçbir ekstra ücret ödemeden ilk ve son düğümlere işaret eden iki değişkenle birlikte doğrusal bir listeyle öykünebilir.

Çift bağlantılı vs. tek bağlantılı

Çift bağlantılı listeler, düğüm başına daha fazla alan gerektirir ( XOR-bağlama kullanılmadığı sürece ) ve temel işlemleri daha pahalıdır; ancak listeye her iki yönde hızlı ve kolay sıralı erişime izin verdikleri için manipüle edilmeleri genellikle daha kolaydır. Çift bağlantılı bir listede, yalnızca o düğümün adresi verilen sabit sayıda işlemde bir düğüm eklenebilir veya silinebilir. Aynısını tek başına bağlantılı bir listede yapmak için, o düğümün işaretçisinin adresine sahip olunmalıdır; bu, ya tüm listenin tanıtıcısı (ilk düğüm olması durumunda) veya önceki düğümdeki bağlantı alanıdır . Bazı algoritmalar her iki yönde de erişim gerektirir. Öte yandan, çift bağlantılı listeler, kuyruk paylaşımına izin vermez ve kalıcı veri yapıları olarak kullanılamaz .

Dairesel bağlantılı vs. doğrusal bağlantılı

Dairesel olarak bağlantılı bir liste, doğal olarak dairesel olan dizileri temsil etmek için doğal bir seçenek olabilir, örneğin bir çokgenin köşeleri, FIFO ("ilk giren ilk çıkar") düzeninde kullanılan ve serbest bırakılan bir arabellek havuzu veya bir dizi o olmalıdır işleyen zaman paylaşımlı içinde kez deneme sırayla . Bu uygulamalarda, herhangi bir düğüme yönelik bir işaretçi, tüm liste için bir tanıtıcı görevi görür.

Dairesel bir liste ile, son düğüme bir işaretçi, bir bağlantıyı izleyerek ilk düğüme de kolay erişim sağlar. Bu nedenle, listenin her iki ucuna erişim gerektiren uygulamalarda (örneğin, bir kuyruğun uygulanmasında), dairesel bir yapı, yapının iki yerine tek bir işaretçi ile işlenmesine izin verir.

Dairesel bir liste, her parçanın son düğümünün adresleri verilerek sabit zamanda iki dairesel listeye bölünebilir. İşlem, bu iki düğümün bağlantı alanlarının içeriğinin değiştirilmesinden oluşur. Aynı işlemi iki ayrı listedeki herhangi iki düğüme uygulamak, iki listeyi tek bir listede birleştirir. Bu özellik, dört kenar ve yüz kenar gibi bazı algoritmaları ve veri yapılarını büyük ölçüde basitleştirir .

Boş bir dairesel listenin (böyle bir şey mantıklı olduğunda) en basit temsili , listenin düğümü olmadığını gösteren bir boş göstericidir. Bu seçenek olmadan, birçok algoritma bu özel durumu test etmek ve ayrı ayrı ele almak zorundadır. Buna karşılık, boş bir doğrusal listeyi belirtmek için null kullanımı daha doğaldır ve genellikle daha az özel durum oluşturur.

Sentinel düğümleri kullanma

Sentinel düğümü , her öğe için bir sonraki veya önceki düğümlerin var olmasını ve hatta boş listelerin bile en az bir düğüme sahip olmasını sağlayarak belirli liste işlemlerini basitleştirebilir. Bazı liste sonu testlerini ortadan kaldırmak için listenin sonunda uygun bir veri alanı olan bir sentinel düğümü de kullanılabilir. Örneğin, liste, belirli bir değer ile bir düğüm arayan tararken x , için sentinel veri alanını ayarlama x sonu-of-the listesinde döngü içinde testine gereksiz kılar. Başka bir örnek, sıralanmış iki listenin birleştirilmesidir: eğer nöbetçileri +∞ olarak ayarlanmış veri alanlarına sahipse, bir sonraki çıkış düğümünün seçimi, boş listeler için özel işleme ihtiyaç duymaz.

Ancak, nöbetçi düğümler fazladan alan kullanır (özellikle çok sayıda kısa liste kullanan uygulamalarda) ve diğer işlemleri (yeni bir boş liste oluşturma gibi) karmaşık hale getirebilirler.

Bununla birlikte, dairesel liste yalnızca doğrusal bir listeyi simüle etmek için kullanılıyorsa, her listeye son ve ilk veri düğümleri arasına tek bir sentinel düğüm ekleyerek bu karmaşıklığın bir kısmından kaçınılabilir. Bu kuralla, boş bir liste, yalnızca bir sonraki düğüm bağlantısı aracılığıyla kendisine işaret eden nöbetçi düğümden oluşur. Liste tanıtıcısı, liste boş değilse, nöbetçiden önceki son veri düğümüne bir işaretçi olmalıdır; veya liste boşsa nöbetçinin kendisine.

Aynı hile, tek bir sentinel düğümü olan dairesel bir çift bağlantılı listeye dönüştürülerek, çift bağlantılı doğrusal bir listenin işlenmesini basitleştirmek için kullanılabilir. Ancak, bu durumda, tanıtıcı, kukla düğümün kendisine yönelik tek bir işaretçi olmalıdır.

Bağlantılı liste işlemleri

Bağlantılı listeleri yerinde manipüle ederken, önceki atamalarda geçersiz kıldığınız değerleri kullanmamaya özen gösterilmelidir. Bu, bağlantılı liste düğümlerini eklemek veya silmek için algoritmaları biraz incelikli hale getirir. Bu bölüm, yerinde tek, çift ve dairesel olarak bağlantılı listelere düğüm eklemek veya çıkarmak için sözde kod sağlar. Çeşitli şekillerde uygulanabilecek bir liste sonu işaretçisine veya sentinel'e atıfta bulunmak için null kullanacağız .

Doğrusal bağlantılı listeler

Tek başına bağlantılı listeler

Düğüm veri yapımız iki alana sahip olacaktır. Biz de bir değişken tutmak -düğüm her zaman listedeki ilk düğüme işaret, ya da boş boş liste için.

record Node
{
    data; // The data being stored in the node
    Node next // A reference to the next node, null for last node
}

record List
{
    Node firstNode // points to first node of list; null for empty list
}

Tek başına bağlantılı bir listenin geçişi, ilk düğümden başlayarak ve sonuna gelene kadar sonraki her bağlantıyı izleyerek basittir :

node := list.firstNode
while node not null
    (do something with node.data)
    node := node.next

Aşağıdaki kod, tek bağlantılı bir listedeki mevcut bir düğümden sonra bir düğüm ekler. Diyagram nasıl çalıştığını gösterir. Mevcut bir düğümden önce bir düğüm eklemek doğrudan yapılamaz; bunun yerine, bir önceki düğümü takip etmeli ve ondan sonra bir düğüm eklemelidir.

Tek başına bağlantılı bir listeye bir düğüm ekleme şeması

function insertAfter(Node node, Node newNode) // insert newNode after node
    newNode.next := node.next
    node.next    := newNode

Listenin başına eklemek ayrı bir işlev gerektirir. Bu, firstNode'un güncellenmesini gerektirir .

function insertBeginning(List list, Node newNode) // insert node before current first node
    newNode.next   := list.firstNode
    list.firstNode := newNode

Benzer şekilde, belirli bir düğümden sonraki düğümü kaldırmak ve listenin başından bir düğümü kaldırmak için işlevlerimiz vardır . Diyagram öncekini gösteriyor. Belirli bir düğümü bulmak ve kaldırmak için, önceki öğenin tekrar izlenmesi gerekir.

Tek başına bağlantılı bir listeden bir düğümü silme diyagramı

function removeAfter(Node node) // remove node past this one
    obsoleteNode := node.next
    node.next := node.next.next
    destroy obsoleteNode

function removeBeginning(List list) // remove first node
    obsoleteNode := list.firstNode
    list.firstNode := list.firstNode.next // point past deleted node
    destroy obsoleteNode

Dikkat edin removeBeginning()setleri list.firstNodeiçin nulllistedeki son düğümü çıkarılırken.

Geriye doğru yineleme yapamayacağımız için verimli insertBeforeveya removeBeforeişlemler mümkün değildir. Belirli bir düğümden önce bir listeye eklemek, en kötü durumda O(n) çalışma süresine sahip olacak olan listeyi geçmeyi gerektirir.

Kuyruğa bir referans Liste yapısının bir parçası olarak tutulmadıkça, bir bağlantılı listeyi diğerine eklemek verimsiz olabilir, çünkü kuyruğu bulmak için ilk listenin tamamını geçmemiz ve ardından ikinci listeyi buna eklememiz gerekir. Bu nedenle, lineer olarak bağlantılı iki listenin her birinin uzunluğu ise , liste ekleme asimptotik zaman karmaşıklığına sahiptir . Lisp dil ​​ailesinde, liste ekleme prosedürle sağlanır. ${\görüntüleme stili n}$${\görüntüleme stili O(n)}$append

Bağlantılı liste işlemlerinin özel durumlarının çoğu, listenin önüne bir kukla öğe eklenerek ortadan kaldırılabilir. Bu olmasını sağlar orada listenin başında hiçbir özel durumlardır ve hem hale getirdiği insertBeginning()ve removeBeginning()gereksiz. Bu durumda, listedeki ilk yararlı veriler adresinde bulunacaktır . list.firstNode.next

Dairesel bağlantılı liste

Dairesel olarak bağlı bir listede, tüm düğümler boş kullanılmadan sürekli bir daire içinde bağlanır . Önü ve arkası (sıra gibi) olan listeler için, listedeki son düğüme bir referans depolanır. Bir sonraki son düğüme sonra düğüm ilk düğümdür. Öğeler, listenin arkasına eklenebilir ve sabit zamanda önden çıkarılabilir.

Dairesel bağlantılı listeler tek veya çift bağlantılı olabilir.

Döngüsel bağlantılı listelerin her iki türü de herhangi bir düğümden başlayarak tam listeyi geçme yeteneğinden yararlanır. Bu, genellikle firstNode ve lastNode öğelerini depolamaktan kaçınmamıza izin verir , ancak liste boş olabilirse, listedeki bir düğüme işaret eden veya boşsa null olan bir lastNode değişkeni gibi boş liste için özel bir temsile ihtiyacımız olur; burada böyle bir lastNode kullanıyoruz . Bu gösterim, boş olmayan bir listeyle düğüm eklemeyi ve çıkarmayı önemli ölçüde basitleştirir, ancak boş listeler o zaman özel bir durumdur.

algoritmalar

SomeNode öğesinin boş olmayan dairesel tek başına bağlantılı bir listedeki bir düğüm olduğunu varsayarsak , bu kod someNode ile başlayarak bu listeyi yineler :

function iterate(someNode)
    if someNode ≠ null
        node := someNode
    do
        do something with node.value
        node := node.next
    while node ≠ someNode

" while node ≠ someNode" testinin döngünün sonunda olması gerektiğine dikkat edin. Test döngünün başına taşınırsa, listede yalnızca bir düğüm olduğunda prosedür başarısız olur.

Bu işlev, verilen bir "düğüm" düğümünden sonra bir dairesel bağlantılı listeye bir "newNode" düğümü ekler. "Düğüm" boş ise, listenin boş olduğunu varsayar.

function insertAfter(Node node, Node newNode)
    if node = null    // assume list is empty
        newNode.next := newNode
    else
        newNode.next := node.next
        node.next := newNode
    update lastNode variable if necessary

"L"nin dairesel bağlantılı bir listenin son düğümüne işaret eden bir değişken olduğunu varsayalım (veya liste boşsa boş). İçin "newNode" eklemek için sonuna listesinin, tek yapabilir

insertAfter(L, newNode)
L := newNode

Listenin başına "newNode" eklemek için

insertAfter(L, newNode)
if L = null
    L := newNode

Bu işlev, O(1) zamanında verilen bir "düğüm" düğümünden önce bir "newVal" değeri ekler. "Düğüm" ile bir sonraki düğüm arasında yeni bir düğüm oluşturuyoruz ve ardından "node" değerini bu yeni düğüme koyuyoruz ve "node" içine "newVal" koyuyoruz. Böylece, yalnızca bir firstNode değişkeni ile tek başına bağlantılı dairesel olarak bağlantılı bir liste , O(1) zamanında hem öne hem de arkaya eklenebilir.

function insertBefore(Node node, newVal)
    if node = null    // assume list is empty
        newNode := new Node(data:=newVal, next:=newNode)
    else
        newNode := new Node(data:=node.data, next:=node.next)
        node.data := newVal
        node.next := newNode
    update firstNode variable if necessary

Bu işlev, O(1) zamanında 1'den büyük bir listeden boş olmayan bir düğümü kaldırır. Bir sonraki düğümdeki verileri düğüme kopyalar ve ardından düğümün bir sonraki işaretçisini bir sonraki düğümü atlayacak şekilde ayarlar .

function remove(Node node)
    if node ≠ null and size of list > 1
        removedData := node.data
        node.data := node.next.data
        node.next = node.next.next
        return removedData

Düğüm dizilerini kullanan bağlantılı listeler

Herhangi bir başvuru türünü desteklemeyen diller, işaretçileri dizi dizinleriyle değiştirerek yine de bağlantılar oluşturabilir. Yaklaşım tutmaktır dizi ait kayıtların her bir kaydın dizideki bir sonraki (ve muhtemelen önceki) düğümün indeksini belirten tamsayı alanları sahip olduğu,. Dizideki tüm düğümlerin kullanılması gerekmez. Kayıtlar da desteklenmiyorsa, bunun yerine genellikle paralel diziler kullanılabilir.

Örnek olarak, işaretçiler yerine dizileri kullanan aşağıdaki bağlantılı liste kaydını göz önünde bulundurun:

record Entry {
    integer next; // index of next entry in array
    integer prev; // previous entry (if double-linked)
    string name;
    real balance;
}

Bu yapıların bir dizisini ve ilk öğenin dizinini depolamak için bir tamsayı değişkeni oluşturarak bağlantılı bir liste oluşturulabilir.

integer listHead
Entry Records[1000]

Öğeler arasındaki bağlantılar, sonraki (veya önceki) hücrenin dizi indeksinin belirli bir öğe içindeki Sonraki veya Önceki alanına yerleştirilmesiyle oluşturulur. Örneğin:

Yukarıdaki örnekte, ListHeadlistedeki ilk girişin konumu olan 2'ye ayarlanacaktır. 3 ve 5 ile 7 arasındaki girişlerin listenin parçası olmadığına dikkat edin. Bu hücreler, listeye herhangi bir ekleme için kullanılabilir. Bir ListFreetamsayı değişkeni oluşturarak , hangi hücrelerin mevcut olduğunu takip etmek için ücretsiz bir liste oluşturulabilir. Tüm girişler kullanımdaysa, yeni girişlerin listeye kaydedilebilmesi için dizinin boyutunun artırılması veya bazı öğelerin silinmesi gerekir.

Aşağıdaki kod listede gezinir ve adları ve hesap bakiyesini görüntüler:

i := listHead
while i ≥ 0 // loop through the list
    print i, Records[i].name, Records[i].balance // print entry
    i := Records[i].next

Bir seçimle karşı karşıya kalındığında, bu yaklaşımın avantajları şunları içerir:

• Bağlantılı liste yeniden yerleştirilebilir, yani istendiğinde bellekte hareket ettirilebilir ve ayrıca diskte depolama veya bir ağ üzerinden aktarım için hızlı ve doğrudan seri hale getirilebilir .
• Özellikle küçük bir liste için, dizi dizinleri birçok mimaride tam bir işaretçiden önemli ölçüde daha az yer kaplayabilir.
• Düğümleri bellekte bir arada tutarak ve periyodik olarak yeniden düzenleyerek referansın yerelliği geliştirilebilir, ancak bu bir genel mağazada da yapılabilir.
• Naif dinamik bellek ayırıcılar , ayrılan her düğüm için aşırı miktarda ek depolama alanı üretebilir; Bu yaklaşımda düğüm başına neredeyse hiçbir tahsis yükü oluşmaz.
• Önceden tahsis edilmiş bir diziden bir girdiyi ele geçirmek, her düğüm için dinamik bellek tahsisi kullanmaktan daha hızlıdır, çünkü dinamik bellek tahsisi tipik olarak istenen boyutta boş bir bellek bloğu aranmasını gerektirir.

Ancak bu yaklaşımın bir ana dezavantajı vardır: düğümleri için özel bir bellek alanı yaratır ve yönetir. Bu, aşağıdaki sorunlara yol açar:

• Uygulamanın karmaşıklığını artırır.
• Büyük bir diziyi dolduğunda büyütmek zor veya imkansız olabilir, oysa büyük, genel bir bellek havuzunda yeni bir bağlantılı liste düğümü için yer bulmak daha kolay olabilir.
• Dinamik bir diziye eleman eklemek bazen (dolduğunda) beklenmedik bir şekilde sabit zaman yerine doğrusal ( O (n)) alır (yine de amortismana tabi bir sabittir).
• Genel bellek havuzu kullanmak, liste beklenenden küçükse veya çok sayıda düğüm serbest bırakılırsa diğer veriler için daha fazla bellek bırakır.

Bu nedenlerle, bu yaklaşım esas olarak dinamik bellek ayırmayı desteklemeyen diller için kullanılır. Bu dezavantajlar, dizinin oluşturulduğu sırada listenin maksimum boyutu biliniyorsa da azaltılır.

Dil desteği

Lisp ve Scheme gibi birçok programlama dilinde yerleşik olarak tekil bağlantılı listeler bulunur. Birçok işlevsel dilde bu listeler, her biri eksiler veya eksiler hücresi olarak adlandırılan düğümlerden oluşturulur . Eksilerin iki alanı vardır: car , o düğümün verilerine bir referans ve cdr , bir sonraki düğüme referans. Eksi hücreler diğer veri yapılarını oluşturmak için kullanılabilse de, bu onların birincil amacıdır.

Soyut veri türlerini veya şablonlarını destekleyen dillerde , bağlantılı listeler oluşturmak için bağlantılı liste ADT'leri veya şablonları mevcuttur. Diğer dillerde, bağlantılı listeler genellikle kayıtlarla birlikte referanslar kullanılarak oluşturulur .

Dahili ve harici depolama

Bağlantılı bir liste oluştururken, listedeki verileri doğrudan dahili depolama adı verilen bağlantılı liste düğümlerinde depolamak veya yalnızca harici depolama adı verilen verilere bir referans depolamak arasında seçim yapılır . Dahili depolama, verilere erişimi daha verimli hale getirme, genel olarak daha az depolama gerektirme, daha iyi referans yerelliğine sahip olma ve liste için bellek yönetimini basitleştirme (verileri liste düğümleriyle aynı anda tahsis edilir ve serbest bırakılır) avantajına sahiptir .

Öte yandan, harici depolama, daha genel olma avantajına sahiptir, çünkü verinin boyutu ne olursa olsun, bağlantılı bir liste için aynı veri yapısı ve makine kodu kullanılabilir. Aynı verileri birden çok bağlantılı listeye yerleştirmeyi de kolaylaştırır. Dahili depolama ile aynı veriler , düğüm veri yapısına birden çok sonraki referans dahil edilerek birden çok listeye yerleştirilebilse de , her alana dayalı olarak hücre eklemek veya silmek için ayrı rutinler oluşturmak gerekli olacaktır. Harici depolama kullanarak ve ek bağlantılı listelerin hücrelerinin, verileri içeren bağlantılı listenin düğümlerine referansları depolamasını sağlayarak, dahili depolamayı kullanan ek bağlantılı öğe listeleri oluşturmak mümkündür.

Genel olarak, bağlantılı listelere bir dizi veri yapısının dahil edilmesi gerekiyorsa, harici depolama en iyi yaklaşımdır. Bir veri yapısı kümesinin yalnızca bir bağlantılı listeye dahil edilmesi gerekiyorsa, harici depolama kullanan genel bir bağlantılı liste paketi mevcut olmadığı sürece dahili depolama biraz daha iyidir. Benzer şekilde, aynı veri yapısında depolanabilecek farklı veri kümeleri tek bir bağlantılı listeye dahil edilecekse, dahili depolama iyi olur.

Bazı dillerle kullanılabilecek başka bir yaklaşım, farklı veri yapılarına sahip olmayı içerir, ancak tümü , aynı konumdaki sonraki (ve çift ​​bağlantılı listeyse önceki ) referanslar dahil olmak üzere başlangıç ​​alanlarına sahiptir . Her veri türü için ayrı yapılar tanımlandıktan sonra, diğer tüm yapılar tarafından paylaşılan minimum miktarda veriyi içeren ve yapıların başında (başlangıçta) yer alan genel bir yapı tanımlanabilir. Ardından, bağlantılı liste tipi işlemleri gerçekleştirmek için minimum yapıyı kullanan genel rutinler oluşturulabilir, ancak daha sonra ayrı rutinler belirli verileri işleyebilir. Bu yaklaşım, genellikle birkaç tür mesajın alındığı, ancak hepsinin aynı alan kümesiyle başladığı, genellikle mesaj türü için bir alan içeren mesaj ayrıştırma rutinlerinde kullanılır. Genel rutinler, alındığında bir kuyruğa yeni mesajlar eklemek ve mesajı işlemek için bunları kuyruktan çıkarmak için kullanılır. Mesaj tipi alanı daha sonra belirli mesaj tipini işlemek için doğru rutini çağırmak için kullanılır.

Dahili ve harici depolama örneği

Ailelerin ve üyelerinin bağlantılı bir listesini oluşturmak istediğinizi varsayalım. Dahili depolamayı kullanarak yapı aşağıdaki gibi görünebilir:

record member { // member of a family
    member next;
    string firstName;
    integer age;
}
record family { // the family itself
    family next;
    string lastName;
    string address;
    member members // head of list of members of this family
}

Dahili depolamayı kullanan ailelerin ve üyelerinin tam listesini yazdırmak için şunu yazabiliriz:

aFamily := Families // start at head of families list
while aFamily ≠ null // loop through list of families
    print information about family
    aMember := aFamily.members // get head of list of this family's members
    while aMember ≠ null // loop through list of members
        print information about member
        aMember := aMember.next
    aFamily := aFamily.next

Harici depolama kullanarak aşağıdaki yapıları oluştururuz:

record node { // generic link structure
    node next;
    pointer data // generic pointer for data at node
}
record member { // structure for family member
    string firstName;
    integer age
}
record family { // structure for family
    string lastName;
    string address;
    node members // head of list of members of this family
}

Harici depolama kullanan ailelerin ve üyelerinin tam listesini yazdırmak için şunu yazabiliriz:

famNode := Families // start at head of families list
while famNode ≠ null // loop through list of families
    aFamily := (family) famNode.data // extract family from node
    print information about family
    memNode := aFamily.members // get list of family members
    while memNode ≠ null // loop through list of members
        aMember := (member)memNode.data // extract member from node
        print information about member
        memNode := memNode.next
    famNode := famNode.next

Harici depolama kullanırken, kaydı düğümden çıkarmak ve uygun veri türüne dönüştürmek için fazladan bir adımın gerekli olduğuna dikkat edin. Bunun nedeni, hem aile listesinin hem de aile içindeki üye listesinin aynı veri yapısını ( düğüm ) kullanan iki bağlantılı listede saklanması ve bu dilin parametrik türleri olmamasıdır.

Derleme zamanında bir üyenin ait olabileceği aile sayısı bilindiği sürece dahili depolama sorunsuz çalışır. Bununla birlikte, bir üyenin, belirli sayı yalnızca çalışma zamanında bilinen, rastgele sayıda aileye dahil edilmesi gerekiyorsa, harici depolama gerekli olacaktır.

Aramayı hızlandırmak

Bağlı bir listede belirli bir öğeyi bulmak, sıralanmış olsa bile normalde O( n ) zaman gerektirir ( doğrusal arama ). Bu, bağlantılı listelerin diğer veri yapılarına göre birincil dezavantajlarından biridir. Yukarıda tartışılan değişkenlere ek olarak, aşağıda arama süresini iyileştirmenin iki basit yolu bulunmaktadır.

Sırasız bir listede, ortalama arama süresini azaltmak için basit bir buluşsal yöntem , bir öğeyi bulunduğunda basitçe listenin başına taşıyan öne doğru hareket buluşsal yöntemidir . Basit önbellekler oluşturmak için kullanışlı olan bu şema, en son kullanılan öğelerin yeniden bulunmasının en hızlı olmasını sağlar.

Diğer bir yaygın yaklaşım, daha verimli bir dış veri yapısı kullanarak bağlantılı bir listeyi " indekslemek "tir. Örneğin , öğeleri bağlantılı liste düğümlerine referans olan kırmızı-siyah bir ağaç veya karma tablo oluşturulabilir . Tek bir listede bu tür birden çok dizin oluşturulabilir. Dezavantajı, bu dizinlerin bir düğüm her eklendiğinde veya çıkarıldığında (veya en azından bu dizin yeniden kullanılmadan önce) güncellenmesi gerekebilmesidir.

Rastgele erişim listeleri

Bir rasgele erişimli listesi okumak veya listesinde herhangi bir elemanın yeniden düzenlenmesi hızlı rastgele erişim için destek ile bir liste bulunmaktadır. Olası bir uygulama, özel özelliklere sahip ağaçların bir listesini içeren çarpık ikili sayı sistemini kullanan bir çarpık ikili rasgele erişim listesidir ; bu, en kötü durum sabit zamanlı kafa/eksi işlemlerine ve en kötü durum logaritmik zamanına göre bir öğeye indekse göre rastgele erişime izin verir. Rastgele erişim listeleri, kalıcı veri yapıları olarak uygulanabilir .

Rastgele erişim listeleri, aynı O(1) baş ve kuyruk işlemlerini aynı şekilde destekledikleri için değişmez bağlantılı listeler olarak görüntülenebilir.

Rastgele erişim listelerinin basit bir uzantısı , sabit zamanda (mutasyon karmaşıklıkları olmadan) tüm listedeki minimum öğeyi veren ek bir işlem sağlayan min- list'tir.

İlgili veri yapıları

Hem yığınlar hem de kuyruklar genellikle bağlantılı listeler kullanılarak uygulanır ve yalnızca desteklenen işlem türlerini kısıtlar.

Atlama listesi hızla elemanlarının çok sayıda üstünden atlayarak ve ardından bir sonraki katmana inen için işaretçiler katmanlarıyla artar bağlantılı listesidir. Bu işlem, asıl liste olan alt katmana kadar devam eder.

Bir ikili ağaç elemanları kendilerini aynı nitelikteki listeleri bağlantılı olan bağlantılı listenin bir türü olarak görülebilir. Sonuç olarak, her düğüm, içerikleriyle birlikte o düğümün altındaki alt ağaçları oluşturan bir veya iki diğer bağlantılı listenin ilk düğümüne bir referans içerebilir.

Bir rulo yapılmaz bağlantılı liste her bir düğüm verisi değerlerinin bir dizisini içeren bir bağlantılı listesidir. Bu , daha fazla liste öğesi bellekte bitişik olduğundan ve listenin her bir öğesi için daha az meta verinin depolanması gerektiğinden, bellek yükünü azalttığı için geliştirilmiş önbellek performansına yol açar .

Bir hash tablosu , hash tablosunda aynı konuma hash olan öğelerin zincirlerini depolamak için bağlantılı listeleri kullanabilir.

Bir yığın , bağlantılı bir listenin bazı sıralama özelliklerini paylaşır, ancak neredeyse her zaman bir dizi kullanılarak uygulanır. Düğümden düğüme referanslar yerine, sonraki ve önceki veri indeksleri, mevcut veri indeksi kullanılarak hesaplanır.

Bir kendinden organize liste listesinin başında sık erişilen düğümleri tutarak veri alımı için kez arama azaltır bazı sezgisel dayalı düğümleri yeniden düzenler.

Notlar

Referanslar

daha fazla okuma

• Juan, Melek (2006). "Bölüm 20 –Veri Yapıları; ID06 - JAVA ile PROGRAMLAMA ('Big Java' kitabının slayt kısmı, CayS. Horstmann)" (PDF) . P. 3. Orijinalinden (PDF) 2012-01-06 tarihinde arşivlendi . 2011-07-10 alındı .
• Siyah, Paul E. (2004-08-16). Pieterse, Vreda; Siyah, Paul E. (ed.). "bağlantılı liste" . Algoritmalar ve Veri Yapıları Sözlüğü . Ulusal Standartlar ve Teknoloji Enstitüsü . 2004-12-14 alındı .
• Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). C/C++ Kullanan Pratik Veri Yapıları . Prentice-Hall. s.  165–190 . ISBN'si 0-13-280843-9.
• Collins, William J. (2005) [2002]. Veri Yapıları ve Java Koleksiyonları Çerçevesi . New York: McGraw Tepesi. s. 239–303. ISBN'si 0-07-282379-8.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. ; Stein, Clifford (2003). Algoritmalara Giriş . MİT Basın. s. 205–213, 501–505. ISBN'si 0-262-03293-7.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. ; Stein, Clifford (2001). "10.2: Bağlantılı listeler". Algoritmalara Giriş (2. baskı). MİT Basın. s. 204-209. ISBN'si 0-262-03293-7.
• Green, Bert F., Jr. (1961). "Sembol Manipülasyonu için Bilgisayar Dilleri". Elektronikte İnsan Faktörleri Üzerine IRE İşlemleri (2): 3–8. doi : 10.1109/THFE2.1961.4503292 .
• McCarthy, John (1960). "Sembolik İfadelerin Özyinelemeli İşlevleri ve Makine Tarafından Hesaplanması, Bölüm I" . ACM'nin İletişimi . 3 (4): 184. doi : 10.1145/367177.367199 .
• Knuth, Donald (1997). "2.2.3-2.2.5". Temel Algoritmalar (3. baskı). Addison-Wesley. s. 254–298. ISBN'si 0-201-89683-4.
• Newell, Allen ; Shaw, FC (1957). "Mantık Teorisi Makinesi Programlama". Batı Ortak Bilgisayar Konferansı Tutanakları : 230–240.
• Parlante, Nick (2001). "Bağlı liste temelleri" (PDF) . Stanford Üniversitesi . 2009-09-21 alındı .
• Sedgewick, Robert (1998). C algoritmaları . Addison Wesley. s.  90–109 . ISBN'si 0-201-31452-5.
• Shaffer, Clifford A. (1998). Veri Yapılarına ve Algoritma Analizine Pratik Bir Giriş . New Jersey: Prentice Salonu. s. 77–102. ISBN'si 0-13-660911-2.
• Wilkes, Maurice Vincent (1964). "Basit Liste İşleme Dili için Kendi Kendini Derleyen Derleyici ile Bir Deney". Otomatik Programlamada Yıllık Gözden Geçirme . Bergama Basın. 4 (1): 1. doi : 10.1016/0066-4138(64)90013-8 .
• Wilkes, Maurice Vincent (1964). "Listeler ve Neden Yararlıdırlar". ACM Ulusal Konferansı Gelirleri, Philadelphia 1964 . ACM (P–64): F1–1.
• Shanmugasundaram, Kulesh (2005-04-04). "Linux Çekirdeği Bağlantılı Listesi Açıklaması" . 2009-09-21 alındı .

Dış bağlantılar

• Açıklama gelen Algoritmalar ve Veri Yapıları Sözlük
• Bağlantılı Listelere Giriş , Stanford Üniversitesi Bilgisayar Bilimleri Kütüphanesi
• Bağlantılı Liste Problemleri , Stanford Üniversitesi Bilgisayar Bilimleri Kütüphanesi
• Açık Veri Yapıları - Bölüm 3 - Bağlantılı Listeler , Pat Morin
• Aynı anda birkaç bağlantılı listede bulunan düğümlere sahip olma fikri için patent (bu tekniğin, patent verilmeden önce onlarca yıldır yaygın olarak kullanıldığını unutmayın)