Collection이란?
데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현한 것이다.
기존에는 여러 개의 객체들을 하나의 객체에 담기 위해서 Object 클래스의 배열을 사용했지만, 배열의 경우 정적 메모리 할당(선언한 크기의 공간만큼 사용)을 하는 반면 컬렉션은 동적 메모리 할당(공간이 계속 필요한만큼 추가)을 하기 때문에 메모리 면에서 효율적으로 사용할 수 있다.
자바의 컬렉션의 구조는 다음과 같다.
ArrayList란?
ArrayList란 자바의 컬렉션 중 하나로서, 동적 배열을 구현한 클래스
이때, 동적 배열이란 할당된 ArrayList의 배열 공간이 꽉 찼을 때 새로운 배열을 만들어서 기존의 내용을 자동으로 복사하는 과정을 일컫는다.
- 일반적으로 기존 배열의 크기는 10이며, 새로운 배열을 생성할 시 1.5배 확장
지금까지 설명한 ArrayList를 그림으로 표현하면 다음과 같다.
ArrayList의 특징
보통 검색이 빈번한 경우에 모든 데이터를 상수 시간에 접근할 수 있다는 장점을 가지고 있다. 그러나,
ArrayList는 배열 공간이 꽉 차거나, 요소 중간에 삽입을 행하려 할때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.
이러한 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 리사이징 처리에서 시간이 소모된다.
LinkedList란?
LinkedList란 자바의 컬렉션 중 하나로서, 노드와 포인터로 이루어져 있는 클래스
LinkedList는 데이터를 배열에 저장하는 구조가 아니라, 노드(Node)에 데이터(value)와 이전 노드를 가리키는 포인터(prev), 다음 노드를 가리키는 포인터(next)를 가지고 있다.
- 노드(Node) : 데이터를 담고있는 값(value)을 저장
- 이전 포인터(prev) : 노드가 이전 노드를 가리키는 포인터이며, 이 포인터를 통해 이전에 위치한 노드와 연결되며 탐색할 수 있음
- 첫 번째 노드인 경우, 이전 포인터는 null 값 - 다음 포인터(next) : 노드가 다음 노드를 가리키는 포인터이며, 이 포인터를 통해 다음에 위치한 노드와 연결되며 탐색할 수 있음
- 마지막 노드인 경우, 다음 포인터는 null 값
LinkedList의 특징
LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다. 따라서 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다
하지만 LinkedList 에도 만능이 아니며 단점이 존재한다.
요소를 get 하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능하기 때문이다.
LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점 이다. 배열 같은 경우 그냥 데이터 그대로만 저장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에 next 나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요 할 수 밖에 없다.
LinkedList vs ArrayList 성능 비교
시간 복잡도 비교
실제 성능 측정
두 리스트에 대해 실제 메서드 동작 시간을 측정한 그래프이다.
조회(get)시에는 arraylist가 우위 지만 삽입/삭제(add/remove) 시에는 linkedlist가 뛰어난 성능을 보여준다.
But, LinkedList는 의외로 잘 사용되지 않는다
나노초 단위로 비교하면 차이가 있는건 사실이지만, 실제로 체감이 되지 않을 정도로 미세한 차이가 있다고 한다.
ArrayList의 배열 공간이 꽉 차거나, 요소 중간에 삽입 경우 배열을 복사하는 과정에서 시간이 많이 들거같지만, 사실 내부적으로 최적화가 잘 되어 있어서 성능면에서 크게 차이가 없다.
