DataStructure ArrayList vs LinkedList
2021, Mar 12
알아보게 된 이유.
팀에 있는 분과 알고리즘에 대해 이야기 해보다가 시간 복잡도에 대해 이야기를 해보았다.
정리를 해보자.
| 리스트 | 설명 |
|---|---|
| Array | 정적인 길이를 제공하는 배열 |
| Vector | Java 1.0에서 추가. 동기화 기능이 제공되는 가변이 가능한 자료구조. |
| ArrayList | Java 2.0에서 추가. 동기화가 제공되지 않음. 데이터의 검색에 유리하며, 추가, 삭제에는 성능을 고려해야 한다. |
| LinkedList | Java 1.2에서 추가. ArrayList에 비해 데이터의 추가, 삭제에 유리하며 데이터 검색시에는 성능을 고려해야 한다. |
ArrayList
-
ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사하는 방법을 사용하고 있다.
- 대량의 자료를 추가/삭제하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있다.
- 하지만 각 데이터는 인덱스를 가지고 있기 때문에 한번에 참조가 가능해서 데이터 검색에는 유리하다.
데이터 검색시에는 ArrayList는 인덱스 기반의 자료구조라서 get(int index)를 통해서 O(1)의 시간 복잡도를 갖는다.
LinkedList
-
LinkedList는 데이터를 저장하는 각노드가 이전 노드와 다음 노드의 상태만 알고 있다.
-
ArrayList와 같이 데이터의 추가, 삭제 시 불필요한 데이터의 복사가 없어서 추가,삭제시에는 유리하지만, 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다.
데이터 검색시에는 LinkedList는 모든 요소를 탐색해야 하기 때문에 최악의 경우에는 O(n)의 시간 복잡도를 갖는다.
작업의 속도비교
| 작업 | ArrayList | LinkedList |
|---|---|---|
| 이전 원소/다음 원소 찾기 | O(1) | O(1) |
| 맨 뒤에 원소 추가/삭제 | O(1) or O(n) | O(1) |
| 맨 뒤 이외의 위치에 원소 추가/삭제 | O(n) | O(1) |
| 임의의 위치의 원소 찾기 | O(1) | O(n) |
| 크기 구하기 | O(n) | O(n) or O(1) |