[리스트] ArrayList, LinkedList

ArrayList (배열 리스트)

배열을 이용한 리스트이다.

ArrayList 의 장점

- 인덱스가 있어서 정렬이 되어있을 때, 이진탐색을 이용한 탐색이 쉽다.

ArrayList 의 단점

- 컴파일 시 배열의 크기를 정해주어야 한다.
- 삽입 및 삭제 시 배열을 하나씩 당겨주거나, 하나씩 밀어주어야 한다.

데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리하다.

LinkedList (연결 리스트)

데이터를 담을 공간과 다음 데이터를 가르키는 포인터 하나가 구조체를 이룬다.

LinkedList 의 장점

- 논리적 공간의 제약이 없다.
- 삽입 및 삭제 시, 시간복잡도가 O(1)이다.

LinkedList 의 단점

-  탐색 시, 시간복잡도가 O(n)이다.

삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리하다.