리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

Transcription

1 00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트

2 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) l l 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트

3 새로운항목을리스트의끝, 처음, 중간에추가한다. 기존의항목을리스트의임의의위치에서삭제한다. 모든항목을삭제한다. 기존의항목을대치한다. 리스트가특정한항목을가지고있는지를살핀다. 리스트의특정위치의항목을반환한다. 리스트안의항목의개수를센다. 리스트가비었는지, 꽉찼는지를체크한다. 리스트안의모든항목을표시한다.

4 객체 : 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 a a b a b c addtail(list1,a) addtail(list1,b) add(list1,2,c) a d b c a d c a e c add(list1,1,d) delete(list1,2) replace(list1,1,e)

6 void main() int i, n; // list2를생성한다 : 구현방법에따라약간씩다름 ListType list2; add_tail(&list2," 마요네즈 ); // 리스트의포인트를전달 add_tail(&list2," 빵 ); add_tail(&list2," 치즈 ); add_tail(&list2," 우유 ); display(&list2); n = get_length(&list2); printf(" 쇼핑해야할항목수는 %d입니다.\n", n); for(i=0;i<n;i++) printf("%d항목은 %s입니다.,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) A B C D E 삽입연산 : 삽입위치다음의항목들을이동하여야함. N A B C D E 삭제연산 : 삭제위치다음의항목들을이동하여야함 C A B D E

9 항목들의타입은 element 로정의 list 라는 1 차원배열에항목들을차례대로저장 length 에항목의개수저장 typedef int element; typedef struct int list[max_list_size]; int length; ArrayListType; // 배열정의 // 현재배열에저장된항목들의개수 // 리스트초기화 void init(arraylisttype *L) L->length = 0;

10 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;

11 1. add 함수는먼저배열이포화상태인지를검사하고삽입위치가적합한범위에있는지를검사한다. 2. 삽입위치다음에있는자료들을한칸씩뒤로이동한다.. N A B C D E position length-1 // 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++; A B C D E A B C D E A B C D E A B N C D E

12 1. 삭제위치를검사한다. 2. 삭제위치부터맨끝까지의자료를한칸씩앞으로옮긴다. // position: 삭제하고자하는위치 // 반환값 : 삭제되는자료 element delete(arraylisttype *L, int position) int i; element item; 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

13 리스트 ADT 의연산을연결리스트를이용하여구현 리스트 ADT 의 add, delete 연산의파라미터는위치 연결리스트의 insert_node, remove_node 의파리미터는노드포인터 상황에따라연산을적절하게선택하여야함 사용자 add( 항목의위치 ) delete( 항목의위치 ) 리스트 ADT insert_node( 노드포인터 ) remove_node( 노드포인터 ) 연결리스트

14 첫번째노드를가리키는헤드포인터 typedef struct ListNode *head; int length; ListType; // 헤드포인터 // 노드의개수 ListType list1; 연결리스트내의존재하는노드의개수 리스트 ADT 의생성

15 int is_empty(listtype *list) if( list->head == NULL ) return 1; else return 0; // 리스트의항목의개수를반환한다. int get_length(listtype *list) return list->length;

16 새로운데이터를임의의위치에삽입 항목의위치를노드포인터로변환해주는함수 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= if( node == NULL ) error(" 메모리할당에러 "); node->data = data; p = get_node_at(list, position-1); insert_node(&(list->head), p, node); list->length++; (ListNode *)malloc(sizeof(listnode));

17 임의의위치의데이터를삭제 항목의위치를노드포인터로변환해주는함수 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--;

18 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함.

19 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다.

20 C 언어로표현하는링크드리스트의노드 typedef struct tagnode int Data; /* 데이터필드 */ struct tagnode* NextNode; /* 다음노드를가리키는포인터 */ Node; 노드추가

21 노드삭제

22 노드삽입

23 각노드가앞노드 / 뒷노드양쪽에대한포인터를모두갖고있어각노드들을이중으로연결하는리스트.

24 노드추가

25 노드삭제 삭제 노드는 12 노드뒤에있는 87 노드를가리키고, 87 노드는 98 노드를가리키도록변경합니다. 그리고 12 노드는아무것도가리키지않습니다 x x

26 노드삭제

27 우로보로스처럼머리 ( 헤드 ) 가꼬리 ( 테일 ) 를물고있는형태의링크드리스트

28 노드추가 최초의노드를추가하는경우 ( 즉, 노드가한개뿐 ) 리스트에노드가이미한개이상존재하는경우에는 테일노드뒤에새노드를붙인다 보다는 테일과헤드사이에새노드를삽입한다.

29 노드추가코드 void CDLL_AppendNode(Node** Head, Node* NewNode) /* 헤드노드가 NULL 이라면새로운노드가 Head */ if ( (*Head) == NULL ) *Head = NewNode; (*Head)->NextNode = *Head; (*Head)->PrevNode = *Head; else /* 테일과헤드사이에 NewNode 를삽입한다. */ Node* Tail = (*Head)->PrevNode; Tail->NextNode->PrevNode = NewNode; Tail->NextNode = NewNode; NewNode->NextNode = (*Head); NewNode->PrevNode = Tail; /* 기존의테일을새로운 */ /* 테일의 PrevNode 가가리킨다. */

30 노드삭제코드 void CDLL_RemoveNode(Node** Head, Node* Remove) if ( *Head == Remove ) (*Head)->PrevNode->NextNode = Remove->NextNode; (*Head)->NextNode->PrevNode = Remove->PrevNode; *Head = Remove->NextNode; Remove->PrevNode = NULL; Remove->NextNode = NULL; else Node* Temp = Remove; Remove->PrevNode->NextNode = Temp->NextNode; Remove->NextNode->PrevNode = Temp->PrevNode; Remove->PrevNode = NULL; Remove->NextNode = NULL;