Dołączanie elementu na końcu listy w Scali

223

Brzmi jak głupie pytanie, ale wszystko, co znalazłem w Internecie, to śmieci. Po prostu nie mogę dodać elementu typu Tdo listy List[T]. Próbowałem z, myList ::= myElementale wydaje się, że tworzy dziwny obiekt, a dostęp do myList.lastzawsze zwraca pierwszy element, który został umieszczony na liście.

arrays scala

— Masiar
źródło

394

List(1,2,3) :+ 4

Results in List[Int] = List(1, 2, 3, 4)

Zauważ, że ta operacja ma złożoność O (n). Jeśli potrzebujesz tej operacji często lub w przypadku długich list, rozważ użycie innego typu danych (np. ListBuffer).

— Landei
źródło

7

Nie ma O (2 * n), stałe czynniki są ignorowane dla asymptotycznych złożoności. Myślę, że Listjest konwertowany na a ListBuffer, element jest dołączany, a ListBufferkonwertowany z powrotem (prawie jak Stringi StringBuilderw Javie), ale to tylko przypuszczenie.

— Landei

2

Jest to O (n), ponieważ musisz przejść całą listę, aby dotrzeć do wskaźnika ostatniego elementu i móc dołączyć element, który wskazuje na niego wskaźnik ostatniego elementu.

— pisaruk,

39

@pisaruk, gdyby tak było, można po prostu utrzymać wskaźnik do głowy i ogona. Jednak lista w scali jest niezmienna, co oznacza, że aby „zmodyfikować” ostatni element listy, należy najpierw wykonać jej kopię. Jest to kopia, którą jest O (n) - nie przejście przez samą listę.

2

Wierzę, że to O (n) po prostu dlatego, że tworzy zupełnie nową listę

— Raffaele Rossi

3

Operator wad ma złożoność O (1), ponieważ działa po „zamierzonej” stronie listy.

— Landei,

67

To dlatego, że nie powinieneś tego robić (przynajmniej z niezmienną listą). Jeśli naprawdę potrzebujesz dołączyć element na końcu struktury danych, a ta struktura danych naprawdę musi być listą, a ta lista naprawdę musi być niezmienna, wykonaj następujące czynności:

(4 :: List(1,2,3).reverse).reverse

albo to:

List(1,2,3) ::: List(4)

— agilesteel
źródło

Wielkie dzięki! Właśnie tego szukałem. Wydaje mi się, że z twojej odpowiedzi nie powinienem tego robić ... Zrewiduję swoją strukturę i zobaczę, co mogę zrobić. Dzięki jeszcze raz.

— Masiar

6

@Masiar użyj Vectora, jeśli chcesz niezmienność i wydajne dołączanie. Zobacz sekcję charakterystyki wydajności w scala-lang.org/docu/files/collections-api/collections.html

— Arjan Blokzijl,

29

„Zbuduj listę, dodając ją, a następnie odwróć” jest użytecznym wzorcem, jeśli masz wiele elementów do dodania, ale nie sądzę, że dobrym pomysłem jest zastosowanie go tak jak w przypadku dodawania jednego elementu do istniejąca lista. Sztuczka polegająca na „podwójnym odwróceniu” odbudowuje listę dwa razy, a :+choć może być nieefektywna, odbudowuje ją tylko raz.

— Nicolas Payette,

25

Listy w Scali nie są zaprojektowane do modyfikacji. W rzeczywistości nie można dodawać elementów do Scali List; to niezmienna struktura danych , jak ciąg Java. To, co faktycznie robisz, gdy „dodajesz element do listy” w Scali, to tworzenie nowej listy z istniejącej listy . (Źródło)

Zamiast korzystać z list dla takich przypadków użycia, proponuję albo użyć ArrayBufferalbo ListBuffer. Te struktury danych zostały zaprojektowane tak, aby dodawać nowe elementy.

Na koniec, po zakończeniu wszystkich operacji, bufor można przekształcić w listę. Zobacz następujący przykład REPL:

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer

scala> var fruits = new ListBuffer[String]()
fruits: scala.collection.mutable.ListBuffer[String] = ListBuffer()

scala> fruits += "Apple"
res0: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple)

scala> fruits += "Banana"
res1: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple, Banana)

scala> fruits += "Orange"
res2: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple, Banana, Orange)

scala> val fruitsList = fruits.toList
fruitsList: List[String] = List(Apple, Banana, Orange)

— Markus Weninger
źródło

3

Jest to podobne do jednej z odpowiedzi, ale w inny sposób:

scala> val x=List(1,2,3)
x: List[Int] = List(1, 2, 3)

scala> val y=x:::4::Nil
y: List[Int] = List(1, 2, 3, 4)

— Venkat
źródło

2

Możemy dołączyć lub dodać dwie listy lub dołączyć listę i tablicę
:

var l = List(1,2,3)    
l=l:+4 
Result : 1 2 3 4  
var ar = Array(4,5,6)    
for(x<-ar)    
{ l=l:+x}  
  l.foreach(println)

Result:1 2 3 4 5 6

Przygotowywanie:

var l = List[Int]()  
   for(x<-ar)  
    { l=x::l } //prepending    
     l.foreach(println)   

Result:6 5 4 1 2 3

— Ramesh Muthavarapu
źródło

1

Tak, możemy, ale byłby to zły pomysł z wszystkich powodów wymienionych w innych odpowiedziach.

— jwvh