JAVA의 List 컬렉션
- 데이터를 인덱스로 관리
- 데이터 자체가 아닌 번지(주소)를 저장
- 데이터의 중복 저장이 가능
- 저장 순서가 유지됨
- 구현 클래스는
ArrayList,LinkedList,Vector,Stack등이 있음
ArrayList
- 배열의 크기를 동적으로 할당하고 싶을 때 사용
- 데이터의 삽입, 삭제 시 임시 배열을 생성해 데이터를 복사하는 방법 사용
검색
- 인덱스를 활용해 데이터에 빠른 접근 가능
삽입 & 삭제
- 배열 끝부분을 제외한 위치의 데이터 삽입, 삭제 시 데이터의 복사와 이동이 많이 발생해 시간이 많이 걸림
LinkedList
ArrayList의 단점을 보완하기 위함- 데이터의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결한 구조
- 노드와 포인터로 관리되기 때문에 메모리 측면에서 봤을 때는 ArrayList가 낫다
검색
- 첫번째 데이터부터 차례대로 접근해야 하기 때문에 시간이 많이 걸림
삽입 & 삭제
- 데이터를 삽입, 삭제하는 위치에 해당하는 노드의 주소값만 바꾸면 되기 때문에 빠름
정리
| Method | ArrayList | LinkedList | |
|---|---|---|---|
| 검색 | get(index) | O(1) | O(n) |
| 끝에 삽입 (추가) | add(value) | O(1) | O(1) |
| 앞/중간에 삽입 | add(index, value) | O(n) | search time + O(1) |
| 삭제 | remove(index) | O(n) | search time + O(1) |
데이터의 검색이 잦은 경우 ArrayList가 적합하다
- 순차적으로 접근해야한다면?
- ArrayList는 메모리에 연속으로 저장되고 LinkedList는 무작위의 공간에 저장됨
- 추가적으로 다음 데이터의 주소를 찾은 후 접근하기 보다 메모리상 연속적으로 저장된 ArrayList가 빠름
데이터의 삽입, 삭제가 잦은 경우 LinkedList가 적합하다
- 데이터 검색 속도를 포함한다면?
- ArrayList는 추가 공간을 확보하거나 데이터를 이동하는 처리 속도가 느리기 때문에 색인 속도를 포함해도 LinkedList가 더 빠름
