ArrayList vs LinkedList

List 인터페이스는 Java의 Collection을 확장한 인터페이스이다.

 

ArrayList와 LinkedList 모두 이 List 인터페이스의 구현체이다.

 

 

ArrayList

먼저, ArrayList는 배열(array)에 기반을 두고 있다.

 

index를 통한 요소 검색에 빠르다는 장점이 있지만, 요소의 추가 삭제가 느리다는 단점이 있다.

 

ArrayList의 일반적인 add() 메서드(맨 마지막 요소 뒤에 요소를 추가하는)를 통한 요소 삽입은

 

시간복잡도 Big-O 기준 O(1)의 시간복잡도를 가진다.

 

그러나, 특정 요소 사이에 요소를 삽입하거나 삭제하는 과정의 시간복잡도는 O(n)을 가진다.

 

 

LinkedList

LinkedList는 각 노드(Node)가 서로 연결되어 있는 형태이다.

 

링크를 건다라는 말을 많이 들어봤을 것이다. 링크를 걸면 그 링크를 타고 이동해서 특정 웹 페이지로 이동하게 된다.

 

LinkedList의 링크(Link) 또한 같은 맥락이다. Linked+List = 링크로 연결된 리스트라고 보면 편할 것 같다.

 

LinkedList의 장점으로는 요소의 삽입과 삭제가 O(1)의 시간복잡도를 가진다는 것이다.

 

단순히 삽입과 삭제의 과정이라면 그렇지만, 먼저 삽입과 삭제의 위치를 찾는 수순이 필요하다.

 

그 위치를 찾는 건 또 O(n)의 시간복잡도를 가진다. ( Java의 LinkedList의 경우 O(n/2)까지 보장됨 )

 

 

그럼 언제 어떤 걸 사용하는 게 적절할까?

만약 5개의 노드를 삽입한다고 가정해보자.

 

삽입하거나 삭제하는 경우

ArrayList는 O(n)*3

LinkedList는 O(3)

일 것이다.

 

한 번에 여러 개의 요소를 삽입하거나 삭제할 때는 LinkedList를,

하나의 요소를 삽입하거나 삭제할 때는 어떤 걸 써도 시간 복잡도는 비슷할 것 같다.

 

 

 

내용 중 틀린 부분이 존재할 수 있습니다.

피드백 주시면 감사하겠습니다.