💡 배열 (Array)
- 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조다.
- 동일 타입의 데이터를 저장하며, 인덱스를 사용하여 값에 바로 접근할 수 있다.
- 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없다.
- 중간에 특정 요소를 삽입 및 삭제하는 경우, 특정 요소로부터 뒤에 있는 모든 요소들을 이동시켜주어야 한다.
- 삽입 및 삭제에 비용이 많이 들게된다.
배열의 시간 복잡도
| Operation | average case | worst case |
|---|---|---|
| read | O(1) | O(1) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
| search | O(n) | O(n) |
💡 연결 리스트 (Linked List)
- 리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조다.
- 포인터로 연결되어 있으므로 데이터 삽입/삭제 연산 속도가 빠르다.
- 리스트의 크기를 별도로 지정하지 않아도 된다.
- 인덱스가 없으므로 값에 접근하려면 Head 부터 순서대로 접근해야 한다.
연결 리스트의 시간 복잡도
| Operation | average case | worst case |
|---|---|---|
| read | O(n) | O(n) |
| insert | O(1) | O(1) |
| delete | O(1) | O(1) |
| search | O(n) | O(n) |
'자료구조·알고리즘' 카테고리의 다른 글
| 구간 합 (0) | 2023.06.23 |
|---|---|
| [자료구조] 이진 탐색 트리 (0) | 2022.10.07 |
| [자료구조] 트리 (0) | 2022.10.06 |