ArrayList와 LinkedList의 차이 / Stringbuilder

ArrayList vs LinkedList

 

ArrayList는 메모리주소를 바탕으로 저장된다. 주소를 찾는 계산식(배열의 주소 + n * 데이터 크기)을 사용하여 빠르게 찾을 수 있다.

 

반면에 LinkedList는 데이터를 순차적으로 저장한다. 특정 데이터를 찾기 위해서는 1번부터 하나씩 찾아야 한다.

10개의 노드가 연결되어 있다면 1번 노드부터 한 칸씩 다 확인을 하며 찾아야 한다.

 

또한 LinkedList는 지역성(locality of reference) 측면에서도 불리하다. 왜냐면 ArrayList는 데이터를 연속적인 묶음으로 저장하지만 LinkedList는 불연속적으로 저장 후 연결하는 방식이기 때문이다. 당연히 다음 데이터에 대한 주소를 가지고 있다고 하더라도 접근하는데 시간이 걸릴 수 밖에 없다.

 

LinkedList의 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다는 점이다.

 

* 시간복잡도

	add	remove	get	contains	iterator.remove
ArrayList	O(1)	O(n)	O(1)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)	O(1)

 

ArrayList

자바에서는 배열의 길이가 고정되어 있기 때문에 배열을 만들 때 배열 길이를 함께 지정해야 한다.

동적 가변 크기 기능을 사용하고 싶을때는 보통 ArrayList를 사용한다.

ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서 O(1)의 접근 시간을 유지한다.

 

* resize

통상적으로 배열이 가득 차는 순간 배열의 크기를 두 배로 늘린다. 크기를 두 배로 늘리는 시간은 O(n)이지만 자주 발생하지 않기 때문에 상환 입력 시간(amortized insertion time)으로 계산했을 때 여전히 O(1)이 된다.

 

StringBuilder

만약 문자열의 리스트가 주어졌을 때 이 문자열들을 하나로 이어붙이려고 하면 수행 시간은 어떻게 될까?

예)

String sentence = "";
for(String w : words) {
	sentence = sentenct + w;
}

문자열을 이어붙일 때마다 두 개의 문자열을 읽은 뒤 문자를 하나하나 새로운 문자열에 복사해야 한다.

처음에는 x(w.length)개, 두 번째는 2x개, 세 번째는 3x개... n번째는 nx개의 문자를 복사해야 한다. - (참고 : String은 불변)

 

따라서 총 수행 시간은 O(x+2x+...+nx) = O(xn^2) = O(n^2)이 된다.

 

이 문제는 StringBuilder를 사용하여 해결할 수 있다.

StringBuilder는 단순하게 가변 크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게 한다.

 

StringBuilder sentence = new StringBuilder();
for(String w : words) {
	sentence.append(w);
}

 

 

 

 

 

 

References

https://yeon-kr.tistory.com/152

Cracking the coding interview 6/E, 게일 라크만 맥도웰