[알고리즘 개념] ArrayList와 LinkedList

ArrayList와 LinkedList는 둘 다 동적으로 크기가 조정되는 선형 자료구조로, 원소들을 순차적으로 저장하는 공통점이 있지만, 내부적인 구현과 동작 방식에서 차이가 있다.

 

ArrayList

인덱스를 통해 원소에 빠르게 접근할 수 있다. 리스트의 원소들이 메모리에 연속적으로 저장되어 있기 때문에 인덱스로 바로 접근이 가능하고 O(1)의 시간 복잡도를 가진다.

 

LinkedList

원소에 접근하기 위해서는 처음부터 해당 원소까지 순차적으로 찾아야 한다. 따라서 인덱스를 통한 접근이 느리며, 최악의 경우 O(n)의 시간 복잡도를 가진다.

 

삽입과 삭제

ArrayList : 중간에 원소를 삽입하거나 삭제할 경우, 해당 위치 이후의 원소들을 한 칸씩 미뤄야 하므로 O(n)의 시간 복잡도를 가집니다. 하지만 끝에 원소를 추가하는 경우(append)는 O(1)로 매우 빠르다.

LinkedList: 중간에 원소를 삽입하거나 삭제할 경우, 단순히 앞 노드와 뒤 노드를 연결해주면 되기 때문에 O(1)의 시간 복잡도를 가진다. 또한 리스트의 양 끝에 원소를 추가하는 경우도 O(1)로 빠르다.

 

메모리 사용

ArrayList: 내부적으로 배열을 사용하기 때문에, 원소들이 메모리에 연속적으로 저장되어 각 원소의 크기가 일정하다. 따라서 메모리 사용이 효율적이다.

LinkedList: 각 노드가 독립적으로 메모리에 저장되기 때문에 포인터 오버헤드가 있다. 따라서 같은 데이터를 저장하는 데에는 ArrayList보다 더 많은 메모리를 사용할 수 있다.

 

주요 용도

ArrayList: 데이터의 접근과 검색이 빈번한 경우에 유용하다. 인덱스를 기반으로 빠른 데이터 접근이 필요한 상황에서 성능이 좋다.

LinkedList: 데이터의 삽입과 삭제가 빈번한 경우에 유용하다. 리스트 중간에 원소를 삽입하거나 삭제하는 작업이 빠르고 효율적이다.