September
3rd,
2022
Java에서 ArrayList와 LinkedList 둘다 모두 List 인터페이스를 구현하고 있다. 둘다 순서를 유지하고 있는 클래스지만 아래와 같은 차이점이 있다.
| ArrayList | LinkedList |
|---|---|
| ArrayList는 내부적으로 동적 배열을 사용하여 저장한다. | LinkedList는 내부적으로 더블 링크드 리스트를 사용하여 요소를 저장한다. |
| 내부적으로 배열을 사용하기 때문에 조작 측면에서 볼때는 느리다. 예를들어 원소 하나가 제거된다면 다른 배열 요소들이 빈자리를 채우러 메모리에서 이동되어야 한다. | 조작 측면에서는 Double Linked List를 사용하고 있기 때문에 LinkedList가 ArrayList보다 빠르다. 그러므로 어떤 것도 메모리에서 이동할 필요가 없다. |
| ArrayList는 오로지 list의 역할만 한다. 왜냐하면 오로지 List만의 구현체이기 때문이다. | LinkedList는 리스트와 큐로 사용될 수 있다. List와 Deque 인터페이스 구현체기 때문이다. |
| ArrayList는 데이터를 저장하고 액세스하는게 더 낫다. | LinkedList는 데이터 조작 측면에서 더 좋다. |
| ArrayList의 요소들은 메모리에서 연속적이어야 한다. | LinkedList의 요소들은 메모리에서 연속적일 필요가 없다. |
| 일반적으로 ArrayList가 초기화 되면 기본 용량인 10이 할당된다. | LinkedList는 기본 용량이 없다. LinkedList에서는 LinkedList가 초기화될 때 빈 목록이 만들어진다. |
| ArrayList는 크기 조정 가능한 배열이다. | LinkedList는 List 인터페이스의 Doubly Linked List를 구현한다. |
| 구분 | Array | ArrayList | LinkedList |
|---|---|---|---|
| i번째 탐색 | 인덱스를 이용하여 constant time에 탐색 O(1) |
인덱스를 이용하여 constant time에 탐색 O(1) |
i번 만큼 체인 이동 => O(n) |
| i번째 삽입 | 새로운 배열 할당 비용 + 전체 배열 복사 비용 O(n) + 공간 비용 + 복사 비용 |
i번째 탐색 비용 + i번째 이후 원소들의 인게스를 1 증가시키며 복사하는 비용 + capacity 초과시 새로운 배열 할당 비용 O(n) + 복사 비용 + 공간 비용(capacity 초과시) |
i번째 탐색 비용 + i를 기준으로 앞 뒤 노드 참조 연결 비용 => O(n) + 앞뒤 노드 참조 맵핑 비용 |
| i번째 삭제 | 새로운 배열 할당 비용 + 전체 배열 복사 비용 => O(n) + 공간 비용 + 복사 비용 |
i번째 탐색 비용 + i번째 이후 원소들의 인덱스를 -1 감소시키며 복사하는 비용 + n번째 원소는 삭제 O(n) + i 번째 이후 복사 비용 |
i번째 탐색 비용 + i번째 앞 뒤 노드간 참조 연결 비용 O(n) + 앞뒤 노드 참조 맵핑 비용 |
중요사항
-
사용해야 할 때
LinkedList : 추가 또는 제거가 읽기보다 높으면 사용한다.
ArrayList : 읽는 빈도가 추가 또는 제거보다 많으면 사용한다.
-
ArrayList는 연속적인 메모리 할당으로 cache locality가 좋다. CPU 캐시는 한 메모리 주소에 접근할 때 그 주소뿐 아니라 해당 블록을 전부 캐시에 가져오게 된다. 이때 Array는 해당 블록에 있는 것들은 함꼐 캐싱되기 때문에 cache miss가 덜하다. LinkedList는 비연속적인 메모리 할당을 하기 때문에 효율적인 캐싱이 어렵고 cache miss가 많이 발생하게 되고 이에 따른 오버헤드가 있다.
-
LinkedList의 메모리 오버 헤드는 ArrayList에 비해 더 많다. LinkedList는 이전 노드와 다음 노드의 주소를 저장하는 데 필요하므로 두 개의 추가 링크가 있고, 이러한 링크는 추가 공간을 소비한다.