6-1
리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2
객체 : 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) ::= 리스트의모든요소를표시한다. 6-3
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 6-4
연결리스트의항목들을노드 (node) 라고하는곳에저장 각노드는데이타필드와링크필드로구성 데이타필드 리스트의원소, 즉데이타값을저장 링크필드 다른노드의주소를저장 ( 포인터 ) 메모리안에서노드의물리적순서가리스트의논리적순서와일치할필요는없음 A C D E B 메모리 6-5
노드 = 데이터필드 + 링크필드 data link 헤드포인터 (head pointer): 리스트의첫번째노드를 가리키는변수 헤드포인터 NULL 노드의생성 : 필요할때마다동적메모리생성 (malloc) 이용하여노드를생성 요구 운영체제 동적생성 헤드포인터 NULL 6-6
삽입연산 장점 삽입, 삭제가보다용이하다. N 연속된메모리공간이필요없다. 크기제한이없다 A C D E 단점 B 구현이어렵다. 오류가발생하기쉽다. 메인메모리 삭제연산 A C D E B 메인메모리 6-7
단순 (simple) 연결리스트 헤드포인터 NULL 원형 (circular) 연결리스트 헤드포인터 이중 (doubly) 연결리스트 헤드포인터 6-8
하나의링크필드를이용하여연결 마지막노드의링크값은 NULL 헤드포인터 10 20 NULL 30 NULL 40 NULL 50 NULL 6-9
before after before after 10 30 10 30 new 20 new 20 insert_node(list, before, new) if List = NULL then List new else new.link before.link before.link new 6-10
before removed after 10 20 30 before removed after 10 20 30 remove_node(list, before, removed) if List NULL then before.link removed.link destroy(removed) 6-11
데이터필드 : 구조체로정의 링크필드 : 포인터사용 typedef int element; typedef struct ListNode { element data; struct ListNode *link; ListNode; 노드의생성 : 동적메모리생성라이브러리 malloc 함수이용 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); p1 6-12
데이터필드와링크필드설정 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): 연결리스트의맨처음노드를가리키는포인터 6-13
삽입함수의프로토타입 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) phead: 헤드포인터 head 에대한포인터 p: 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입된다. new_node: 새로운노드를가리키는포인터 헤드포인터가함수안에서변경되므로헤드포인터의포인터필요 삽입의 3 가지경우 head가 NULL인경우 : 공백리스트에삽입 p가 NULL인경우 : 리스트의맨처음에삽입 일반적인경우 : 리스트의중간에삽입 6-14
(1) head 가 NULL 인경우 : head 가 NULL 이라면현재삽입하려는 노드가첫번째노드가된다. 따라서 head 의값만변경하면된다.. head new_node NULL (2) p 가 NULL 인경우 : 새로운노드를리스트의맨앞에삽입한다. head NULL NULL new_node NULL 6-15
(3) head 와 p 가 NULL 이아닌경우 : 가장일반적인경우이다. new_node 의 link 에 p->link 값을복사한다음, p->link 가 new_node 를가리키도록한다. p NULL new_node (2) (1) 6-16
// 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 이면첫번째노드로삽입 6-17
삭제함수의프로토타입 //phead: 헤드포인터 head 의포인터 //p: 삭제될노드의선행노드를가리키는포인터 //removed: 삭제될노드를가리키는포인터 void remove_node(listnode **phead, ListNode *p, ListNode *removed) 삭제의 2 가지경우 p 가 NULL 인경우 : 맨앞의노드를삭제 p 가 NULL 이아닌경우 : 중간노드를삭제 6-18
p 가 NULL 인경우 : 연결리스트의첫번째노드를삭제한다. 헤드포인터변경 list NULL removed p가 NULL이아닌경우 : removed 앞의노드인 p의링크가 removed 다음노드를가리키도록변경 p list NULL NULL removed 6-19
// 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); 6-20
방문연산 : 리스트상의노드를순차적으로방문반복과순환방법사용가능반복방법 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); 6-21
탐색연산 : 특정한데이터값을갖는노드를찾는연산 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 반환 6-22
합병연산 : 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; 6-23
역순연산 : 리스트의노드들을역순으로만드는연산 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 는역순으로된리스트의헤드포인터 6-24
마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 head NULL NULL 보통헤드포인터가마지막노드를가리키게끔구성하면리스트의처음이나마지막에노드를삽입하는연산이단순연결리스트에비하여용이 NULL NULL head 6-25
(2) E A B C NULL (1) node // 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; D NULL head 6-26
(2) A B C NULL D NULL E (1) (3) head 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; 6-27
단순연결리스트의문제점 : 선행노드를찾기가힘들다 삽입이나삭제시에는반드시선행노드가필요 이중연결리스트 : 하나의노드가선행노드와후속노드에대한두개의링크를가지는리스트 링크가양방향이므로양방향으로검색이가능 단점은공간을많이차지하고코드가복잡 실제사용되는이중연결리스트의형태 : 헤드노드 + 이중연결리스트 + 원형연결리스트 헤드노드 6-28
헤드노드 (head node): 데이터를가지지않고단지삽입, 삭제코드를간단하게할목적으로만들어진노드 헤드포인터와의구별필요 공백상태에서는헤드노드만존재 헤드노드 이중연결리스트에서의노드의구조 typedef int element; typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; llink data rlink 6-29
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; 6-30
// 노드 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); 6-31