컬렉션 프레임워크(2) - List 컬렉션 3 : Linked List

 

 

 

LinkedList는, 앞서 살펴보았던 ArrayList와 사용방법은 동일하지만, 내부 구조가 완전히 다른 List 구현 클래스입니다. 기본적으로 ArrayList는 배열(인덱스)을 기반으로 관리하지만, LinkedList는 인접참조를 통해 체인처럼 연결한 객체를 관리하게 됩니다.

 

 

컬렉션 프레임워크(2) - List 컬렉션 2 : ArrayList

 

---

 

 

위에서 말씀드렸다시피, 기본적으로 ArrayList와 LinkedList는 사용법 자체는 동일합니다. 인덱스 기반으로 배열처럼 생성과 호출이 진행되죠. 하지만, 배열 관리 구조의 차이로 인해 성능의 차이가 발생합니다. ArrayList는 만약에 배열 중간에 삭제나 추가가 일어나면, 이후의 모든 배열의 인덱스 넘버가 영향을 받는다고 했습니다. 그래서 맨 끝에 추가/삭제가 일어나는 경우에는 성능이 좋지만, 데이터 중간 수정이 빈번한 경우에는 사용을 추천하지 않는다 했습니다. 

 

하지만 LinkedList의 경우는 아래 그림과 같은 형태로 관리됩니다. 

 

 

 

 

즉, 각각의 인접 객체끼리 연결되어 관리되는 것입니다. 만일, 특정 인덱스에 추가/삭제 등의 변화가 일어날 경우에는 다른 링크 연결된 체인은 그대로 있고, 해당 인덱스 인접 객체끼리의 연결에만 변화가 생기는 것입니다. "결국 인덱스 넘버는 변경되는 것이 아닌지?"라는 생각이 들기도 하겠지만, 편의상 인덱스 넘버를 사용할 뿐 ArrayList와 LinkedList의 구조는 아예 다르기 때문에 이 점은 신경쓰지 않으셔도 됩니다. 

 

그렇기 때문에 두 구현 클래스는 장단점이 있습니다. ArrayList는 추가 삭제가 어려운 리스트 방식인만큼, 대신에 검색에 있어서는 매우 빠른 속도를 자랑합니다. 순차적인 인덱스 넘버를 찾아가면 끝이니까요. 반대로 LinkedList는 특정 위치 검색은 상대적으로 느린 반면, 위에서 설명한 것처럼 중간 추가/삭제 등의 수정에 있어서 매우 빠른 속도를 자랑합니다. 

 

 

분류	순차적 추가 / 삭제	중간 추가 / 삭제	검색
ArrayList	빠름	느림	빠름
LinkedList	느림	빠름	느림

 

 

 

---

 

아래 예제에서, LinkedList와 ArrayList를 통해 0번 인덱스에 10000개의 객체를 추가하는 과정의 속도를 측정했습니다.

 

public class ExampleMain {
	public static void main(String[] args) {
	
	List<String> list1 = new ArrayList<String>();
	List<String> list2 = new LinkedList<String>();
	
	long startTime;
	long endTime;
	
	// ArrayList
	startTime = System.nanoTime();
	
	for(int i = 0; i < 10000; i++) {
		list1.add(0, String.valueOf(i));
	}
	
	endTime = System.nanoTime();
	
	System.out.println("ArrayList : " + (endTime - startTime) + "ns");
	
	
	// LinkedList
	startTime = System.nanoTime();
	
	for(int i = 0; i < 10000; i++) {
		list2.add(0, String.valueOf(i));
	}
	
	endTime = System.nanoTime();
	
	System.out.println("LinikedList : " + (endTime - startTime) + "ns");
	
	}
}

/* 출력
ArrayList   : 2828900ns
LinikedList : 1168000ns
*/