Arraylist 또는 LinkedList에서 요소를 제거하는 것이 더 효율적입니까?

Question

이론적으로, 요소를 ArrayList 또는 a LinkedList?

Answer 1

그것들을 LinkedList, an에서 제거하기 때문에 ArrayList 모든 후속 요소를 목록의 새로운 위치로 옮기는 것이 필요합니다. 배열의 모든 후속 요소에는 새 값이 할당되어야합니다. 링크 된 목록의 경우 하나의 포인터 (또는 이중 연결 목록이있는 2 개) 만 재 할당해야합니다.

Answer 2

글쎄, (이중-연결된) 목록에서 요소를 제거하는 것은 O (1)입니다. 그러나 배열에서 제거하려면 나머지 요소가 배열의 한 공간, 즉 O (n)의 한 공간 아래로 이동해야합니다.

즉, 인덱스별로 목록에서 특정 요소를 얻는 것은 O (n)이며, 인덱스별로 특정 요소를 얻는 것은 O (1)입니다.

따라서 실제 제거를 위해 LinkedList가 더 좋습니다. 배열 대 링크드 목록에 대한 추가 정보가 있습니다 여기.