[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.