(Java)ArrayList vs LinkedList 시간 복잡도

1) 서론

Selenium과 JSoup을 이용해서 크롤링을 하다 보면 데이터를 가지고 오고, 추가하는 작업을 많이 하게 됩니다. 그럴 때 반복적으로 사용하게 되는 것이 List 인터페이스와 For loop입니다. 

 

하지만 List 인터페이스를 사용할 때는 습관적으로 ArrayList 클래스만 사용하고 있었습니다. 하지만 List 인터페이스를 구현한 것은 LinkiedList 클래스도 추가로 있습니다. Vector도 있긴 하지만, ArrayList와 동일한 동작을 하며 자바 1.8 이상부터는 사용하지 않는 것으로 알고 있습니다. 

 

그래서 LinkedList와 ArrayList의 성능상 차이점은 뭐가 있을까 고민을 해봤습니다.

---

2) ArrayList vs LinkedList 기본적인 차이점

두 개의 가장 큰 차이점은 어떻게 자료를 저장하고, 찾느냐인 것 같습니다. 

 

ArrayList는 기본적으로 메모리의 주소를 바탕으로 저장이 됩니다. 즉 찾을 때도 어떤 작업이 없이, 주소를 찾는 계산식으로 금방 찾을 수 있습니다. 계산식은 (배열의 주소 + n * 데이터 크기)입니다. 컴퓨터처럼 연산 능력이 뛰어난 기계에게 이 정도쯤은 아무것도 아닙니다.

 

반면에 LinkedList는 데이터를 순차적으로 저장을 합니다. 긴 기차에서 각 호차마다 연결된 고리를 생각하시면 됩니다. 여기서 특정 데이터를 찾는 것에 큰 차이가 있습니다. ArrayList는 간단한 계산식이면 되지만, LinkedList는 1번부터 찾을 곳을 다 봐야 합니다. 간단히 생각해서 10호차에 타고 있는 어떤 손님을 찾기 위해서, 1호차부터 하나하나 훑어야 하는 겁니다. 

 

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

 

물론 LinkedList가 단점만 있는 것은 아닙니다. 데이터를 추가, 삭제할 때는 장점이 있습니다. 열차의 고리를 끊고, 연결하는 것처럼 데이터를 삭제할 때는 그 데이터만 삭제하고, 고리를 연결하면 됩니다. 추가를 할 때도 가운데에서 고리를 끊고, 추가하고, 다시 연결하면 됩니다.

 

ArrayList는 고리로 연결되지 않은 여러 호차를 생각하시면 됩니다. 중간에 특정 호차를 집어넣으려면 특정 위치 이후의 열차들을 뒤로 다 옮기고, 중간에 넣어야 합니다. 즉 한 칸씩 Shift를 하게 됩니다.

---

3) 연구

3. 1) ArrayList vs LinkedList 시간 복잡도 

■ n개의 요소에서 중간 지점에 1개의 데이터를 add/get 할 때

 

ArrayList

• add(index, element) - O(n) 
• get() - O(1)

 

LinkedList

• add() - O(n)
• get() - O(n)

 

ArrayList는 특정 위치에 한 개의 데이터를 추가하려면, 특정 위치 다음에 존재하는 데이터를 복사 후 한 칸 뒤에 붙여야 합니다. 즉 Shift를 하는 시간이 포함되기 때문에 O(n)의 시간 복잡도를 가집니다. 

 

LinkedList의 경우에는 일단 추가할 위치를 찾기 위해 처음부터 훑어야 하고, 그리고 추가합니다. 그렇기 때문에 마찬가지로 O(n)의 시간 복잡도를 가집니다.

 

get()에서는 ArrayList가 장점이 있습니다. 특정 위치의 주소를 계산 후 곧바로 찾아서 가지고 오면 되니까요. 

 

■ 순차적으로 n개의 데이터를 리스트 끝에 add 할 때 (For loop)

 

ArrayList 

• add(index, element) - O(n)

 

LinkedList

• add() - O(n)

 

For loop을 이용해 데이터를 리스트의 끝 부분에 계속해서 추가를 할 때의 경우 입니다.

 

OpenJDK를 바탕으로 ArrayList의 메모리 크기를 할당하지 않은 채로 위의 작업을 하게 된다면, 최초 Capacity는 10으로 할당이 됩니다. 그리고 데이터가 10개 보다 더 존재하는 경우에는, 새 배열을 만들고 복사 후 옮기게 됩니다. 이는 grow() 메서드를 통해서 이루어집니다.

 

이때 1개의 데이터가 더 필요하다고 해서, 1개만큼 더 만드는 것이 아니라 기존 배열의 50% 크기만큼 더 늘리게 됩니다. 

 

만약에 단순하게 1개가 더 필요하다고 해서, 1개씩 계속 늘리게 된다면 O(n^2) 같이 시간 복잡도가 급격히 증가하게 됩니다. 그렇기 때문에 자바에서는 더 필요한 숫자보다 더 많이 늘리고 있습니다. Java 11 API에서는 배열을 늘리는것은 상수시간만큼 시간복잡도가 증가한다고 나와있습니다. 그렇기 때문에 배열을 추가하는 과정이 있음에도 불구하고 O(n)이 됩니다. 

 

