LinkedList와 ArrayList의 속도차이 및 용도

Java에서 LinkedList와 ArrayList는 둘 다 List 인터페이스를 구현한 컬렉션 클래스이며, 각각의 특징과 시간 복잡도가 다르다.

ArrayList는 내부적으로 배열을 사용하므로 인덱스를 기반으로 빠르게 요소에 접근할 수 있습니다. 따라서 요소를 읽는 작업(get)에 대한 시간 복잡도는 O(1) 이다. 그러나 배열의 크기를 늘리거나 줄일 때는 새로운 배열을 생성하고 기존 배열의 요소를 복사해야 하므로, 크기를 변경하는 작업(add, remove)에 대한 시간 복잡도는 O(n)이다. 그리고 중간에 요소를 추가하거나 삭제하는 작업은 빠르지 않다.

LinkedList는 각 요소가 이전 요소와 다음 요소에 대한 참조를 가지고 있는 연결 리스트 구조를 사용함. 따라서 인덱스를 사용해 요소에 접근하는 작업은 리스트의 길이에 비례하여 시간이 걸린다. 하지만 요소를 추가하거나 삭제할 때에는 그 요소와 인접한 요소들의 참조만 변경하면 되므로, 시간 복잡도는 O(1) 입니다. 따라서 중간에 요소를 추가하거나 삭제하는 작업에 유리하다.

따라서, ArrayList는 요소를 읽는 작업이 빈번하고, 크기가 변하지 않는 경우에 유리하다. 반면에 LinkedList는 요소를 추가하거나 삭제하는 작업이 빈번하고, 리스트의 길이가 변경되는 경우에 유리하다.

또한 ArrayList는 요소를 읽는 작업은 빠르지만, 중간에 요소를 추가하거나 삭제하는 작업은 많은 요소를 이동해야 하므로 비효율적입니다. 따라서 중간에 요소를 추가하거나 삭제하는 작업이 많은 경우 LinkedList를 사용하는 것이 더 효율적이다.

하지만, LinkedList는 포인터(참조)를 저장해야 하므로, 메모리 사용량이 ArrayList보다 크고, 요소에 대한 접근 시간이 더 많이 걸립니다. 따라서 요소를 읽는 작업이 빈번한 경우에는 ArrayList가 더 효율적입니다.

따라서 상황에 따라 적절한 자료구조를 선택하여 사용하는 것이 중요합니다.

 

 

 

 

'CS' 카테고리의 다른 글

빌더 패턴(Builder Pattern)  (0) 2023.07.23
Java Optional이란?  (0) 2023.07.23
JAVA - StringBuilder와 System.out.print의 속도차이  (0) 2023.07.14
FrameWork VS Library 차이점  (0) 2023.07.13