ArrayList, LinkedList의 특징과 차이

ArrayList

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

LinkedList

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

어떨때 사용하면 좋을까

ArrayList

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

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

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

LinkedList

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

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

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

결론

• 검색: ArrayList가 빠름

• 삽입,삭제: LinkedList빠름

• 공간복잡도는 LinkedList가 높다

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

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