LinkedList için durum kullan

Question

Bu yayın yalnızca scala.collection.mutable.LinkedList öğelerini açıklar. Diğer uygulamalar bu iş parçacığının konusu değildir.

Sorum şu: Bu sınıfın kullanım durumu nedir? Ben hiçbirinin yararı sağlamazken hem değişebilir hem de değişmez yapıların problemlerine sahip olduğunu düşünüyorum. Çünkü söylemek: bir değişmez API (filter, map, drop, take vb tüm yerinde değişiklikler yeni LinkedList dönmek yerine yapıyor)

sanki

• API bana bakıyor bütün değişmez bağlantılı listenin faydaları o var elem ve var next yoluyla (hala değişken olduğundan en azından ben, yani yapılar arasındaki maksimum paylaşımı, mevcut olmadığı tahmin vardır.

yani temelde biz doğrusal bir erişim zaman var, doğrusal ap pend zamanı, doğrusal boşluk vb. ve uzay karmaşıklığı veya kod hakkında akıl yürütme yeteneği için gösterilecek hiçbir şey (belki de O (1) eklemeye devam etse de yine de değişmez listelerin olduğu durum).

Bu tür bir yapının önemli bir faydasını göremiyorum? Bu sınıfa uygulanabilen nesnel önlemler ve/veya kullanım vakaları arıyorum.

Answer 1

Bunun nedeni karmaşıklık olduğunu söyleyebilirim - bağlantılı liste sınıfı listenin ortasındaki bir düğüme başvuruda bulunmanıza izin verir ve o düğümün başına geçmek yerine, o düğümde insert veya update kullanın. liste. Bazı dizide bir değişiklik (yukarıdaki myReference) olur tam olarak nerede bir uygulamada

[] --> [] --> ... --> [] --> ... --> [] --| 
^     ^
head     myReference 

, ( immutable.List ile durum olurdu bu konuma her şeyi kopyalamak yerine bu konumu değiştirmek için çok daha az maliyeti yani myReference'dan sonra yeni bir düğüm ekliyorum.

       myNewNode 
          v 
[] --> [] --> ... --> [] --> [] ---> ... --> [] --| 
^     ^
head     myReference 

böyle bir uygulamanın bir örneği - Bir dize bölümlerini genişletmek bir L-system. Yeni düğümlerin yerinde eklenmesi çok daha ucuzdur, çünkü genişletilmesi gereken her zaman tüm dizeyi kopyalamaktır.

diğer nedeni tamamlanmasının - extra LinkedList sınıf standart kütüphane boyutuna düşük maliyetle geldi sağlayan ortak altyapı DoubleLinkedList ve LinkedListLike pay beri bir sürü.