>> [MÜZİK OYUN]
Doug LLOYD: Pekala.
Yani sadece bitmiş ise tek başına bağlantılı listelerde üzgünüm video
Ben seni bıraktığınız Bir çekişme biraz.
Ama bitirmek için buradayız sevindim çift-bağlantılı listeler hikayesi.
>> Eğer gelen çağırmak Yani eğer Bu video konuştuk
tek başına bağlantılı nasıl Listeler yeteneğimizi katılmak do
bilgi ile başa çıkmak için nerede elemanların sayısı
veya öğe sayısı içinde Bir liste büyüyebilir veya küçültmek olabilir.
Biz şimdi başa çıkabilirim Böyle bir şey nerede
Biz dizilerle onunla anlaşma olamazdı.
>> Ama birinden muzdarip yapmak Kritik sınırlama hangi
Bir tek başına bağlanmış olduğu sahip Liste, biz sadece şimdiye kadar taşıyabilirsiniz
listesi üzerinden tek bir yönde.
Ve tek gerçek durum nerede bir sorun haline gelebilir
iken biz çalışıyorlardı Tek bir öğeyi silmek.
Ve biz bile bunu nasıl tartışmak değil pseudocode bir tek başına bağlantılı listesinde.
Bu kesinlikle yapılabilir ama o bir güçlük biraz olabilir.
Eğer kendinizi bulmak Yani eğer nerede bir durumda
Silmek için çalışıyoruz Listeden tek elemanlar
veya gerekli gidiyor Eğer silme olacağım
dan tek elemanlar listesinde, isteyebilirsiniz
kullanmayı düşünün bir çift-bağlantılı yerine tek başına bağlantılı listenin listesi.
Çift-bağlı listeler yapmanızı sağlar, çünkü ileriye ve geriye doğru hareket etmek hem de
yerine listesi üzerinden Sadece ileri list-- yoluyla
Sadece bir ekstra eleman ekleyerek Bizim yapısı tanımına
çift-bağlantılı liste düğüm için.
>> Yine, gitmiyorsun eğer Tek elemanları silme olabilir
list-- biz ekliyoruz çünkü Bizim yapısına ekstra alan
tanımı, düğümler kendileri çift-bağlantılı listeler için
Daha büyük olacak.
Onlar almaya gidiyoruz fazla bellek bayt kadar.
Ve eğer öyleyse bu bir şey değil Eğer, yapmanız gereken gidiyoruz
Eğer karar verebilirsiniz off değmez ticaret
Ekstra harcamak zorunda bellek bayt gerekmektedir
Bir çift-bağlantılı liste için sen değilsen gidiş tek elemanları silme için.
Ama aynı zamanda iyisin Çok başka şeyler için.
>> Dediğim gibi Yani, biz sadece eklemek zorunda Bizim yapıya tek bir alan
Bu kavramı definition-- Bir önceki işaretçi.
Bir tek başına bağlantılı listede Yani, biz , değer ve sonraki işaretçisi var
yani çift-bağlantılı liste sadece var Bir yol da geriye doğru hareket etmek.
>> Şimdi tek tek bağlantılı olarak Liste, video, konuştuk
Bunlarla ilgili beş vardır Eğer olması gerekiyor temel şeyler
mümkün bağlantılı listeler ile çalışmak için yapmak.
Ve bunların çoğu, aslında Bir çift-bağlantılı liste olduğunu
Gerçekten büyük bir sıçrama değildir.
Biz hala sadece tarafından arama yapabilirsiniz baştan ileri hareket sonuna kadar.
Biz hala dışarı bir düğüm oluşturabilir İnce hava, hemen hemen aynı şekilde.
Biz güzel listelerini silebilirsiniz Çok fazla aynı şekilde.
Tek şey bu , kurnazca farklı
Gerçekten, eklediğiniz listeye yeni düğümler,
ve nihayet silme bahsedeceğiz yanı sıra listeden tek bir unsur.
Yine, hemen hemen Diğer üç we '
Onlar hakkında konuşmak için gitmiyorum Şu anda onlar sadece çünkü
fikirler çok küçük tweaks tartışıldı tek başına bağlantılı liste video.
>> Yani yeni bir düğüm eklemek izin Bir çift-bağlantılı liste halinde.
Biz bunu konuştuk yanı listeleri tek başına bağlantılı,
ancak ekstra bir çift var çift-bağlantılı listeler ile yakalar.
Biz [misin? geçen?] kafasında Burada listelenecek ve bazı keyfi değer,
ve biz yeni başkanı almak istiyorum Bu işlevin dışında listesinin.
Bir dllnode yıldız döndürür nedeni budur.
Peki adımlar nelerdir?
Yine, çok benzer listeleri tek başına bağlantılı etmek
bir ilave ilavesi ile.
Biz yeni bir alanı ayırır istiyorum düğüm ve çek geçerli olduğundan emin olmak için.
Biz bu düğümü doldurmak istiyorum her türlü bilgi ile biz
bunu koymak istiyorum.
Son şey, biz sanıyor- gerekiyor Yapmamız gereken ekstra bir şey, rather--
Önceki işaretçi düzeltmek için Listenin eski kafa.
Unutmayın, çünkü iki kat bağlantılı listeler,
biz ileriye taşıyabilirsiniz ve backwards-- hangi
Her düğüm aslında işaret anlamına gelir diğer iki düğümlerin yerine sadece biri.
Ve böylece biz düzeltilmesi gereken Listenin eski başkanı
yeni başkanı geriye işaret bir şeydi bağlantılı liste,
Daha önce yapmak zorunda değildi.
Ve daha önce olduğu gibi, biz sadece geri dönmek Listenin yeni başkanı işaretçisi.
>> Yani burada bir liste.
Biz bu listeye 12 eklemek istiyorum.
Şeması dikkat edin biraz farklıdır.
Her bir düğüm üç fields-- içeriyor Veri ve kırmızı bir sonraki işaretçi,
ve mavi bir önceki işaretçi.
Hiçbir şey, 15 düğümden önce gelir bu yüzden onun Önceki işaretçi null olur.
Bu listenin başında bulunuyor.
Daha önce bir şey yok.
Ve hiçbir şey, 10 düğümden sonra gelir ve bu nedenle sonraki gösterici de null var.
>> Yani bu listeye 12 ekleyelim.
Biz düğüm için [duyulamaz] alanı gerekiyor.
Biz bunu 12 içini koydu.
Ve sonra tekrar, gerçekten olması gerekir Dikkatli zinciri kırmak için değil.
Biz yeniden düzenlemek istiyoruz Doğru sırayla işaretçileri.
Ve bazen bu yani-- olabilir biz özellikle göreceğimiz gibi
delete-- ile bazı var olduğunu gereksiz işaretçileri, ama bu sorun değil.
>> Bu yüzden ilk ne istiyorsun?
Ben tavsiye ederim şeyler muhtemelen gerekir
do 12 işaretçileri doldurmak için vardır düğüm başka kimse dokunmadan önce.
Peki 12 sonraki işaret olacak?
15.
Ne 12 önce gelir?
Hiçbir şey.
Şimdi dolu ettik 12 ekstra bilgiler
bu nedenle Önceki, Sonraki ve değeri vardır.
>> Şimdi olabilir 15'de-- bu ekstra Biz biz about-- konuşuyorduk adım
Geri 12 15 noktası olabilir.
Ve şimdi biz baş taşıyabilirsiniz bağlantılı liste de 12 olmak.
Bu yüzden oldukça benzer ne tek başına bağlantılı listeleri ile yaptıklarını,
ekstra adımı dışında Listenin, eski kafa bağlayan
Listenin yeni başkanı geri.
>> Şimdi nihayet silmenize izin Bağlantılı listeden bir düğüm.
Yani biz diyelim diğer bazı işlev o
Biz Silmek istediğiniz bir düğüm bulma ve tam bize bir işaretçi verdi
Biz Silmek istediğiniz düğüm.
Biz bile demek need-- yok Kafa hala küresel ilan edilir.
Burada baş ihtiyacımız yok.
Bütün bu fonksiyon yapıyor biz ettik olduğu tam düğüm biz bir işaretçi bulundu
kurtulmak istiyorum.
En ondan kurtulmak edelim.
Bu bir çok daha kolay listeleri çift-bağlantılı.
Bu aslında birinci-- Sadece bir kaç şey.
Biz sadece çevredeki düzeltmek gerekir düğümlerin göstericiler onlar üzerinden atlamak böylece
düğüm biz silmek istiyorum.
Ve sonra biz bu düğümü silebilirsiniz.
Yani yine, biz sadece buradan gidiyoruz.
Görünüşe göre karar verdik Biz düğüm X silmek istediğiniz
Ve yine, ne olduğumu yol-- tarafından var-- yapıyor
Bir genel bir durumdur ortasında düğüm.
Bir çift vardır Ekstra uyarılar olduğunu sen
Eğer silme yaparken dikkate almak gerekir Listenin başından
veya listenin çok uç.
Özel bir çift var Köşe durumlar ile başa çıkmak için.
>> Yani bu herhangi bir düğüm silme için çalışır list-- birinin ortasında olduğu
ileri meşru işaretçi vardır ve geriye meşru bir işaretçi,
meşru Önceki ve sonraki işaretçi.
Yine, çalışıyorsanız uçları, sen
Bu işlemek gerekir biraz farklı,
ve biz gitmiyoruz Şimdi bu konuda konuşmak.
Ama muhtemelen can neye ihtiyacı olduğunu anlamaya
Bu videoyu izleyerek sadece yapılacak.
>> Yani biz izole ettik X X düğüm Biz listeden silmek istiyorum.
Biz ne yaptık?
İlk olarak, biz yeniden gerekir dış işaretçileri.
Biz yeniden gerekir 9 sonraki 13 üzerinden atlamak için
ve nokta 10-- hangi biz sadece ne yaptık olduğunu.
Ve biz de gereken 10 en Önceki yeniden
Bunun yerine 13'e işaret 9'a işaret etmek.
>> Yani yine, bu oldu ile başlayan diyagram.
Bu bizim zinciri oldu.
Biz, 13 üzerinden atlamak gerekiyor ama aynı zamanda korumak için mi
Listenin bütünlüğü.
Biz herhangi bir kaybetmek istemiyoruz her iki yönde bilgiler.
Bu yüzden yeniden gerekir işaretçileri dikkatlice
bu yüzden biz hiç zincir kırmak istemem.
>> Yani biz 9'un sonraki işaretçi söyleyebiliriz aynı yere işaret
on üç Next pointer hemen işaret ediyor.
Biz sonunda Çünkü 13 üzerinden atlamak istiyorum olacak.
Yani her yerde 13 puan gelecek, sizi Dokuz Orada yerine işaret etmek istiyorum.
Yani bu.
Ve sonra her yerde 13 puan geri için, 13 öncesi gelirse,
Biz işaret etmek istiyorum 10 Bu yerine 13.
Eğer takip ederseniz Şimdi fark oklar, biz 13 bırakabilirsiniz
Aslında herhangi bir bilgi kaybetmeden.
Biz, listenin bütünlüğünü muhafaza ettik ileri ve geri hareketli hem.
Ve sonra biz sadece sıralama can biraz o kadar temiz
Birlikte liste çekerek.
Yani biz düzenlenmeyecek iki tarafında işaretçileri.
Ve sonra biz X serbest 13 ihtiva düğüm
ve biz zinciri kırmadım.
Yani biz iyi yaptı.
>> Burada bağlantılı listeler Final notu.
Böylece singly- hem de çift bağlı listeleri, biz gördüğümüz gibi,
destek gerçekten verimli ekleme ve elemanların silinmesi.
Hemen hemen yapabilirsiniz sürekli zaman içinde.
Ne silmek için yapmanız gereken yaptım bir eleman önce sadece ikinci?
Biz bir işaretçi taşındı.
Biz başka bir işaretçi taşındı.
Biz X-- üç operasyonları aldı kurtardı.
Her zaman üç operasyonları alır Bir düğüm boşaltmak için bu node-- silin.
>> Nasıl eklerim?
Peki, biz sadece zaman konum Başlangıçta üzerinde teyel
biz verimli takarken eğer.
Yani biz rearrange-- gerekiyor o ise bağlı
Bir singly- veya çift bağlı Liste, biz üç yapmanız gerekebilir
ya da dört operasyon maks.
Fakat yine de, her zaman üç ya da dört var.
Bu kaç önemli değil elementler, bizim listesinde bulunan
her zaman üç ya da dört operations-- var: sadece silme her zaman gibi
Üç ya da dört işlem.
Bu sabit zamanı.
Yani bu gerçekten harika.
>> Diziler, biz yapıyorduk Ekleme tür gibi bir şey.
Muhtemelen bu ekleme hatırlamak Sıralama sabit bir zaman algoritma değil.
Aslında oldukça pahalı.
Yani bu sokulması için çok daha iyidir.
Ama belirtildiği gibi Liste videoyu tek başına bağlantılı,
Burada bir dezavantajı var, çok doğru değil mi?
Biz yeteneğini kaybettik rastgele unsurları erişebilirsiniz.
Biz eleman sayısını dört istiyorum diyemem Bağlantılı bir listenin veya eleman sayısı 10
Aynı şekilde biz bir dizi ile bunu
ya da biz sadece doğrudan endeksi can Bizim dizinin elemanı içine.
>> Ve böylece bir bulmaya çalışıyor Bağlantılı bir list-- elemanı
arama important-- ise Şimdi lineer zaman alabilir.
Liste uzadıkça, bu ek bir adım alabilir
Listedeki her elemanı için Sipariş biz aradığınızı bulmak için.
Yani ticaret finaller var.
Yanlısı biraz var Burada ve aleyhte öğesi.
>> Ve çift-bağlı listeler değildir Veri yapısı kombinasyonunun son tür
biz hakkında konuşmak edeceğiz tüm temel alarak binayı
C blokları bir araya koyarak.
Aslında, biz çünkü Hatta bundan daha iyisini
Bir veri yapısını oluşturmak için bu Eğer arama mümkün olabilir
sabit zamanda çok.
Ama başka bir videoda bu konuda daha fazla.
>> Ben Doug Lloyd değilim.
Bu CS50 olduğunu.