내부 구현 측면에서 arraylist와 linkedlist의 차이

[3Juhwan]

.

[alstn113]

ArrayList와 LinkedList는 자바 컬렉션 프레임워크의 두 가지 주요 리스트 구현체입니다.
내부 구현 측면에서는 다음과 같은 차이가 있다.

1. 내부 자료 구조

   • ArrayList는 배열(Array)을 기반으로 내부적으로 요소를 저장합니다. 요소의 인덱스로 직접 접근할 수 있습니다.
   • LinkedList: 연결 리스트(Linked List)를 기반으로 내부적으로 요소를 저장합니다. 각 요소는 데이터와 다음 요소를 가르키는 포인터(참조)로 구성됩니다.

2. 데이터 접근 시간

   • ArrayList: 요소에 대한 랜덤 액세스(인덱스를 통한 접근)가 빠릅니다. 인덱스로 요소를 찾기 때문에 시간 복잡도는 O(1)입니다.
   • LinkedList: 요소에 대한 랜덤 액세스가 느립니다. 특정 인덱스로 이동하기 위해 처음부터 순회해야 하므로 시간 복잡도는 O(n)입니다.

3. 데이터 삽입 및 삭제 시간:

   • ArrayList: 중간에 요소를 삽입하거나 삭제할 경우 해당 요소 뒤의 모든 요소를 이동해야 하므로 시간 복잡도는 O(n)입니다.
   • LinkedList: 중간에 요소를 삽입하거나 삭제할 경우 해당 요소의 앞뒤 포인터만 조정하면 되므로 시간 복잡도는 O(1)입니다.

따라서 데이터의 삽입, 삭제가 빈번한 경우에는 LinkedList가 유리하며, 데이터의 접근이 빈번한 경우에는 ArrayList가 유리합니다.

[GIVEN53]

	ArrayList	LinkedList
내부 자료구조	배열을 기반으로 요소 저장	연결 리스트로 요소 저장 각 요소는 이전 요소와 다음 요소를 참조
인덱스로 데이터 접근	O(1) 각 데이터의 인덱스를 가지고 있어 무작위 접근	O(N) 데이터를 찾기 위해 첫 번째부터 순차 접근
첫 번째 인덱스 삽입/삭제	O(N) 나머지 요소를 하나씩 뒤로 이동시켜야 함	O(1)
마지막 인덱스 삽입/삭제	O(1) 공간 부족으로 배열 리사이징 처리 시 O(N)	O(1)
중간 인덱스 삽입/삭제	O(N)	인덱스로 데이터 접근 O(N) + O(1)

• 조회가 많다 -> ArrayList
• 삽입/삭제가 많다 -> LinkedList