[Java] ArrayList 와 LinkedList 차이점과 속도 비교해보기!

2020-12-23

---

ArrayList와 LinkedList는 언뜻 보기에는 인덱스를 이용해 객체를 저장하여 서로 비슷해 보인다. 하지만 두 list클래스들의 장단점은 명확하다. 오늘은 이 둘의 장단점을 알아보도록 하자.

---

구체적인 예를 들어 살펴보겠다. 우선 ArrayList의 경우 아래와 같이 처음에 6개의 객체가 있다고 가정해보자. 인덱스는 그러면 0부터 5번까지 객체가 들어 있을 것이다. 근데 아래 이미지와 같이 1번째의 객체가 remove() 메서드 (list.remove(1))를 통해서 제거가 된다면, 해당 제거된 인덱스 뒤에 위치한 객체들이 하나씩 앞으로 당겨져 온다.  

그 결과 리스트의 사이즈는 5가 될 것이며, 인덱스 번호는 0 ~ 4번으로 변경되게 된다. 때문에 순서대로 객체를 추가하거나, 객체를 검색할때에는 속도가 빠르다. 반면에 중간에 위치한 객체를 제거하게 되면, 전체 list가 한 칸씩 움직이게 되어 계속해서 객체를 중간에 추가 삭제 작업이 필요한 경우에는 효율이 떨어진다고 볼 수 있다.

---

이제 다른 하나인 LinkedList 를 살펴보자. 예제와 전제조건은 기존ArrayList와 동일하다. LinkedList의 경우 하나의 객체가 삭제되더라도, 나머지 모든 객체의 위치를 당겨오지 않고 앞뒤의 인덱스 링크만 변경되기 때문에, 중간 추가 / 삭제 작업에서 

ArrayList 보다 빠른 성능을 보이게 된다.

---

이제 코드로 그 속도가 얼마나 차이가 나는지 살펴보자.

package List;

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

public class main {

	public static void main(String[] args) {		List<String> listA = new ArrayList<>();
		List<String> listL = new LinkedList<>();	
		
        long start;
		long end; 
		//시작시간과 끝나는 시간 저장변수
		
		start = System.nanoTime();
		for(int i = 0; i < 20000; i++) {
			listA.add(0, String.valueOf(i));
			//0번째 위치를 계속해서 i값을 변경하는 작업 실시
		}
		end = System.nanoTime();
		System.out.println("ArrayList 지속 변경 총시간  :" + (end - start) + "나노초");
		
		
		start = System.nanoTime();
		for(int i = 0; i < 20000; i++) {
			listL.add(0, String.valueOf(i));
			//0번째 위치를 계속해서 i값을 변경하는 작업 실시
		}
		end = System.nanoTime();
		System.out.println("LinkedList 지속 변경 총시간 :" + (end - start) + "나노초");
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////		
		
		start = System.nanoTime();
		for(int i = 0; i < 20000; i++) {
			listA.add(String.valueOf(i));
		}
		end = System.nanoTime();
		System.out.println("ArrayList 순차적 추가 총시간 :" + (end - start) + "나노초");
		
		start = System.nanoTime();
		for(int i = 0; i < 20000; i++) {
			listL.add(String.valueOf(i));
		}
		end = System.nanoTime();
		System.out.println("LinkedList 순차적 추가 총시간 :" + (end - start) + "나노초");
		
	}

}

위의 코드는 각 리스트의 2만의 루핑을 돌면서 ArrayList / LinkedList 의 총 작업속도를 측정하는 코드이다.

 

처음은 중간 추가 / 삭제 작업에 따른 ArrayList / LinkedList의 속도 차이를 비교한 것이며, 다음은 순차적 추가 / 삭제 작업에 따른 속도 차이를 비교한 것이다. 결과 값은 아래와 같다.

지속적인 변경 즉 중간에 추가 /삭제 작업의 경우 LinkedList가 ArrayList가 약 10배 가량 빠른 것을 확인할 수 있다. 반면에 순차적 추가 / 삭제 작업의 경우 ArrayList가 LinkedList보다 약 2배 정도 빠른 것을 확인할 수 있다.

(컴퓨터의 성능과 작업 환경에 따라 속도는 상이할 수 있다.)