컬렉션 프레임워크 LinkedList

LinkedList는 List 구현 클래스 이므로 ArrayList와 사용 방법은 같지만 내부 구조는 다릅니다.

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리합니다.

 

ArrayList는 객체가 제거되면 1씩 앞으로 당겨지지만 LinkedList는 객체를 제거해도 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다.

번번한 객체 삭제와 삽입이 일어나는곳에서는 ArrayList보다 LinkedList가 좋은 성능을 발휘합니다.

LinkedList를 생성하기 위해서는 저장할 객체 타입을 타입 파라미터 <E>에 표기하고 기본 생성자를 호출하면 됩니다.

처음에 생성될 때에는 어떠한 링크도 만들어지지 않기 때문에 내부는 비어있습니다.

List<E> list = new LinkedList<E>();

다음 예제는 ArrayList와 LinkedList 에 10000개의 객체를 삽입하는 데 걸린 시간을 측정한 예제입니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Ex4 {
	public static void main(String[] args) {
		List<String> list1 = new ArrayList<String>();
		List<String> list2 = new LinkedList<String>();

		long startTime;
		long endTime;

		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			list1.add(0, String.valueOf(i));
			// Array 리스트 객체에 10000까지 추가
		}
		endTime = System.nanoTime();
		System.out.println("ArrayList 걸린시간 :" + (endTime - startTime) + "ns");

		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			list2.add(0, String.valueOf(i));
			// LinkedList 리스트 객체에 10000까지 추가
		}
		endTime = System.nanoTime();
		System.out.println("LinkedList 걸린시간 :" + (endTime - startTime) + "ns");
	}
}

실행결과 LinkedList가  훨씬 빠른성능을 보여줍니다.

 

-ArrayList가 중간에 추가/삭제가 느린이유는

뒤쪽 인덱스들을 모두 1씩 증가 or 감소시키는 시간이 필요하여 그렇다.

구분	순차적으로 추가/삭제	중간에 추가/삭제	검색
ArrayList	빠르다	느리다	빠르다
LinkedList	느리다	빠르다	느리다