목록에 추가하는 것이 왜 나쁜가요?

목록에 추가하는 것이 왜 나쁜가요?

---

저는 최근에 스칼라를 배우기 시작했고 ::목록 앞에 추가되는 (단점) 기능을 발견했습니다.
"Programming in Scala"라는 책에서 목록에 추가하는 것은 성능이 o (n)이고 prepending은 성능이 o (1)이기 때문에 추가 기능이 없다고 말합니다.

그 진술에 대해 뭔가 잘못되었습니다.

성능이 구현에 의존하지 않습니까? 순방향 및 역방향 링크로 목록을 구현하고 첫 번째와 마지막 요소를 컨테이너에 저장하는 것이 가능하지 않습니까?

두 번째 질문은 1,2,3과 같이 목록이 있고 그 끝에 4를 더하고 싶을 때 무엇을해야 하는가입니다.

---

핵심은 x :: somelist변경하지 않고 somelist대신 x 다음에의 모든 요소를 ​​포함하는 새 목록을 생성한다는 것입니다 somelist. 새로 생성 된 단일 연결 목록에서 somelist후속 작업 으로 설정 하기 만하면 되기 때문에 O (1) 시간에 수행 할 수 있습니다 x.

이중 연결 목록을 대신 사용 x하는 경우을 somelist수정하는의 머리 의 선행자로 설정해야 합니다 somelist. 따라서 ::원래 목록을 수정하지 않고 O (1)에서 할 수 있도록하려면 단일 연결 목록 만 사용할 수 있습니다.

두 번째 질문과 관련하여 : :::단일 요소 목록을 목록 끝에 연결하는 데 사용할 수 있습니다 . 이것은 O (n) 연산입니다.

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

---

다른 답변은이 현상에 대한 좋은 설명을 제공했습니다. 서브 루틴의 목록에 많은 항목을 추가하거나 요소를 추가하여 목록을 만드는 경우 기능적 관용어는 목록을 역순 으로 작성하여 목록 의 맨 앞에 있는 항목을 고려하는 것 입니다. 끝에서 뒤집습니다. 이것은 O (n²) 대신 O (n) 성능을 제공합니다.

---

질문이 방금 업데이트되었으므로 여기서 상황이 변경되었음을 주목할 가치가 있습니다.

오늘날의 Scala에서는 xs :+ x순차 컬렉션 끝에 항목을 추가하는 데 간단히 사용할 수 있습니다 . (도 있습니다 x +: xs씁니다. 스칼라의 2.8 이상 수집 작업의 많은 연상 기호는 점이다 COL 에이 옆에 간다 COL의 성귀.)

이 O (것 N을 기본 연결 구현) List또는 Seq, 그러나 당신이 사용하는 경우 Vector또는 IndexedSeq,이 효과적으로 일정 시간이 될 것입니다. Scala Vector는 아마도 Scala의 가장 유용한 목록 형 컬렉션 Vector일 것입니다. 오늘날 대부분 쓸모없는 Java와는 다릅니다 .

Scala 2.8 이상에서 작업하는 경우 컬렉션 소개 는 반드시 읽어야합니다.

---

두 가지 작업 만 필요하므로 Prepending이 더 빠릅니다.

1. 새 목록 노드 만들기
2. 새 노드가 기존 목록을 가리 키도록합니다.

추가 작업은 헤드에 대한 포인터 만 있으므로 목록 끝으로 이동해야하므로 더 많은 작업이 필요합니다.

전에 Scala에서 프로그래밍 한 적이 없지만 List Buffer를 사용해 볼 수 있습니다.

---

대부분의 기능 언어는 편리한 불변 컬렉션 유형이므로 단일 링크 목록 데이터 구조를 두드러지게 나타냅니다. 기능적 언어로 "목록"이라고 말하면 일반적으로 의미합니다 (단일 연결 목록, 일반적으로 변경 불가능). 이러한 유형의 경우 append는 O (n)이고 cons는 O (1)입니다.

참고 URL : https://stackoverflow.com/questions/1320139/why-is-appending-to-a-list-bad