1. 리스트와 배열
- 리스트 - 가장 기초적이고 오랫동안 사용된 자료구조
- 배열 - 리스트의 가장 널리 사용되는 구현 방법
2. 리스트의 개념
- 원소들을 한 줄로 나열한 구조 (특별한 순서를 따름)
리스트 ex) 전화번호부 , 앱 스토어 , 음악 플레이어 , 버스 도착 정보 , 포켓몬 고
3. 리스트의 정의
- 유한한 원소들의 나열
- 각 원소들은 인덱스에 대응됨 (index -> element) => 리스트의 가장 중요한 성질
4. 리스트의 구현 방법
- 배열(Array) : 인덱스에 기반한 구현
- 연속된 기억 공간에 원소를 저장
- 인접한 원소는 인접한 주소에 저장
- 연결 리스트(Linked list) : 포인터에 기반한 구현
- 메모리에 배열의 크기보다 더 큰 연속된 공간이 없을 때 사용
- 한 원소는 다음 원소를 가리키는 링크를 가지고 있음.
배열 연결 리스트
5. 2가지 리스트
- 정렬된 리스트
A = (2, 3, 5, 7, 11, 13, 17, 19) => 원소의 위치를 예측할 수 있음 => 원소 검색 연산에 유리
- 정렬되지 않은 리스트
B = (11, 19, 5, 2, 7, 13, 17, 3) => 원소의 위치를 예측할 수 없음 => 원소 추가 연산에 유리
*원소 검색 연산에 유리하도록 리스트를 정렬하는것이 중요함 => 여러가지 정렬 기법 공부
6. 배열의 연산
6-1. 검색
- 검색의 예시
- 검색의 종류
* 선형 검색 (linear search)
- 완전 검색 또는 순차 검색
- 배열의 첫 번째 원소부터 차례로 방문하면서 Key element와 동일한 원소가 있는지 확인
- 정렬되지 않은 배열에서도 적용할 수 있음
* 선형 검색 시간 복잡도
- 최악의 경우 : O(n)
- 평균의 경우 : O(n/2) -> O(n)
- 최선의 경우 : O(1)
* 이진 검색 (binary search)
- 분할 정복 알고리즘
- 배열의 중간 원소와 key element를 비교하여 배열을 분할함으로써 검색을 수행
- 정렬된 배열에서만 적용할 수 있음
* 이진 검색 시간 복잡도
- O(logn)
6-2. 추가
- 추가 (insert) 알고리즘
* 새로운 원소(x)를 배열 arr에 추가하는 과정
1. x를 추가할 위치를 결정 => O(k)
2. 추가할 위치의 원소를 옮겨서 공간을 확보 => O(n-k)
3. 원소를 추가 => O(1)
4. 배열의 크기를 증가 => O(1)
시간 복잡도 : O(n)
6-3. 제거
- 제거 (delete)의 정의
* 원소(x)를 배열 arr에서 제거하는 과정
1. 제거할 원소 (x)를 배열(arr)에서 찾음 => O(k)
2. 제거할 원소 뒤에 있는 원소들을 앞으로 이동 => O(n-k)
3. 배열의 크기를 감소 => O(1)
| 연산 | 함수 | 시간 복잡도 |
| 검색 (search) | linear_search(arr, x) | O(n) |
| binary_search(arr,x) | O(logn) | |
| 추가 (insert) | Insert(arr ,x) | O(n) |
| 제거 (delete) | delete(arr ,x) | O(n) |
'자료구조 C++' 카테고리의 다른 글
| 9. 우선 순위 큐 (Heap) (0) | 2021.02.07 |
|---|---|
| 8. 이진 탐색 트리 (binary search tree) (0) | 2021.02.03 |
| 7. 트리(tree) (0) | 2021.02.03 |
| 6. 정렬 (sorting) (0) | 2021.02.03 |
| 4. 연결 리스트 (linked list) (0) | 2021.02.03 |
