자바에서는 Array, ArrayList, LinkedList로 구분할 수 있습니다.
대부분의 경우 알고리즘 문제에서는 Array를 주지만, 실제 코딩을 할 때에는 ArrayList를 사용하는 것이 개발할 때 더 편합니다.
Array와 ArrayList는 모든 특성이 같지만, Array는 크기조절을 직접해줘야 하기 때문입니다. 속도는 빠르지만, 불편하기 때문에 잘 사용하지 않습니다.
따라서 세 경우를 전부 비교하지 않고 ArrayList와 LinkedList만 비교하려고 합니다.
Java Array와 ArrayList의 차이
Array와 ArrayList은 모든 것이 비슷합니다. 가장 큰 차이점은 길이를 조정할 수 있는가? 없는가? 입니다.
Java의 Array는 고정 길이 입니다. 따라서, 정해진 길이의 배열을 모두 채우면, 새로운 데이터를 추가하고 싶을 경우 새로운 배열을 만들어주어야 합니다.
Java의 ArrayList는 가변 길이입니다. 하지만 내부적으론 배열로 구성되어 있습니다. ArrayList는 Default로 10개의 공간을 가진 배열로 시작합니다. 하지만 최적화(지연 초기화)로 인해 막 생성하면 0개의 사이즈로 시작됩니다. 참고
검색어: ArrayList default size
그 밖에 정해진 용량을 초과하면 새로 배열을 생성할 때에는 JDK의 구현마다 다른 구현방식을 사용할 수 있습니다. 참고
검색어: arraylist capacity increase in java
즉, ArrayList는 좀 더 개발자에게 편한 배열이라고 생각할 수 있습니다. 다만, 편리함의 대가로 살짝 Array보다 느리니 Array로 충분히 처리 가능하다거나 코딩 테스트나 알고리즘을 풀 때에는 Array를 활용해주는 것이 좋을 것 같습니다.
ArrayList와 LinkedList의 차이
공간적 제약
ArrayList는 결국 배열이므로 길이가 고정되어 있습니다. 때문에, 새로 배열에 새로운 요소를 추가하려고 할 때, 배열의 용량이 이미 가득 차있다면 새로운 배열을 생성해주어야 합니다. 이 때, 새로 생성된 배열이 메모리 상에 연속해서 생길 수도 있지만, 이미 다른 값이 메모리를 사용하고 있는 경우, 새로운 위치에 배열이 생성되어야 하고 이는 모든 요소를 옮긴다는 얘기가 됩니다. 또 메모리에 여유공간이 없는 경우 에러가 발생할 수도 있습니다.
반면, LinkedList는 한 개의 Node는 다른 Node에 대한 참조만 가지고 있습니다. 따라서 공간적 제약을 ArrayList에 비해 받지 않습니다.
새로운 요소 추가
ArrayList는 새로운 요소를 추가할 때, 여유 공간이 있는 경우엔 O(1)이지만, 여유공간이 없는 경우엔 O(n)이므로 O(n)입니다.
LinkedList는 새로운 요소를 추가할 때, 항상 O(1)입니다. 왜냐하면, 그냥 마지막 요소에서 다음 참조값을 가지게만 하면 되기 때문입니다.
임의 접근과 순차 접근
임의 접근(Random Access)은 어떤 요소에 바로 접근하는 것을 이야기합니다. 반면 순차 접근(Sequential Access)은 어떤 요소에 접근할 때, 차례차례 접근하는 것을 이야기합니다.
대개의 경우 List의 구현체로 ArrayList를 사용하는 이유가 바로 이 임의 접근에 있습니다. 바로 접근이 가능하다는 것은 곧 O(1)을 의미하기 때문입니다. 반면, LinkedList의 경우엔 순차 접근만 가능하므로 O(n)이 걸리게 됩니다.
새로운 요소 삽입(중간에)
ArrayList는 해당 요소뒤의 요소들도 전부 옮겨야 합니다. 하지만, LinkedList는 앞 뒤 요소의 값만 바꾸어주면 됩니다.
요소 삭제
요소 삭제의 경우도 삽입의 경우와 유사합니다. 중간의 요소를 삭제할 경우 ArrayList는 뒤의 요소들을 전부 앞으로 이동시켜야합니다. 하지만, LinkedList의 경우에는 앞 뒤 요소의 값만 바꾸어주면 됩니다.
요약
| ArrayList | LinkedList | |
|---|---|---|
| 접근 | O(1) | O(n) |
| 추가 | O(n) | O(1) |
| 삭제 | O(n) | O(1) |
- 추가와 삭제는 해당 요소의 추가 삭제시에 소요되는 복잡도를 의미합니다.
그 외의 접근하는 복잡도는 고려하지 않습니다.
감사합니다.
