3. 리스트 - 1
3.1 리스트 추상 데이터 타입
* 리스트
- 순서를 가진 항목들의 모임 ↔ 집합 (항목간의 순서 개념 無)
ex) 요일, 한글 자음의 모임, 카드, 핸드폰의 문자 메시지 리스트
* 리스트 ADT(추상 데이터 타입)
- 객체 : n개의 element 형으로 구성된 순서있는 모임
- 연산
1. add_last(list, item) : 맨 끝에 요소 추가
2. add_first(list, item) : 맨 앞에 요소 추가
3. add(list, pos, item) : pos 위치에 요소 추가
4. delete(list, pos) : pos 위치의 요소 제거
5. clear(list) : 리스트의 모든 요소 제거
6. replace(list, pos, item) : pos 위치의 요소를 item으로 변경
7. is_in_list(list, item) : item이 리스트 안에 있는지 검사
8. get_entry(list, pos) : pos 위치의 요소를 반환
9. get_length(list) : 리스트의 길이 반환
10. is_empty(list) : 리스트가 비었는지 검사
11. is_full(list) : 리스트가 꽉찼는지 검사
12. display(list) : 리스트의 모든 요소 출력
* 리스트 구현 방법
배열을 이용하는 방법 |
연결리스트를 이용하는 방법 |
- 구현이 간단 - 삽입, 삭제 시 오버헤드 (처리 시간 느림) - 항목의 개수 제한 - 메모리 차지 小 |
- 구현이 복잡 - 삽입, 삭제가 효율적 - 크기 제한 X - 메모리 차지 大 |
3.2 배열로 구현된 리스트
* 배열리스트의 특징
1. 1차원 배열에 항목들을 순서대로 저장
2. 삽입연산 : 삽입위치 다음의 항목들을 이동하여야 함
3. 삭제연산 : 삭제위치 다음의 항목들을 이동하여야 함
* is_empty 연산과 is_full 연산의 구현
// 리스트가 비어있으면 1 반환 // 그렇지 않으면 0 반환 int is_empty(ArrayListType *L) { return L->length == 0; } |
// 리스트가 가득 차 있으면 1 반환 // 그렇지 않으면 0 반환 int is_full(ArrayListType *L) { return L->length == MAX_LIST_SIZE; } |
* 삽입 연산 구현
void add(ArrayListType *L, int position, element item) { if(!is_full(L) && (position >= 0) && (position <= L->length)) { int i; for(i = (L->length-1); i >= position; i--) L->list[i+1] = L->list[i]; L->list[position] = item; L->length++; } } |
* 삭제 연산 구현
void delete(ArrayListType *L, int position) { int i; element item; if(position < 0 || position >= L->length) error("위치 오류"); item = L->list[position]; for(i = position; i < (L->length-1); i++) L->list[i] = L->list[i+1]; L->length--; return item; } |
3.3 연결 리스트
* 노드
- 리스트의 항목들을 노드라고 하는 곳에 분산하여 저장
- 다음 항목을 가리키는 주소도 같이 저장
- 데이터 필드(데이터 값을 저장하는 곳)와 링크 필드(다른 노드의 주소값을 저장하는 곳, 포인터)로 구성
- 실제 메모리 안에서 물리적 순서가 리스트 내의 논리적 순서와 일치할 필요 없음
- 동적 메모리 할당 기능을 이용하여 노드 생성
* 헤드 포인터
- 연결 리스트의 맨 처음 노드를 가리키는 포인터
* 연결리스트의 장단점
- 장점
1. 삽입, 삭제 용이
2. 연속된 메모리 공간 필요 X
3. 크기 제한 X
- 단점
1. 구현 어려움
2. 오류 발생 가능성 높음
* 연결 리스트의 종류
1. 단순 연결 리스트
2. 원형 연결 리스트
3. 이중 연결 리스트
* 노드의 정의와 생성
- 노드 : 데이터 필드와 링크필드로 구성, 구조체로 정의
typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; |
- 노드의 생성 : 동적 메모리 할당
ListNode *p1; p1 = (ListNode *)malloc(sizeof(ListNode)); |
* 데이터 필드와 링크 필드 설정
p1->data = 10; p1->link = NULL; |
* 두번째 노드 생성과 첫번째 노드와의 연결
ListNode *p2; p2 = (ListNode *)malloc(sizeof(ListNode)); p2->data = 20; p2->link = NULL; p1->link = p2; |
* 삽입 함수
- 프로토타입
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node); // phead : 헤드 포인터 head에 대한 포인터, 함수 안에서 헤드 포인터를 변경해야 하므로 필요 // p : 삽입될 위치의 선행노드를 가리키는 포인터, 이 다음 노드에 삽입 // new_node : 새로운 노드를 가리키는 포인터 |
- 삽입의 경우
1. head가 NULL인 경우 : 공백 리스트에 삽입
2. p가 NULL인 경우 : 리스트의 맨 처음에 삽입
3. 일반적인 경우 : 리스트의 중간에 삽입
- 삽입 연산 코드
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) { if(*phead == NULL) { new_node->link = NULL; *phead = new_node; } else if(p == NULL) { new_node->link = *phead; *phead = new_node; } else { new_node->link = p->link; p->link = new_node; } } |
* 삭제 함수
- 프로토타입
void remove_node(ListNode **phead, ListNode *p, ListNode *removed); // phead : 헤드 포인터 head에 대한 포인터, 함수 안에서 헤드 포인터를 변경해야 하므로 필요 // p : 삭제될 노드의 선행 노드를 가리키는 포인터 // removed : 삭제될 노드를 가리키는 포인터 |
- 삭제의 경우
1. p가 NULL인 경우 : 맨 앞의 노드를 삭제
2. p가 NULL이 아닌 경우 : 중간 노드를 삭제
- 삭제 연산 코드
void remove_node(ListNode **phead, ListNode *p, ListNode *removed) { if(p == NULL) *phead = (*phead)->link; else p->link = removed->link; free(removed); } |