LinkedList의 경우에는 공간이 부족해서 새로 할당하는 경우가 없기 때문에 O(1)이 걸리고, 이것을 n번 반복하면 O(n)이 됩니다.

 

사실상 시간 복잡도에서는 차이가 없습니다.

 

3. 2) 실제 코드 비교

아래는 JSoup 파싱을 이용해서 데이터를 가져온 후 DB에 저장하는 코드입니다. 

 

여기서 최초에 웹 사이트에서 가져온 파싱 데이터를 배열에 저장 후 한꺼번에 DB에 저장하는 방식인데요. 파싱 할 데이터의 개수가 정해져 있지 않기 때문에 배열의 길이는 정해주지 않았습니다.

 

List 인터페이스를 이용해서 참조 변수를 만들어 준 것은 클래스를 이용하게 되면, ArryaList와 LinkedList를 바꿔 줄 때 변수의 클래스도 바꿔줘야 하기 때문입니다. 

 

주의해야 할 점은 파싱을 여러 페이지를 빠르게 하다 보면, 대상 되는 웹 사이트에서 새로고침 반복으로 인해 에러 페이지를 띄웁니다. 그렇기 때문에 다음 페이지 전 'Thread.sleep(5000)'을 걸어줬습니다. 즉 실제로 Thread.sleep 없이 반복되는 코드와는 실행시간에서 차이가 많은 것이며, 데이터의 양에 따라서도 다를 것입니다. 그냥 동일한 환경에서의 차이점만 봐주세요.

 

 

각각의 List는 한 페이지씩 크롤링 한 데이터를 저장하며, 총 8페이지 데이터를 저장합니다.
그 후 For문으로 DB에 8페이지 전체 데이터를 한 번에 저장합니다.

 

 

약 950개 데이터, 3회 평균 실행 시간 (initial capacity 설정 X)

• LinkedList - 141337 ms
• ArrayList - 147572 ms

 

실제로 3회를 반복했을 때 평균 실행 시간은 LinkedList가 6000ms 정도 더 빨랐습니다. 생각보다 큰 차이입니다. 만약에 950개가 아니라, 950,000개의 데이터가 있었다면 더 많은 차이가 났을 것이라는 추측을 할 수 있습니다. 

 

하지만 위의 코드는 initial capacity를 설정하지 않았습니다. ArrayList는 따로 설정하지 않는다면 initial capacity는 10인데요. LinkedList와 다른점 입니다.

 

Initial capacity를 1000으로 넉넉하게 준 뒤 실행을 해보니 평균 119101ms 걸렸습니다. LinkedList와 같은 시간복잡도를 가지지만, 더 빠른 속도를 보여줍니다.

---

4) 그래서 어떤 것을 사용해야 할까?

제가 나름대로 고민 후 내린 결론입니다. 

 

LinkedList의 경우에는 Head, Tail 같은 부가적인 정보를 가지고 있어야 하기 때문에 추가적인 메모리 소요를 하게 됩니다. 이때 부가적인 정보를 가지고 있는것은 위에서 언급한 지역성 문제와도 연결됩니다.

 

그럼에도 불구하고 메모리 할당 크기를 지정해주지 않는 상태, 얼마의 데이터가 입력이 될지 모르는 상태에서는 LinkedList가 더 유리하다고 생각합니다. 왜냐하면 LinkedList는 단순히 앞뒤 주소만 가진 채로 연결만 해주면 됩니다. 공간이 부족해 새로 할당하는 경우가 없습니다. 즉 배열을 resize 하는 동작이 필요 없습니다.

 

ArrayList는 위와 같은 경우에 배열을 resize 하는 과정을 거칩니다. 시간 복잡도는 동일하지만, resize 하는 시간 때문에 LinkedList 보다 느리지 않을까 생각을 합니다. 

 

하지만 결론은 ArrayList에 initial capacity를 넉넉히 할당을 해주는것으로 해결했습니다. 그러면 최초 capacity인 10보다는 resize 동작이 줄어들기 때문에, 좀 더 빠른 접근을 할 수 있습니다.

 

또한 만약에 대략적으로 몇 개의 데이터를 넣을지 추측을 할 수 있다면 ensureCapacity 메서드를 활용해서, 배열의 크기를 지정해주는 것도 좋다고 생각합니다. 그렇더라도 시간 복잡도는 동일하지만, 배열의 resize를 줄일 수 있을 것입니다.

---

5) 수정 사항

2021년 2월 26일

실제 코드 비교 추가

 

2021년 2월 27일

List 인터페이스 사용 이유 추가

 

2021년 3월 02일

참고사항 및 인용 추가

 

2021년 3월 14일

ArrayList capacity 추가

---

6) 참고 문헌

github.com/openjdk/jdk