들어가며
알고리즘 공부 중 알게 된 ArrayList 와 LinkedList를 비교하였습니다.
공통점
두 자료구조 모두 배열처럼 사용 가능합니다 하지만 원소를 저장하는 방식에 있어 다음과 같은 차이가 있습니다.
- 기본 구조
- 삽입, 삭제 시
- 메모리 공간
ArrayList
- 각 원소는 index를 가지고 있다. 때문에 조회 시 O(1)
- 삽입, 삭제 시 원소를 하나 밀고, 당기는 식으로 처리한다. 따라서 삽입 및 삭제 시 O(N)
- 단, 맨 끝에 삽입하는 경우는 O(1)
- 메모리 상에 연속된 공간에 저장되어 있어 데이터 접근 시 더 적은 시간이 소요된다
LinkedList
- 각 원소는 index가 아닌 앞, 뒤 원소의 위치 값을 가지고 있다. 즉 앞 뒤 노드의 포인터를 가지고 있는 연결 형태. 때문에 조회 시 O(N)
- 삽입, 삭제 시 앞, 뒤 노드의 포인터만 변경하는 방식으로 처리한다. 따라서 삽입 및 삭제 시 O(1)
- 단 index 기반으로 특정 위치를 찾아야 하면 탐색이 O(N) 걸림
- 메모리 상에 불연속된 공간에 저장되어 있다. 이런 이유에서 캐시 적중률이 낮아 실제 성능은 ArrayList가 더 좋은 경우가 많음
마치며
읽어주셔서 감사합니다.
참고자료
ArrayList vs. LinkedList
ArrayList와 LinkedList의 차이
ArrayList vs LinkedList 특징 & 성능 비교
Difference between Array List and Linked List
