List 자료구조 선택하기 (LinkedList, ArrayList)

List 자료 구조 선택하기 (Java)

ArrayList와 LinkedList 중 어떤 자료구조를 선택하면 좋을까?

• 이중 연결 리스트 구현은 ArrayList 클래스보다 시작에 요소를 추가하고 삭제하는 연산이 좋다. 끝에 요소를 추가하고 제거하는 연산은 ArrayList와 동일하다. 따라서 ArrayList 클래스의 유일한 이점은 get과 set 메서드이다. 연결 리스트는 심지어 이중 연결 리스트일 때도 선형 시간이 필요하다.
• 응용 프로그램의 실행 시간이 get과 set 메서드에 의존한다면 ArrayList 클래스가 좋은 선택이다. 실행 시간이 시작이나 끝 근처에 요소를 추가하거나 제거하는 연산에 의존한다면 LinkedList 클래스가 좋다.
• 하지만 이러한 추천은 큰 문제의 증가 차수에 기반을 두고 있다. 이 외에 고려해야 할 요소는 다음과 같다.
  • 이러한 연산이 응용 프로그램의 실행 시간에 뚜렷한 영향을 미치지 않는다면, 즉 응용 프로그램이 다른 일을 하느라 대부분의 시간을 소모하면 List 구현 선택은 큰 의미가 없다.
  • 작업하는 리스트가 매우 크지 않으면 기대하는 성능을 얻기 어려울 수 있다. 작은 문제에서는 이차 알고리즘이 선형 알고리즘보다 빠르기도 하고 또는 선형 알고리즘이 상수 시간보다 빠르기도 하다. 작은 문제에서는 그 차이가 그리 중요하지 않다.
  • 공간에 대해서 잊지 않도록 한다. 지금까지 실행 시간에 초점을 맞추었지만, 다른 구현은 다른 양의 공간이 필요하다. ArrayList에서 요소들은 한 덩어리의 메모리 안에 나란히 저장되어 거의 낭비되는 공간이 없고, 컴퓨터 하드웨어도 연속된 덩어리에서 종종 속도가 더 빠르다. 연결 리스트에서 각 요소는 하나 또는 두 개의 참조가 있는 노드가 필요하다. 참조는 공간을 차지 한다. 메모리 여기저기에 노드가 흩어져 있으면 하드웨어의 효율이 떨어질 수 있다.

요약하면 알고리즘 분석은 자료구조를 선택하는 지침을 제공하지만, 오직 다음 조건일 때만 유효하다.

1. 응용 프로그램의 실행 시간이 중요하다.
2. 응용 프로그램의 실행시간이 선택한 자료구조에 의존한다.
3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제 크기가 충분히 크다.

참고 및 출처

• 책 <자바로 배우는 핵심 자료구조와 알고리즘>