자료구조: CHAP 6 리스트 (1)
2021. 5. 10
순천향대학교 컴퓨터공학과
내용
리스트 개요
리스트의 배열 구현
단순 연결 리스트
표현
삽입
삭제
리스트 연산
응용: 다항식
원형 연결 리스트
이중 연결 리스트
리스트란?
일상생활에서의 리스트
리스트의 기본 연산
리스트에 새로운 항목을 추가한다(삽입 연산)
리스트에서 항목을 삭제한다(삭제 연산)
리스트에서 특정한 항목을 찾는다(탐색 연산)
리스트 ADT
∙ 객체: 0개 이상의 항목들로 구성된 순서 있는 모임
∙ 연산:
insert(list, pos, item) ::= pos 위치에 요소를 추가한다.
insert_last(list, item) ::= 맨 끝에 요소를 추가한다.
insert_first(list, item) ::= 맨 처음에 요소를 추가한다.
delete(list, pos) ::= pos 위치의 요소를 제거한다.
clear(list) ::= 리스트의 모든 요소를 제거한다.
get_entry(list, pos) ::= pos 위치의 요소를 반환한다.
get_length(list) ::= 리스트의 길이를 구한다.
is_empty(list) ::= 리스트가 비었는지를 검사한다.
is_full(list) ::= 리스트가 꽉 찼는지를 검사한다.
예제
다음 각 연산의 결과는 무엇인가? (항목의 위치는 0부터 시작한다고 가정)
insert_last(list, a);
insert_last(list b);
insert(list, 2, c);
insert(list, 1, d);
delete(list, 2);
list
리스트 구현
배열로 구현된 리스트
배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순 차적 표현(sequential representation)이라고 한다.
연산 예:
N의 항목을 리스트의 3번째 항목으로 삽입 리스트의 3번째 항목을 삭제
리스트 구현: 배열
리스트 표현
…
size array
typedef int element; // 항목 타입 정의
typedef struct { // 리스트 타입 정의
int array[MAX_LIST_SIZE]; // 항목을 포함 배열
int size; // 현재 리스트에 포함된 항목 개수
} ArrayListType;
리스트의 현재 크기
기초 연산
init(ArrayListType *L) // 리스트 초기화
is_empty(ArrayListType *L) // 리스트 검사
is_full(ArrayListType *L) // 리스트 검사
get_entry(ArrayListType *L, int pos)
// 특정 위치 원소 반환
print_list(ArrayListType *L) // 리스트 출력
typedef int element;
typedef struct {
int array[MAX_LIST_SIZE];
int size;
} ArrayListType;
삽입 연산 (1): 마지막 위치
insert_last(ArrayListType* list, int item) // 리스트 마지막 위치에 item을 삽입
{
}
typedef struct {
element array[MAX_LIST_SIZE];
int size;
} ArrayListType;
삽입 연산(2): 임의 위치
typedef struct {
element array[MAX_LIST_SIZE];
int size;
} ArrayListType;
insert(ArrayListType* list, int pos, int item) // pos 위치에 item을 삽입
{
}
// 배열이 꽉 차 있고, pos가 올바른 범위에 있는지 검사
삭제 연산(1): 임의 위치
int delete(ArrayListType* list, int pos) // pos 위치 값을 삭제하고, 삭제된 값을 반환 {
}
// pos가 올바른 범위에 있는지 검사
typedef struct {
int array[MAX_LIST_SIZE];
int size;
} ArrayListType;
isEmtpy(), isFull()
isEmpty() 연산
isFull()
boolean isEmpty(in ArrayListType list)
// 리스트가 비어 있으면 true, 그렇지 않으면 // false를 반환
{
}
typedef struct {
int array[MAX_LIST_SIZE];
int size;
} ArrayListType;
print_list()
print_list(in ArrayListType* list) // 리스트에 포함된 모든 항목을 출력 {
}
typedef struct {
int list[MAX_LIST_SIZE];
int length;
} ArrayListType;
리스트의 배열 구현: ArrayListType
int main(void) {
ArrayListType list;
init(&list);
insert(&list, 0, 10);
insert(&list, 0, 20);
insert(&list, 0, 30);
insert_last(&list, 40);
delete(&list, 0);
print_list(&list);
return 0;
}
연결 리스트란?
리스트의 항목들을 노드(node)에 분산하여 저장하고, 이들을 링크로 연결
노드는 데이타 필드와 링크 필드로 구성
데이타 필드: 리스트의 원소, 즉 데이타 값
링크 필드: 다른 노드의 주소값을 저장하는 장소 (포인터)
data link
연결 리스트 연산: 삽입과 삭제
연결 리스트 평가
장점
삽입, 삭제가 용이하다.
연속된 메모리 공간이 필요 없다.
크기 제한이 없다
단점
구현이 어렵고, 오류가 발생하기 쉽다.
메모리 공간 추가 부담
연결 리스트의 노드 구조
데이터 필드 + 링크 필드
연결 리스트의 동적 생성
노드를 동적 생성하고,링크 필드를 이용하여 노드들을 연결
헤드 포인터: 첫번째 노드를 가리키는 포인터
마지막 노드의 링크 필드는 NULL로 설정
연결 리스트의 종류
단순 연결 리스트
노드가 한 개의 링크 필드를 포함
모든 노드들이 링크 필드를 이용하여 연결
헤드포인터는 첫번째 노드를 가리킴
마지막 노드의 링크 값은 NULL
헤드포인터
10 20 NULL30 NULL
50 NULL
40NULL
노드 타입 정의
typedef int element;
typedef struct ListNode { // 노드 타입 정의 element data;
struct ListNode *link;
} ListNode;
기초 연산
공백 리스트 생성
ListNode *head = NULL
노드 생성
ListNode *p;
…
P = (ListNode *)malloc(sizeof(ListNode));
노드 연결
ListNode* head, p; // 리스트 변수 선언 // 첫번째 노드를 생성하고 초기화
// 두번째 노드를 생성하고 초기화
// 두 개 노드를 연결
head
data link
p data link
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
단순 연결 리스트의 연산
연산 함수 연산 의미
insert_first() 리스트의 시작 부분에 항목을 삽입 insert() 리스트의 중간 부분에 항목을 삽입 delete_first() 리스트의 첫 번째 항목을 삭제
delete() 리스트의 중간 항목을 삭제
print_list() 리스트를 방문하여 모든 항목을 출력
삽입 연산(1)
ListNode* insert_first(ListNode *head, int value)
// 노드를 생성하여 리스트의 첫번째 노드로 삽입후 반환 {
}
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
삽입 연산 (2)
ListNode* insert(ListNode *head, ListNode* pre, element value) // pre 뒤에 새로운 노드 삽입후 반환
{
}
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
NU LL
리스트 방문
리스트에 포함된 모든 노드를 순차적으로 방문
void print_list(ListNode* head) // head: 헤드 포인터
{
}
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
삭제 연산 (1)
ListNode* delete_first(ListNode *head)
// 리스트의 첫번째 노드를 삭제후, 리스트를 반환 {
// 리스트가 비어 있는 경우 고려 // 삭제된 노드는 회수
}
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
삭제 연산 (2)
ListNode* delete(ListNode *head, ListNode* pre) // pre의 다음 노드를 삭제한 후에 리스트 반환 {
// 삭제된 노드는 회수할 것
}
typedef struct ListNode { element data;
struct ListNode *link;
} ListNode;
테스트 프로그램
int main(void) {
ListNode *head = NULL;
// 노드 삽입
for (int i = 0; i < 5; i++) {
head = insert_first(head, i);
print_list(head);
}
// 노드 삭제
for (int i = 0; i < 5; i++) {
head = delete_first(head);
print_list(head);
}
return 0;
