나는 ArrayList 및 LinkedList의 장단점에 능통합니다. ArrayList는 추가 및 제거가 적을 때 무작위 액세스에 선호되며, 반대의 경우도 마찬가지입니다. 무작위 액세스를 모두 수행해야하는 데이터 구조가 필요하고 & 항목을 목록에서 자주 제거해야하는 경우 어떻게해야합니까?ArrayList 대 랜덤 액세스 및 추가 - 제거 모두에 대한 LinkedList
선택할 수있는 것은?
나는 ArrayList 및 LinkedList의 장단점에 능통합니다. ArrayList는 추가 및 제거가 적을 때 무작위 액세스에 선호되며, 반대의 경우도 마찬가지입니다. 무작위 액세스를 모두 수행해야하는 데이터 구조가 필요하고 & 항목을 목록에서 자주 제거해야하는 경우 어떻게해야합니까?ArrayList 대 랜덤 액세스 및 추가 - 제거 모두에 대한 LinkedList
선택할 수있는 것은?
임의의 액세스를 ArrayList로 가져 오려면 일반 목록으로 사용하고 항목을 추가/제거 할 수 있습니다.
ArrayList의 메모리는 블록으로 할당되며, ArrayList가 커질 때까지 메모리가 부족할 수 있습니다.
메모리 제한이 있는지 여부는 언급하지 않았으므로 (제한 사항은 임의 액세스 임) ArrayList가 모든 필요를 충족시켜야한다고 말했을 것입니다.
이러한 데이터 구조는 API와 호환되며 두 가지 모두를 사용하여 코드를 벤치마킹/프로파일 링합니다.
또 다른 힌트 : ArrayList
은 N
개의 조회와 N
개의 돌연변이를 수행한다고 가정합니다. 총 합계는 O(N) + O(N * N) <=> O(N^2)
입니다. LinkedList
을 사용하면 O(N*N) + O(N) <=> O(N^2)
(선형 조회 시간 N
+ 일정 시간 변이 시간 N
)이 표시됩니다. 그래서 두 가지 데이터 구조는 비슷합니다.
토끼 구멍에 조금 더 깊이 들어가기를 원하시면 scala.collection.immutable.Vector
은 룩업과 삽입/제거 모두 amortized constant cost입니다. 그리고 그것은 스레드로부터 안전하지 않은 불변입니다! 아래에 정교한 데이터 구조를 사용하여 구현됩니다.
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html –
@BheshGurung 귀하의 의견은 무엇을해야할지 모르겠습니까? –