[Coding Test] Collection(4)

1. ArrayList

• 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 비슷
• 하지만 ArrayList는 배열과 다르게 배열을 추가하고 삭제하는 매서드가 존재
• 데이터 추가시 더 큰 용량의 임시 배열을 만들어 복사

2. LinkedList

• 연결된 노드들의 집합인데, 각 노드는 데이터와 포인터(다음 노드를 가리키는)로 이루어져 있다.
• 데이터 추가시 새로운 데이터 노드를 만들고 이전 노드의 포인터를 새 노드를 가리키게 만든다.
• 즉, 각 노드는 앞 뒤의 노드의 위치를 저장한다.

3. ArrayList vs LinkedList

1) ArrayList

인덱스 기반의 자료구조이기 때문에 get(int index)를 통해 무작위 접근 가능 → O(1)의 시간복잡도를 가짐

삽입, 삭제시 배열을 임시배열에 복사하는 방식이기 때문에 O(N) 복잡도

포인터를 저장하지 않아도 되는 배열 (연속된 메모리안에 저장)

2) LinkedList

처음노드부터 찾으려는 노드까지 순차적으로 탐색해야하므로 최대 O(N)의 시간복잡도를 가짐

삽입, 삭제시 이전노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 O(1)의 복잡도

포인터의 사용으로 저장공간을 많이 차지한다

3) 결론

• 검색: ArrayList가 빠름

• 삽입,삭제: LinkedList빠름

• 공간복잡도는 LinkedList가 높다

데이터 검색을 자주한다면 ArrayList, 데이터 삽입 및 삭제를 많이 한다면 Linked List

ArrayList는 연속된 메모리안에 저장되고, 포인터를 저장할 필요가 없기 때문에 공간효율성 관점에서는 더 유리