List 컬렉션(ArrayList vs LinkedList)

List 컬렉션이란 무엇인지 알아보고 대표적 구현 클래스인 ArrayList와 LinkedList를 서로 비교하여 알아보자. 

Interface List<E> : List Collection

• List컬렉션은 java.util 패키지에 있으며 Collection 인터페이스를 상속한다.
• List 컬렉션은 listIterator 인터페이스의 팩토리이며 ListIterator를 통해 List를 정방향, 역방향으로 반복할 수 있다.
• List 컬렉션은 객체를 일렬로 늘어놓은 구조를 가지고 있으며 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색,삭제할 수 있는 기능을 제공한다.
• List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조한다.
• List 컬렉션은 인덱스 순서대로 저장이 되며, 동일한 객체를 중복 저장할 수 있는데, 이 경우 동일한 번지가 참조 된다.
• null도 저장이 가능하며, 이 경우 해당 인덱스는 객체를 참조하지 않는다.
• List Collection을 구현하는 대표적인 클래스들은 ArrayList, Vector, LinkedList가 있다.(Vecotr 클래스는 Java5 부터 사용 되지 않는다.)
• List<E> 에서의 E 타입의 파라미터는 List 인터페이스가 제네릭 타입이기 때문이며, 구체적인 타입은 구현 객체를 생성할 때 결정된다.

 

 

참고로 List Collection이 상속받고 있는 자바의 컬렉션 프레임워크에 대한 내용은 아래 링크를 참고!

자바컬렉션 프레임워크(Java Collection Framework) 장점 / 종류

 

 

 

 

그렇다면, List Collection을 구체화한 클래스들을 하나 하나 예제와 함께 자세히 알아보자!

이번 포스팅에서는 List Collection을 구체화한 클래스 중, ArrayList와 LinkedList에 대해 알아본다.

 

 

Class ArrayList<E>

• ArrayList는 List 인터페이스의 구현 클래스로 Arraylist에 객체를 추가하면 객체가 인덱스로 관리가 된다.
• 일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 공통점이 있지만 배열은 생성할 때 크기가 고정적이고 사용 중에 크기를 변경할 수 없지만, ArrayList는 저장 용량을 초과한 객체가 add되면 자동으로 용량이 늘어난다는 차이가 있다.
• ArrayList를 생성하기 위해서는 저장할 객체 타입을 타입 파라미터로 표기하고 기본 생성자를 호출하면 된다.

List<String> list = new ArrayList<String>();

 

• 기본 생성자로 ArrayList 객체를 생성하면 내부에 10개의 객체를 저장할 수 있는 초기용량(capacity)을 갖게 된다.
  (Java의 Arraylist는 내부적으로 배열의 크기가 고정되어 설정됨. 만약 배열이 가득 찼음에도 새로운 데이터가 추가된다면 기존의 배열보다 1.5배 긴 새로운 배열을 만들어 기존 리스트 데이터를 새로운 배열로 복제)
• 저장되는 객체수가 늘어나면 용량이 자동으로 증가하지만, 처음부터 용량을 정해줄 수도 있다.

List<String> list = new ArrayList<String>(30);

 

• 자바 4이전에는 제네릭이 도입되기 이전이기 때문에 타입변환이 필요하다.(성능에 좋지 못함)
• ArrayList에 객체를 추가하면 인덱스 0부터 차례대로 저장된다.
• ArrayList에서 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 1씩 앞으로 당겨지고 특정 인덱스에 객체를 삽입하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 밀려난다.
  
  >>> 따라서, 빈번한 객체의 삭제와 삽입이 일어나는 곳에서는 ArrayList대신 LinkedList를 사용하는 것이 더 좋다.
         그러나 인덱스 검색이나 맨 마지막에 객체를 추가하는 경우에는 ArrayList가 더 좋은 성능을 발휘 한다.
  
  
• ArrayList를 생성하고 런타임 시 필요에 의해 객체들을 추가하는 것이 일반적이지만, 고정된 객체들로 구성된 List를 생성할 때도 있다. 이런 경우에는 Arrays.asList(T...a) 메소드를 사용하는 것이 간편하다.
  
  

List<String> list1 = Arrays.asList("a", "b", "c");
		
for(String obj : list1)
{
    System.out.println(obj);
}

 

• T타입 파라미터에 맞게 asList()의 매개값을 순차적으로 입력하거나 T[] 배열을 매개값으로 주면 된다.

Class LinkedList<E>

• LinkedList는 List 컬렉션의 구현 클래스이므로 ArrayList와 사용방법은 동일하지만 내부 구조는 완전히 다르다.
• ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.
• LinkedList는 Node간의 연결(Link)을 이용하여 동적으로 크기를 할당할 수 있는 선형 자료구조이다.

• LinkedList의 각 Node는 데이터와 포인터를 가지고 있으며 각 Node의 포인터는 다음 Node 또는 이전 Node와의 연결을 담당한다.

출처 : https://medium.com/journey-of-one-thousand-apps/data-structures-in-the-real-world-508f5968545a

 

• LinkedList에서 특정 인덱스의 객체를 제거하거나 삽입했을 때, 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
  (빈번한 객체 삭제와 삽입이 일어나는 곳에서는 ArrayList보다 LinkedList가 더 좋은 성능을 발휘!!)
• LinkedList 생성하기 위해서는 저장할 객체 타입을 타입 파라미터(E)에 표기하고 기본 생성자를 호출하면 된다.

# LinkedList가 처음 생성될 때에는 어떠한 링크도 만들어지지 않기 때문에 내부는 비어있음
Linked<E> list = new LinkedList<E>();

 

ArrayList와 LinkedList 실행 성능 비교 테스트

 

ArrayList와 LinkedList에 10000개의 객체를 삽입하는데 걸린 시간을 측정하여 성능비교 테스트를 진행

실행 결과를 보면 LinkedList가 훨씬 더 빠른 성능을 나타내는 것을 볼 수 있다.

 

[ console out ]

 

 

List<String> arrayList = new ArrayList<String>();
List<String> linnkedList = new LinkedList<String>();

long startTime;
long endTime;

startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
    arrayList.add(0, String.valueOf(i));
}

endTime = System.nanoTime();
System.out.println("ArrayList 걸린 시간 : " + (endTime - startTime) + "(ns)");

startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
    linnkedList.add(0, String.valueOf(i));
}

endTime = System.nanoTime();
System.out.println("LinnkedList 걸린 시간 : " + (endTime - startTime) + "(ns)");

 

끝에서부터(순차적으로) 추가/삭제 하는 경우에는 ArrayList가 빠르지만 중간에 추가 또는 삭제하는 경우는 앞뒤 링크 정보만 변경하면 되는 LinkedList가 더 빠르다. ArrayList는 뒤쪽 인덱스들을 모두 1씩 증가 또는 감소시키는 시간이 필요하기 때문에 처리 속도가 느리다.

 

그러나

 

데이터를 검색하는 측면에 있어서 ArrayList는 LinkedList에 비해 굉장히 빠르다. ArrayList는 인덱스 기반의 자료구조이며, get(int index)를 통해 O(1)의 시간 복잡도를 가진다. 그에 비해 LinkedList는 검색할 때, 모든 요소를 탐색해야되기 때문에 최악의 경우 O(N)의 시간 복잡도를 가진다.

 

 

따라서, 다루는 데이터의 용도에 맞게 List class를 구현하여 사용하도록 한다.