[자바] ArrayList와 LinkedList의 차이

ArrayList와 LinkedList는 Java에서 제공하는 Collection으로 List 인터페이스를 상속한다. 먼저 둘에 대해 알아보자.

 

ArrayList는 배열을 사용한다고 생각하면 되는데 데이터를 추가하거나 삭제할 때 이미 크기가 정해져 있어 임시 배열을 생성해서 데이터를 복사하는 방법을 사용하고 있다.

 

<ArrayList의 데이터 추가>

 

 

LinkedList는 각 노드의 앞과 뒤에 있는 노드의 주소로 연결되어 있어서 데이터를 추가하거나 삭제할 때 알고 있는 앞과 뒤쪽 노드의 주소 값만 바꿔주면 된다.

 

<LinkedList의 데이터 추가>

 

반응형

 

이제 앞에서 본 두 리스트의 차이점을 보자.

 

1. 검색

ArrayList는 각 데이터의 index를 가지고 있으므로 바로 검색할 수 있어 빠르다.

LinkedList는 제일 앞에 있는 데이터부터 차례대로 찾아야 하기 때문에 느리다.

 

2. 데이터 추가 & 삭제

데이터를 추가할 때 ArrayList는 임시로 배열을 만든 후 추가할 데이터의 위치의 앞까지는 그대로 데이터를 복사한 후 나머지 데이터가 추가된다. 때문에 메모리나 시간적인 측면에서 성능 저하를 일으킨다.

LinkedList는 데이터가 추가, 삭제되는 위치에 해당하는 노드의 주소값만 바꿔주면 되기 때문에 빠르게 바꿔줄 수 있다. 하지만 중간에 있는 데이터를 바꿀 때 추가, 삭제할 위치를 찾는 검색하는 시간이 있기 때문에 O(n)의 시간 복잡도를 가지게 되된다.