> List (Interface)
List Interface를 구현한, 자료구조 Class들의 특징을 이야기 하려고 한다. List는, 소속된 Element의 순서가 있는 Collection 종류이다. 각 Element가 삽입되는 위치를 정확하게 제어 할 수 있다. 또한 정수로 되어있는 Index를 이용해 Element 접근할 수 있다.
Set과 달리 List는 일반적으로 중복 요소를 허용한다. 문법적으로 이야기 하자면, 일반적으로 List는 e1.equals(e2)가 허용되는 소속 Element들이 존재할 수 있다. 그리고 일반적으로 null Element를 허용하는 경우 여러 개의 null Element를 허용한다.
Iterator를 이용하여 Element의 삽입 및 교체, 접근 등이 가능하며 구현체들은 Iterator를 얻기위한 메서드를 제공한다.
List를 구현한 구현체로는 ArrayList와 LinkedList가 일반적으로 사용된다.
Element로의 접근 및 검색, 삽입, 삭제 등 에서 두 구현체는 구현방법에 따른 성능차이를 보인다. 경우에 따라 ArrayList와 LinkedList가 더 적합한 경우가 존재한다.
> ArrayList
Element들을 저장하는 방법에 있어서 Array[배열]를 사용한다. 그러므로 배열의 장점 및 단점을 어느 정도 공유한다. 예를 들면, Index를 이용해 각 Element에 Direct로 접근 할 수 있는 장점이 있으며, Array가 초기 Size가 정해져 있는 단점이 있어 확장이 용이하지 않은 단점을 가지고 있다. 단지 ArrayList는 System.arraycopy를 이용해 특정 Size를 넘어가면 자동 확장하게 구현되어 있다. 그러나 분명 자동 확장이라 하더라도 확장할때의 성능 저하는 존재한다. 그러한 점 때문에 ArrayList는 초기 생성 할 때 배열의 초기 Size를 지정할 수 있다. (DEFAULT_CAPACITY = 10) 어느 정도 크기가 예상될 경우 기본 크기를 그에 맞게 초기에 설정하는 것이 성능상 유리하다.
또한 List의 중간에 Member의 추가 및 삭제가 이루어질 경우도 부하가 존재한다. 배열의 구조를 생각한다면 당연하게 생각 될 것이다.
ArrayList 배열은 일단 확장하고 나면, Element들을 삭제하여도 그 배열 크기는 줄어들지 않는다. Element의 수가 계속해서 늘었다 줄었다 한다면 ArrayList는 최적의 선택이 아닐 수 있다.
> LinkedList
Element들을 저장하는 데 배열을 이용하지 않고, 리스트 안에서 다음 Element를 가리키는 내부 객체를 이용한다. LinkedList의 각 Element는 해당 Element의 고유 객체(item)와 함께 다음 Element를 가리키는 재귀적 타입인 next라는 필드를 가지고 있다. 또한 prev라는 필드는 직전의 Element를 가리킨다. 이를 이용하면 리스트 사이를 쉽게 이동할 수 있고 순서대로 각 원소를 찾아 처리할 수도 있다. 이러한 특징은 ArrayList의 단점을 없에 준다. List의 중간에 삭제나 삽입이 이루어지기 수월하고, 확장에 따른 부하가 존재하지 않는다. 그러나 ArrayList가 가지고 있는 장점이 LinkedList에서는 단점이 된다. Index를 이용한 Element로의 Direct접근이 불가능하다. get(int index)를 이용할 경우 LinkedList는 List의 첫 요소 부터 혹은 끝부터 List를 순회하여 해당 index를 찾도록 구현 할 수 밖에 없는 것이다.
> ArrayList와 LinkedList의 성능 비교