[자료구조] Array, ArrayList, LinkedList 차이 (시간복잡도, 각각 언제 써야할까?)

목차

• Array
• ArrayList
• LinkedList
• Array, ArrayList, LinekdList 시간복잡도
• Array, ArrayList, LinedList 언제 써야 할까?

 

---

1. Array

배열은 선언 시에 배열의 크기가 결정되고, 이후 변경하지 못해 고정적이다. 인덱스라는 데이터의 논리적 위치와 디스크에 저장되는 물리적 위치가 동일하며, 인덱스를 알고 있다면 빠르게 접근할 수 있다.

 

(특징)

• 크기가 고정적
• 논리적 위치와 물리적 위치가 동일
• 조회 시 인덱스를 알고 있다면 O(1)의 시간복잡도를 가짐
• 데이터의 개수가 제한되어 있고, 조회가 빈번한 경우에 배열을 사용

(장점)

• 캐시에 데이터가 존재할 가능성이 큼
• 조회 속도가 빠름

(단점)

• 배열의 크기가 한정되어 있음

 

---

2. ArrayList

ArrayList는 크기가 가변적인 배열이라고 말할 수 있다. 내부적으로는 배열을 사용하는데, 만약 정해진 크기보다 더 많은 개수가 입력될 경우 1.5배씩 사이즈를 늘린다.

 

(특징)

• 크기가 가변적
• 논리적 위치와 물리적 위치가 동일
• 조회 시 인덱스를 알고 있다면 O(1)의 시간복잡도를 가짐
• 데이터의 개수를 모르고, 조회가 빈번한 경우에 ArrayList를 사용

(장점)

• 캐시에 데이터가 존재할 가능성이 큼
• 조회 속도가 빠름
• 배열에 비해 데이터 개수를 신경 쓰지 않아도 됨
• LinkedList에 비해 더 적은 메모리 공간을 사용함

(단점)

• 배열의 크기를 넘어설 경우, 새로운 배열 생성과 데이터 이동으로 속도가 느림

 

---

3. LinkedList

LinkedList는 연속적이지 않는 데이터들이 연결되어 있는 자료구조이다. 데이터와 함께 다음 노드의 주소를 가지고 있는데, 조회 시에는 순차적으로 접근해야 하므로 속도가 느리고, 삽입 및 삭제 시에는 다음 데이터를 가리키는 주소 값을 변경하면 되므로 속도가 빠르다.

 

(특징)

• 크기가 가변적
• 논리적 위치와 물리적 위치가 다름
• 조회 시 순차적인 접근으로 O(n)의 시간복잡도를 가짐
• 삽입 및 삭제 시 O(1)의 시간복잡도를 가짐

(장점)

• 삽입 및 삭제에 대한 속도가 빠름

(단점)

• 순차적 접근으로 조회 속도가 느림
• 포인터 사용으로 저장 공간 낭비

 

---

4. Array, ArrayList, LinkedList 시간복잡도

	Array	ArrayList	LinkedList
처음 위치 삽입	O(n)	O(n)	O(1)
마지막 위치 삽입	O(1)	O(1) 혹은 O(n)	O(1)
중간 위치 삽입	O(n)	O(n)	O(n)
처음 위치 삭제	O(n)	O(n)	O(1)
마지막 위치 삭제	O(1)	O(1) 혹은 O(n)	O(1)
특정 위치 삭제	O(n)	O(n)	O(n)
조회	O(1)	O(1)	O(n)
수정	O(1)	O(1)	O(n)
탐색	O(n)	O(n)	O(n)

 

---

5. Array, ArrayList, LinkedList 언제 써야 할까?

 

데이터 검색을 자주 한다면 Array와 ArrayList

 

데이터 삽입, 삭제를 자주 한다면 LinkedList