CHAP 4: 리스트
리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item 0, item 1,..., item n 1) 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 영어알파벳 : (a, b,,z) 카드 : (Ace, 2,3,,King) 쇼핑리스트
리스트의연산 새로운항목을리스트의끝, 처음, 중간에추가한다. 기존의항목을리스트의임의의위치에서삭제한다. 모든항목을삭제한다. 기존의항목을대치한다. 리스트가특정한항목을가지고있는지를살핀다. 리스트의특정위치의항목을반환한다. 리스트안의항목의개수를센다. 리스트가비었는지, 꽉찼는지를체크한다. 리스트안의모든항목을표시한다.
리스트 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) ::= 리스트의모든요소를표시한다.
리스트 ADT 사용예 #1 a a b a b c addlast(list,a) addlast(list,b) add(list,2,c) a d b c a d c a e c add(list,1,d) delete(list,2) replace(list,1,e)
리스트 ADT 사용예 #2 main() { int i, n; // list2 를생성한다 : 구현방법에따라약간씩다름 ListType list; addlast(&list," 마요네즈 ); // 리스트의포인트를전달 addlast(&list," 빵 ); addlast(&list," 치즈 ); addlast(&list," 우유 ); display(&list); n = get_length(&list); printf(" 쇼핑해야할항목수는 %d 입니다.\n", n); for(i=0;i<n;i++) printf("%d 항목은 %s 입니다.,i,get_entry(&list,i));
리스트구현방법 1. 배열을이용하는방법 구현이간단 삽입, 삭제시오버헤드 항목의개수제한 2. 연결리스트를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음
배열을이용한방법
배열로구현된리스트 1 차원배열에항목들을순서대로저장 L=(a, b, c, d, e) 삽입연산 : 삽입위치다음의항목들을이동하여야함. 삭제연산 : 삭제위치다음의항목들을이동하여야함
배열로구현된리스트 배열단점 연속된원들이순차적으로저장 기억장소낭비 삽입 / 삭제 : 비싼연산 해결방법 => Link 로해결 ( Pointer 이용 )
ArrayListType 의구현 항목들의타입은 element 로정의 list 라는 1 차원배열에항목들을차례대로저장 length 에항목의개수저장 typedef int element; typedef struct { element list[max_list_size]; // 배열정의 int length; // 현재배열에저장된항목들의개수 ArrayListType; // 리스트초기화 void init(arraylisttype *L) { L->length = 0;
ArrayListType 의구현 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;
ArrayListType 의삽입연산 1. add 함수는먼저배열이포화상태인지를검사하고삽입위치가적합한범위에있는지를검사한다. 2. 삽입위치다음에있는자료들을한칸씩뒤로이동한다.. // 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 position length-1 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
ArrayListType 의삭제연산 1. 삭제위치를검사한다. 2. 삭제위치부터맨끝까지의자료를한칸씩앞으로옮긴다. // 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
연결리스트를이용한방법
Self-referential structures 자체참조구조 : 구성요소중자신을가리키는포인터가존재하는구조 연결리스트를학습하기전자체참조구조를이해하고실습해본다. ( 실습파일참고 )
연결리스트 리스트표현의 2 가지방법 순차표현 : 배열을이용한리스트표현 연결된표현 : 연결리스트를사용한리스트표현, 하나의노드가데이터와링크로구성되어있고링크가노드들을연결한다. 리스트 ADT 배열을이용한구현 a b c a b c 연결리스트를이용한구현 a b c NULL
연결된표현 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 다음항목을가리키는주소도같이저장 노드 (node) : < 항목, 주소 > 쌍 노드는데이타필드와링크필드로구성 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) 메모리안에서의노드의물리적순서가리스트의논리적순서 와일치할필요없음
연결된표현의장단점 장점 삽입, 삭제가보다용이하다. 연속된메모리공간이필요없다. 크기제한이없다 단점 구현이어렵다. 오류가발생하기쉽다.
연결리스트의구조 노드 = 데이터필드 + 링크필드 헤드포인터 (head pointer): 리스트의첫번째노드를가리키는변수 노드의생성 : 필요할때마다동적메모리생성이용하여노드를생성
연결리스트의종류 헤드포인터 NULL 단순연결리스트 헤드포인터 원형연결리스트 헤드포인터 이중연결리스트
단순연결리스트 하나의링크필드를이용하여연결 마지막노드의링크값은 NULL 헤드포인터 10 20 NULL 30 NULL 40 NULL 50 NULL 삽입연산 before after 10 30 before 10 30 after insert_node(l, before, new) if L = NULL then L new 20 new 20 new else new.link before.link before.link new
단순연결리스트 ( 삭제연산 ) remove_node(l, before, removed) if L NULL then before.link removed.link destroy(removed)
단순연결리스트의구현 데이터필드 : 구조체로정의 링크필드 : 포인터사용 typedef int element; typedef struct ListNode { element data; struct ListNode *link; ListNode; 노드의 ListNode 생성 *p1;: 동적메모리생성라이브러리 malloc 함수이용 p1 = (ListNode *)malloc(sizeof(listnode)); p1
단순연결리스트의구현 데이터필드와링크필드설정 p1->data = 10; p1->link = NULL; 두번째노드생성과첫번째노드와의연결 ListNode *p2; p2 = (ListNode *)malloc(sizeof(listnode)); p2->data = 20; p2->link = NULL; p1->link = p2; 헤드포인터 (head pointer): 연결리스트의맨처음노드를 가리키는포인터
단순연결리스트의삽입연산 삽입함수의프로토타입 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) phead: 헤드포인터 head 에대한포인터 p: 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입된다. new_node: 새로운노드를가리키는포인터 헤드포인터가함수안에서변경되므로헤드포인터의포인터필요 삽입의 3 가지경우 head가 NULL인경우 : 공백리스트에삽입 p가 NULL인경우 : 리스트의맨처음에삽입 일반적인경우 : 리스트의중간에삽입
삽입연산 (1) head 가 NULL 인경우 : head 가 NULL 이라면현재삽입하려는노드가첫번째노드여서 head 의값만변경하면된다.. (2) p 가 NULL 인경우 : 새로운노드를리스트의맨앞에삽입한다.
삽입연산 (3) head 와 p 가 NULL 이아닌경우 : 가장일반적인경우이다. new_node 의 link 에 p->link 값을복사한다음, p->link 가 new_node 를가리키도록한다. p ㅔ
삽입연산의코드 // 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 ){ // p가 NULL이면첫번째노드로삽입 new_node->link = *phead; *phead = new_node; else { // p 다음에삽입 new_node->link = p->link; p->link = new_node;
삭제연산 삭제함수의프로토타입 //phead: 헤드포인터 head 의포인터 //p: 삭제될노드의선행노드를가리키는포인터 //removed: 삭제될노드를가리키는포인터 void remove_node(listnode **phead, ListNode *p, ListNode *removed) 삭제의 2 가지경우 p 가 NULL 인경우 : 맨앞의노드를삭제 p 가 NULL 이아닌경우 : 중간노드를삭제
삭제연산 p 가 NULL 인경우 : 연결리스트의첫번째노드를삭제한다. 헤드포인터변경 list NULL removed p가 NULL이아닌경우 : removed 앞의노드인 p의링크가 removed 다음노드를 p 가리키도록변경 list NULL NULL removed
삭제연산코드 // phead : 헤드포인터에대한포인터 // p: 삭제될노드의선행노드 // removed: 삭제될노드 void remove_node(listnode **phead, ListNode *p, ListNode *removed) { if( p == NULL ) else free(removed); *phead = (*phead)->link; p->link = removed->link;
방문연산코드 방문연산 : 리스트상의노드를순차적으로방문 반복과순환기법을모두사용가능 반복버젼 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);
탐색연산코드 탐색연산 : 특정한데이터값을갖는노드를찾는연산 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 반환
합병연산코드 합병연산 : 2 개의리스트를합하는연산 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;
역순연산코드 역순연산 : 리스트의노드들을역순으로만드는연산 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; // q 는역순으로된리스트의헤드포인터
원형연결리스트 마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 head NULL NULL 보통헤드포인터가마지막노드를가리키게끔구성하면리스트의처음이나마지막에노드를삽입하는연산이단순연결리스트에비하여용이
리스트의처음에삽입 // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // node : 삽입될노드 void insert_first(listnode **phead, { ListNode *node) if( *phead == NULL ){ *phead = node; node->link = node; else { node->link = (*phead)->link; (*phead)->link = node;
리스트의끝에삽입 // 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;
이중연결리스트 단순연결리스트의문제점 : 선행노드를찾기가힘들다 삽입이나삭제시에는반드시선행노드가필요 이중연결리스트 : 하나의노드가선행노드와후속노드에대한두개의링크를가지는리스트 링크가양방향이므로양방향으로검색이가능 단점은공간을많이차지하고코드가복잡 실제사용되는이중연결리스트의형태 : 헤드노드 + 이중연결리스트 + 원형연결리스트
헤드노드 헤드노드 (head node): 데이터를가지지않고단지삽입, 삭제코드를간단하게할목적으로만들어진노드 헤드포인터와의구별필요 공백상태에서는헤드노드만존재 헤드노드 이중연결리스트에서의노드의구조 typedef int element; typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; llink data rlink
삽입연산 // 노드 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;
삭제연산 // 노드 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);
연결리스트의응용 : 다항식 다항식을컴퓨터로처리하기위한자료구조 다항식의덧셈, 뺄셈 하나의다항식을하나의연결리스트로표현 A=3x 12 +2x 8 +1 typedef struct ListNode { int coef; int expon; struct ListNode *link; ListNode; ListNode *A, *B;
다항식의덧셈구현 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만다음항으로이동한다.
다항식의덧셈 A 3 1 2 2 8 1 0 NULL B p 8 1 2-3 1 0 1 0 6 NULL C q 1 1 1 2 r A 3 12 2 8 1 0 NULL B p 8 12-3 10 10 6 NULL C 11 12 q -3 10 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 r A 3 12 2 8 1 0 p NULL p 나 q 중에서어느하나가 NULL 이되면아직남아있는항들을전부 C 로가 져온다. B 8 12-3 10 10 6 NULL q C 11 12-3 10 2 8 10 6 1 0 NULL r
리스트 ADT 의구현 첫번째노드를가리키는헤드포인터 typedef struct { ListNode *head; // 헤드포인터 int length; // 노드의개수 ListType; ListType list1; 연결리스트내의존재하는노드의개수 리스트 ADT 의생성
is_empty, get_length 연산의구현 int is_empty(listtype *list) { if( list->head == NULL ) return 1; else return 0; // 리스트의항목의개수를반환한다. int get_length(listtype *list) { return list->length;
add 연산의구현 새로운데이터를임의의위치에삽입 항목의위치를노드포인터로변환해주는함수 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; // 주어진위치에데이터를삽입한다. 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++;
delete 연산의구현 임의의위치의데이터를삭제 항목의위치를노드포인터로변환해주는함수 get_node_at 필요 // 주어진위치의데이터를삭제한다. void delete(listtype *list, int pos) { if (!is_empty(list) && (pos >= 0) && (pos < list->length)) { ListNode *p = get_node_at(list, pos-1); remove_node(&(list->head),p,(p!=null)?p->link:null); list->length--;
질의및토의
숙제 (HW) HW 1. 먼저연결리스트의모든부분을구현하십시오. HW2. 연습문제 #14, #15, #16