Data Structure Chapter 4. 리스트 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr
리스트추상데이터타입
리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트 3
리스트의연산 새로운항목을리스트의끝, 처음, 중간에추가한다. 기존의항목을리스트의임의의위치에서삭제한다. 모든항목을삭제한다. 기존의항목을대치한다. 리스트가특정한항목을가지고있는지를살핀다. 리스트의특정위치항목을반환한다. 리스트안의항목개수를센다. 리스트가비었는지, 꽉찼는지를체크한다. 리스트안의모든항목을표시한다. 4
리스트 ADT 객체 : n 개의 element 형으로구성된순서있는모임 연산 add_last(list, item) ::= 맨끝에요소를추가한다. add_first(list, item) ::= 맨처음에요소를추가한다. add(list, pos, item) ::= pos 위치에요소를추가한다. delete(list, pos) ::= pos 위치의요소를제거한다. clear(list) ::= 리스트의모든요소를제거한다. replace(list, pos, item) ::= pos 위치의요소를 item로바꾼다. is_in_list(list, item) ::= item이리스트안에있는지를검사한다. get_entry(list, pos) ::= pos 위치의요소를반환한다. get_length(list) ::= 리스트의길이를구한다. is_empty(list) ::= 리스트가비었는지를검사한다. is_full(list) ::= 리스트가꽉찼는지를검사한다. display(list) ::= 리스트의모든요소를표시한다. 5
리스트 ADT 사용예 (1/2) a a b a b c addtail(list1,a) addlast(list1, a) addtail(list1,b) addlast(list1, b) add(list1,2,c) addlast(list1, c) a d b c a d c a e c add(list1,1,d) delete(list1,2) replace(list1,1,e) 6
리스트 ADT 사용예 (2/2) 코드예시 main() int i, n; // list2를생성한다 : 구현방법에따라약간씩다름 ListType list2; add_last (&list2," 마요네즈 ); // 리스트의포인트를전달 add_last(&list2," 빵 ); add_last(&list2," 치즈 ); add_last(&list2," 우유 ); n = get_length(&list2); printf(" 쇼핑해야할항목수는 %d입니다.\n", n); for(i=0;i<n;i++) printf("%d항목은 %s입니다.\n, i, get_entry(&list2,i)); 7
리스트구현방법 배열을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트를이용하는방법 구현복잡 연속된메모리공간이필요없음 삽입, 삭제가효율적 크기가제한되지않음 리스트 ADT a b c 배열을이용한구현 a b c 연결리스트를이용한구현 a b c NULL 8
배열로구현된리스트
배열로구현된리스트 1 차원배열에항목들을순서대로저장 L=(A, B, C, D, E) 0 1 2 3 4 5 6 7 8 9 A B C D E 삽입연산 : 삽입위치다음의항목들을이동하여야함. N 0 1 2 3 4 5 6 7 8 9 A B C D E 삭제연산 : 삭제위치다음의항목들을이동하여야함 C 0 1 2 3 4 5 6 7 8 9 A B D E 10
ArrayListType 의구현 (1/2) 항목들의타입은 element 로정의 list 라는 1 차원배열에항목들을차례대로저장 length 에항목의개수저장 typedef int element; typedef struct int list[max_list_size]; int length; ArrayListType; // 배열정의 // 현재배열에저장된항목들의개수 // 리스트초기화 void init(arraylisttype *L) L->length = 0; 11
ArrayListType 의구현 (2/2) is_empty 연산과 is_full 연산의구현 // 리스트가비어있으면 1 을반환 // 그렇지않으면 0 을반환 int is_empty(arraylisttype *L) return L->length == 0; // 리스트가가득차있으면 1 을반환 // 그렇지많으면 1 을반환 int is_full(arraylisttype *L) return L->length == MAX_LIST_SIZE; 12
ArrayListType 의삽입연산 add 함수 배열이포화상태인지, 삽입위치가적합한범위인지검사 삽입위치다음에있는자료들을한칸씩뒤로이동 // position: 삽입하고자하는위치 // item: 삽입하고자하는자료 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++; N 0 1 2 3 4 5 A B C D E A B C D E A B C D E A B C D E A B N C D E position length-1 13
ArrayListType 의삭제연산 delete 함수 삭제위치를검사한다. 삭제위치부터맨끝까지의자료를한칸씩앞으로이동 // position: 삭제하고자하는위치 // 반환값 : 삭제되는자료 element delete(arraylisttype *L, int position) int i; element item; 0 1 2 3 4 5 A B C D E C A B D E position length-1 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; A B D E A B D E 14
연결리스트
연결리스트 노드 (node) < 항목, 주소 > 쌍 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 다음항목을가리키는주소도같이저장 노드는데이타필드와링크필드로구성 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) 메모리안에서의노드의물리적순서가리스트의논리적순서와일치할필요없음 16
연결리스트의구조 구조 노드 = 데이터필드 + 링크필드 data link 헤드포인터 (head pointer): 리스트의첫번째노드를가리키는변수 헤드포인터 NULL 노드의생성 : 필요할때마다동적메모리생성이용하여노드를생성 운영체제 요구 동적생성 헤드포인터 NULL 17
연결리스트의종류 단순연결리스트 헤드포인터 NULL 원형연결리스트 헤드포인터 이중연결리스트 헤드포인터 18
단순연결리스트 단순연결리스트 하나의링크필드를이용하여연결 마지막노드의링크값은 NULL 헤드포인터 10 20 NULL 30 NULL 40 NULL 50 NULL 19
단순연결리스트의구현 (1/2) 데이터필드 : 구조체로정의 링크필드 : 포인터사용 typedef int element; typedef struct ListNode element data; struct ListNode *link; ListNode; 노드의생성 : 동적메모리생성라이브러리 malloc 함수이용 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); 20
단순연결리스트의구현 (2/2) 데이터필드와링크필드설정 p1->data = 10; p1->link = NULL; p1 10 NULL 두번째노드생성과첫번재노드와의연결 ListNode *p2; p2 = (ListNode *)malloc(sizeof(listnode)); p2->data = 20; p2->link = NULL; p1->link = p2; p1 10 20 NULL 헤드포인터 (head pointer) : 연결리스트의맨처음노드를가리키는포인터 21
단순연결리스트의삽입연산 (1/5) 삽입연산 before 10 30 after before 10 30 after 20 new 20 new insert_node(l, before, new) if L = NULL then L new else new.link before.link before.link new 22
단순연결리스트의삽입연산 (2/5) 삽입함수의프로토타입 헤드포인터가함수안에서변경되므로헤드포인터의포인터필요 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) phead: 헤드포인터 head 에대한포인터 p: 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입된다. new_node: 새로운노드를가리키는포인터 삽입의 3 가지경우 head가 NULL인경우 : 공백리스트에삽입 p가 NULL인경우 : 리스트의맨처음에삽입 일반적인경우 : 리스트의중간에삽입 23
단순연결리스트의삽입연산 (3/5) head 가 NULL 인경우 현재삽입하려는노드가첫번째노드 head new_node NULL p 가 NULL 인경우 새로운노드를리스트의맨앞에삽입 head NULL NULL new_node NULL 24
단순연결리스트의삽입연산 (4/5) head 와 p 가 NULL 이아닌경우 가장일반적인경우 new_node의 link에 p->link값을복사 p->link가 new_node를가리키도록함 p NULL new_node (2) (1) 25
단순연결리스트의삽입연산 (5/5) 삽입연산의코드 // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // new_node : 삽입될노드 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) if( *phead == NULL ) new_node->link = NULL; *phead = new_node; else if( p == NULL ) else new_node->link = *phead; *phead = new_node; // 공백리스트인경우 // p 다음에삽입 new_node->link = p->link; p->link = new_node; // p 가 NULL 이면첫번째노드로삽입 26
단순연결리스트의삭제연산 (1/4) 삭제연산 before removed after 10 20 30 before removed after 10 20 30 remove_node(l, before, removed) if L NULL then before.link removed.link destroy(removed) 27
단순연결리스트의삭제연산 (2/4) 삭제함수의프로토타입 //phead: 헤드포인터 head 의포인터 //p: 삭제될노드의선행노드를가리키는포인터 //removed: 삭제될노드를가리키는포인터 void remove_node(listnode **phead, ListNode *p, ListNode *removed) 삭제의 2 가지경우 p 가 NULL 인경우 : 맨앞의노드를삭제 p 가 NULL 이아닌경우 : 중간노드를삭제 28
단순연결리스트의삭제연산 (3/4) p 가 NULL 인경우 연결리스트의첫번째노드를삭제 list NULL removed p 가 NULL 이아닌경우 removed 앞의노드인 p 의링크가 removed 다음노드를가리키도록변경 p list NULL NULL removed 29
단순연결리스트의삭제연산 (4/4) 삭제연산의코드 // phead : 헤드포인터에대한포인터 // p: 삭제될노드의선행노드 // removed: 삭제될노드 void remove_node(listnode **phead, ListNode *p, ListNode *removed) if( p == NULL ) *phead = (*phead)->link; else p->link = removed->link; free(removed); 30
방문연산코드 방문연산 : 리스트상의노드를순차적으로방문 반복과순환기법을모두사용가능 반복버전 void display(listnode *head) ListNode *p=head; while( p!= NULL ) printf("%d->", p->data); p = p->link; printf("\n"); 순환버전 void display_recur(listnode *head) ListNode *p=head; if( p!= NULL ) printf("%d->", p->data); display_recur(p->link); 31
탐색연산코드 탐색연산 : 특정한데이터값을갖는노드를찾는연산 head NULL NULL NULL p ListNode *search(listnode *head, int x) ListNode *p; p = head; while( p!= NULL ) if( p->data == x ) return p; // 탐색성공 p = p->link; return p; // 탐색실패일경우 NULL 반환 32
합병연산코드 합병연산 : 2 개의리스트를합하는연산 head1 NULL NULL NULL head2 NULL NULL NULL ListNode *concat(listnode *head1, ListNode *head2) ListNode *p; if( head1 == NULL ) return head2; else if( head2 == NULL ) return head1; else p = head1; while( p->link!= NULL ) p = p->link; p->link = head2; return head1; 33
역순연산코드 역순연산 : 리스트의노드들을역순으로만드는연산 head NULL NULL NULL NULL ListNode *reverse(listnode *head) // 순회포인터로 p, q, r을사용 ListNode *p, *q, *r; p = head; // p는역순으로만들리스트 q = NULL; // q는역순으로만들노드 while (p!= NULL) r = q; // r은역순으로된리스트. r은 q, q는 p를차례로따라간다. q = p; p = p->link; q->link =r; // q의링크방향을바꾼다. return q; r q p // q 는역순으로된리스트의헤드포인터 34
원형연결리스트 원형연결리스트 마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 head NULL NULL 보통헤드포인터가마지막노드를가리키게끔구성하면리스트의처음이나마지막에노드를삽입하는연산이단순연결리스트에비하여용이 NULL NULL head 35
원형연결리스트의삽입 리스트의처음에삽입 (2) E A B C NULL (1) node DNULL head // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // node : 삽입될노드 void insert_first(listnode **phead, if( *phead == NULL ) *phead = node; node->link = node; else node->link = (*phead)->link; (*phead)->link = node; ListNode *node) 36
원형연결리스트의삽입 리스트의끝에삽입 (2) E A B CNULL (1) node (3) // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // node : 삽입될노드 void insert_last(listnode **phead, ListNode *node) if( *phead == NULL ) *phead = node; node->link = node; else node->link = (*phead)->link; (*phead)->link = node; *phead = node; DNULL head 37
이중연결리스트 단순연결리스트의문제점 선행노드를찾기가힘듬 삽입이나삭제시에는반드시선행노드가필요 이중연결리스트 정의 : 하나의노드가선행노드와후속노드에대한두개의링크를가지는리스트 단점은공간을많이차지하고코드가복잡 실제사용되는이중연결리스트의형태 헤드노드 + 이중연결리스트 + 원형연결리스트 헤드노드 38
이중연결리스트의노드 헤드노드 (head node) 정의 : 데이터를가지지않고단지삽입, 삭제코드를간단하게할목적으로만들어진노드 헤드포인터와의구별필요 공백상태에서는헤드노드만존재 헤드노드 이중연결리스트에서의노드의구조 typedef int element; typedef struct DlistNode element data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; llink data rlink 39
이중연결리스트의삽입연산 삽입연산 before (4) (1) (2) (3) new_node // 노드 new_node 를노드 before 의오른쪽에삽입한다. void dinsert_node(dlistnode *before, DlistNode *new_node) new_node->llink = before; new_node->rlink = before->rlink; before->rlink->llink = new_node; before->rlink = new_node; 40
이중연결리스트의삭제연산 삭제연산 before (1) (2) (3) removed // 노드 removed 를삭제한다. void dremove_node(dlistnode *phead_node, DlistNode *removed) if( removed == phead_node ) return; removed->llink->rlink = removed->rlink; removed->rlink->llink = removed->llink; free(removed); 41
연결리스트의응용 : 다항식
연결리스트의응용 : 다항식 다항식을컴퓨터로처리하기위한자료구조 다항식의덧셈, 뺄셈 하나의다항식을하나의연결리스트로표현 A=3x 12 +2x 8 +1 A 3 12 2 8 1 0 NULL typedef struct ListNode int coef; int expon; struct ListNode *link; ListNode; ListNode *A, *B; 43
다항식의덧셈 (1/3) 2 개의다항식을더하는덧셈연산을구현 A=3x 12 +2x 8 +1, B=8x 12-3x 10 +10x 6 이면 A+B=11x 12-3x 10 +2x 8 +10x 6 +1 다항식 A 와 B 의항들을따라순회하면서각항들을더한다. 1 p.expon == q.expon : 두계수를더해서 0 이아니면새로운항을만들어결과다항식 C 에추가한다. p 와 q 는모두다음항으로이동한다. 2 p.expon < q.expon : q 가지시하는항을새로운항으로복사하여결과다항식 C 에추가한다. q 만다음항으로이동한다. 3 p.expon > q.expon : p 가지시하는항을새로운항으로복사하여결과다항식 C 에추가한다. p 만다음항으로이동한다. 44
다항식의덧셈 (2/3) A=3x 12 +2x 8 +1, B=8x 12-3x 10 +10x 6 A 3 12 2 8 1 0 NULL p B 8 12-3 10 10 6 NULL q C 11 12 r A 3 12 2 8 1 0 NULL p B 8 12-3 10 10 6 NULL C 11 12 q q -3 10 r 45
다항식의덧셈 (3/3) p 나 q 중에서어느하나가 NULL 이되면아직남아있는항들을전부 C 로가져온다. A 3 12 2 8 1 0 NULL p B 8 12-3 10 10 6 NULL q C 11 12-3 10 2 8 r A 3 12 2 8 1 0 NULL p B 8 12-3 10 10 6 NULL q C 11 12-3 10 2 8 10 6 1 0 NULL r 46
다항식프로그램 (1/5) #include <stdio.h> #include <stdlib.h> // 연결리스트의노드의구조 typedef struct ListNode int coef; int expon; struct ListNode *link; ListNode; // 연결리스트헤더 typedef struct ListHeader int length; ListNode *head; ListNode *tail; ListHeader; 47
다항식프로그램 (2/5) // 초기화함수 void init(listheader *plist) plist->length = 0; plist->head = plist->tail = NULL; // plist 는연결리스트의헤더를가리키는포인터, coef 는계수, expon 는지수 void insert_node_last(listheader *plist, int coef, int expon) ListNode *temp = (ListNode *)malloc(sizeof(listnode)); if( temp == NULL ) error(" 메모리할당에러 "); temp->coef=coef; temp->expon=expon; temp->link=null; if( plist->tail == NULL ) plist->head = plist->tail = temp; else plist->tail->link = temp; plist->tail = temp; plist->length++; 48
다항식프로그램 (3/5) // list3 = list1 + list2 void poly_add(listheader *plist1, ListHeader *plist2, ListHeader *plist3) ListNode *a = plist1->head; ListNode *b = plist2->head; int sum; while (a && b) if (a->expon == b->expon) // a 의차수 > b 의차수 sum = a->coef + b->coef; if (sum!= 0) insert_node_last(plist3, sum, a->expon); a = a->link; b = b->link; else if (a->expon > b->expon) // a 의차수 == b 의차수 insert_node_last(plist3, a->coef, a->expon); a = a->link; else // a 의차수 < b 의차수 insert_node_last(plist3, b->coef, b->expon); b = b->link; 49
다항식프로그램 (4/5) // a 나 b 중의하나가먼저끝나게되면남아있는항들을모두 // 결과다항식으로복사 for (; a!= NULL; a = a->link) insert_node_last(plist3, a->coef, a->expon); for (; b!= NULL; b = b->link) insert_node_last(plist3, b->coef, b->expon); // void poly_print(listheader *plist) ListNode *p = plist->head; for (; p; p = p->link) printf("%d %d\n", p->coef, p->expon); 50
다항식프로그램 (5/5) void main() ListHeader list1, list2, list3; // 연결리스트의초기화 init(&list1); init(&list2); init(&list3); // 다항식 1 을생성 insert_node_last(&list1, 3,12); insert_node_last(&list1, 2,8); insert_node_last(&list1, 1,0); // 다항식 2 를생성 insert_node_last(&list2, 8,12); insert_node_last(&list2, -3,10); insert_node_last(&list2, 10,6); // 다항식 3 = 다항식 1 + 다항식 2 poly_add(&list1, &list2, &list3); poly_print(&list3); 51
연결리스트로구현된리스트
연결리스트를이용한리스트의 ADT 리스트 ADT의연산을연결리스트를이용하여구현 리스트 ADT의 add, delete 연산의파라미터는위치 연결리스트의 insert_node, remove_node의파리미터는노드포인터 상황에따라연산을적절하게선택하여야함 사용자 add( 항목의위치 ) delete( 항목의위치 ) 리스트 ADT insert_node( 노드포인터 ) remove_node( 노드포인터 ) 연결리스트 53
리스트의 ADT 첫번째노드를가리키는헤드포인터 typedef struct ListNode *head; int length; ListType; // 헤드포인터 // 노드의개수 ListType list1; 연결리스트내의존재하는노드의개수 리스트 ADT 의생성 54
is_empty, get_length 연산 is_empty int is_empty(listtype *list) if( list->head == NULL ) return 1; else return 0; get_length // 리스트의항목의개수를반환한다. int get_length(listtype *list) return list->length; 55
add 연산 새로운데이터를임의의위치에삽입 항목의위치를노드포인터로변환해주는함수 get_node_at 필요 get_node_at // 리스트안에서 pos 위치의노드를반환한다. ListNode *get_node_at(listtype *list, int pos) int i; ListNode *tmp_node = list->head; if( pos < 0 ) return NULL; for (i=0; i<pos; i++) tmp_node = tmp_node->link; return tmp_node; 56
add 연산 (1/2) add // 주어진위치에데이터를삽입한다. void add(listtype *list, int position, element data) ListNode *p; if ((position >= 0) && (position <= list->length)) ListNode*node= (ListNode *)malloc(sizeof(listnode)); if( node == NULL ) error(" 메모리할당에러 "); node->data = data; p = get_node_at(list, position-1); insert_node(&(list->head), p, node); list->length++; 57
add 연산 (2/2) add // 리스트의끝에데이터를삽입한다. void add_last(listtype *list, element data) add(list, get_length(list), data); // 리스트의처음에데이터를삽입한다. void add_first(listtype *list, element data) add(list, 0, data); 58
delete 연산 임의의위치의데이터를삭제 항목의위치를노드포인터로변환해주는함수 get_node_at 필요 delete // 주어진위치의데이터를삭제한다. void delete(listtype *list, int pos) if (!is_empty(list) && (pos >= 0) && (pos < list->length)) ListNode *p = get_node_at(list, pos-1); ListNode *removed = get_node_at(list, pos); remove_node(&(list->head),p,removed); list->length--; 59
get_entry 연산 위치 pos 에해당하는데이터를반환하는연산 get_entry element get_entry(listtype *list, int pos) ListNode *p; if( pos >= list->length ) error(" 위치오류 "); p = get_node_at(list, pos); return p->data; 60
clear 연산 모든노드를지우는함수 clear void clear(listtype *list, int pos) int i; for(i=0; i<list->length; i++) delete(list, i); 61
display 연산 리스트가가지고있는데이터를화면에출력 display // 버퍼의내용을출력한다. void display(listtype *list) int i; ListNode *node=list->head; printf("( "); for(i=0;i<list->length;i++) printf("%d ",node->data); node = node->link; printf(" )\n"); 62
is_in_list 연산 연결리스트에서데이터필드가 item 인노드를탐색하는연산 is_in_list // 데이터값이 s 인노드를찾는다. int is_in_list(listtype *list, element item) ListNode *p; p = list->head; // 헤드포인터에서부터시작한다. while( (p!= NULL) ) // 노드의데이터가 item 이면 if( p->data == item ) break; p = p->link; if( p == NULL) return FALSE; else return TRUE; 63
전체프로그램 main int main() ListType list1; init(&list1); add(&list1, 0, 20); add_last(&list1, 30); add_first(&list1, 10); add_last(&list1, 40); // list1 = (10, 20, 30, 40) display(&list1); // list1 = (10, 20, 30) delete(&list1, 3); display(&list1); // list1 = (20, 30) delete(&list1, 0); display(&list1); printf("%s\n", is_in_list(&list1, 20)==TRUE? " 성공 ": " 실패 "); printf("%d\n", get_entry(&list1, 0)); 64