Java Collection이란?
자바에서 Collection이란 데이터의 집합, 그룹을 의미하며, JCF(Java Collection Framework)는 이러한 데이터, 자료구조인 컬렉션과 이를 구현하는 클래스를 정의하는 인터페이스를 제공한다.
Collection 인터페이스는 List, Set, Queue로 크게 3가지 상위 인터페이스로 분류할 수 있다.
그리고 Map의 경우 Collection인터페이스를 상속받고 있지 않지만, Collection으로 분류된다.
LinkedList란?
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.
Node는 LinkedList에 객체를 추가하거나, 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않기 때문에 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없다. 그렇기 때문에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하다. 하지만 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다.
그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고, 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.
ArrayList란?
중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사하다. 배열은 크기가 지정되면 고정이지만, ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재한다.
하지만 추가했을 때, 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 된다.
그럼 용량이 초과되었을 때 내부 코드는 어떻게 동작할까?
ArrayList안에는 배열에 값을 추가할 수 있는 add()메소드가 존재하는데, ensureCapacityInternal()에서 배열 용량을 늘리는 작업이 일어난다.
해당 작업을 통해 배열의 용량을 늘린 새로운 배열을 생성하여 내용을 복사하게 된다.
즉, ArrayList는 내부에 고정된 크기를 갖는 배열을 가지고 있고, 어떤 요소를 추가할 때 그 배열의 크기를 넘어가게 되면 늘린 크기의 배열을 새로 할당 해준다.
정리 + ArrayList와 LinkedList차이점
ArrayList와 LinkedList는 둘다 List인터페이스를 상속하는 인터페이스이다.
ArrayList는 크기가 고정된 배열과 달리, 동적으로 크기를 늘릴 수 있고, LinkedList와는 달리 특정 인덱스 배열에 빠르게 접근할 수 있다는 특징이 있다.
동적으로 크기를 늘릴 때의 특징은 지정된 크기를 벗어났을 때, 더 큰 크기의 배열을 새로 생성하여 복사한 후, 새로 할당하게 된다.
LinkedList는 각 노드가 데이터와 포인터를 가지고, 한 줄로 연결되어 구성된 리스트이다.
LinkedList 또한 크기를 동적으로 늘릴 수 있다는 특징이 있다.
LinkedList는 데이터를 추가하거나 삭제할 때, 앞뒤의 링크만 변경되고 나머지 링크는 변경되지 않기 때문에 전체의 인덱스가 밀리거나 당겨지는 일이 없다.
하지만 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다.
참고: https://gangnam-americano.tistory.com/41, https://coding-factory.tistory.com/552, https://devlog-wjdrbs96.tistory.com/64, https://sabarada.tistory.com/63