ArrayList
- 배열을 이용하여 만든 리스트
- 데이터의 저장 순서가 유지되고 중복을 허용
- 데이터량에 따라 공간이 자동으로 늘어나거나 줄어들음 (현재 배열의 크기가 부족하다면, 더 큰 크기의 새로운 배열을 할당하고 기존의 요소들을 새 배열로 복사한다.)
- 단방향 포인터 구조로 자료에 대한 순차적인 접근에 강점이 있어 조회가 빠르다.
- 삭제/삽입이 느리다는 단점이 있다. 단, 순차적으로 삭제/삽입하는 경우에는 가장 빠르다.
LinkedList
- 노드(객체)를 연결하여 리스트처럼 만든 컬렉션(배열이 아님)
- 각 요소는 데이터와 다음 요소를 가리키는 포인터로 구성. 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 링크로 이루어진 구조
- 데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다.
- 임의의 요소에 대한 접근 성능은 좋지 않다.
- 자바의 LinkedList 는 양방향 포인터 구조로 이루어져 있다.
- ArrayList 가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안
ArrayList의 문제점
- 배열 공간이 꽉 차거나, 요소 중간에 삽입을 행하려 할 때 기존의 배열을 복사해서 요소를 뒤로 한 칸씩 일일이 이동해야 하는 작업이 필요
- 삽입/삭제가 빈번하게 발생하는 프로세스의 경우 시스템 성능 저하로 이어질 수 있다.
- 자료들이 지속적으로 삭제되는 과정에서 ArrayList 에서는 그 공간만큼 낭비되는 메모리가 많아지게 되고 리사이징 처리에서 시간이 소모된다.
LinkedList의 장단점
장점
- LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있기 때문에 공간의 제약이 존재하지 않는다.
- 또한 삽입의 경우 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입/삭제의 속도가 빠르다.
단점
- ArrayList 는 무작위 접근이 가능하지만(자료를 연속적인 묶음으로 묶어 저장) LinkedList는 순차접근만(저장 공간에 불연속적인 단위로 저장)이 가능하기 때문에 특정 자료의 탐색 시간이 많이 소요된다.
- 참조자를 위해 추가적인 메모리 할당이 필요하다.
ArrayList vs LinkedList 시간 복잡도
| 작업 | 메소드 | ArrayList | LinkedList |
| add at last index | add() | O(1) | O(1) |
| add at given index | add(index, value) | O(N) | O(1) |
| remove by index | remove(index) | O(N) | O(1) |
| remove by value | remove(value) | O(N) | O(1) |
| get by index | get(index) | O(1) | O(N) |
| search by value | indexOf(value) | O(N) | O(N) |
'JAVA' 카테고리의 다른 글
| 자바 HashMap (0) | 2023.12.30 |
|---|---|
| 자바의 정석 - 7장 객체 지향 언어 2 (0) | 2022.09.15 |
| 자바의 정석 - 6장 객체 지향 언어 (0) | 2022.09.14 |
