제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1
1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다 ( 즉 n 번의링크를따라가야한다, O(n)). 마지막데이터를찾을때, 마지막다음에데이터를삽입할때등의경우에불편함이있다. ptr x1 x2 x3 NULL 단순연결리스트의마지막노드를끝노드와연결시키면? 단순연결리스트를끝노드와연결시키면상황은마찬가지이지만리스트의포인터를마지막노드를가리키면바로찾을수있다. 리스트의첫노드는마지막노드의다음노드이므로리스트의첫노드도바로찾을수있다.( 원형연결리스트의포인터는항상마지막노드를가리켜야한다는점을주의하라.) 2
연결리스트처음과마지막에노드삽입 / 삭제 연결리스트의맨처음과맨마지막에노드를삽입, 삭제할경우노드수 n 과관계 노드를삭제하려면앞노드의주소를알아야한다. 단순 / 원형연결리스트 삽입 삭제 맨처음 O(1) O(1) 맨마지막 O(n)/O(1) O(n) 단순연결리스트 ptr x1 x2 x3 원형연결리스트 x1 x2 x3 ptr 3
단순원형연결리스트 (singly circular linked list) 의예 리스트를원형으로만든다음리스트의포인터를마지막을가리킨다. 그런후리스트의처음과마지막에노드를삽입하는경우를살펴보자 ptr x1 x2 x3 x1 x2 x3 ptr (1) 리스트의처음에삽입 O(1) : 수행시간이상수시간이걸린다. x3 다음에삽입한다. (2) 리스트의마지막에삽입 O(1) : 수행시간이상수시간이걸린다. x3 다음에삽입한다. ptr 값을새로삽입한노드를가리킨다. 4
단순원형연결리스트 (singly circular linked list) 의여러가지모습 (1) ptr (2) ptr x1 (3) x1 x2 x3 ptr 5
수행시간표기법 수행시간이데이터개수에따라어떻게변하는가를나타내는표기로 O- 표기법을사용한다. O(1) - 상수시간 : 항상똑같을때 O(n) 데이터개수 n 의 1 차함수보다크지않을때 O(n 2 ) 데이터개수 n 의이차함수 (n 2 ) 보다크지않을때 즉 O(f(n)) 수행시간이라함은수행시간이많이걸려야 f(n) 함수보다는작거나같다는의미이다. 즉프로그램수행이얼마나오래걸릴것인지에대한척도이다. 6
/* 원형연결리스트의맨뒤에노드를삽입하는알고리즘 */ void insert_last(list_ptr *ptr, list_ptr node) { if(is_empty(*ptr)) { /* 빈리스트경우 */ *ptr = node; node->link = node; else { node->link = (*ptr)->link; /* 1 */ (*ptr)->link = node; /* 2 */ /* 노드연결 */ *ptr = node; /* 3 */ /* 리스트의맨처음에삽입할경우이문장을생략 */ X 2 x1 x2 x3 Y X 3 ptr node 1 7
Q/A ( 실험 1) circularlist.c 프로그램실행 ( 실험 2) 원형연결리스트의맨앞에노드를삭제하는알고리즘작성 void delete_first(list_ptr *ptr,list_ptr node) { if(is_empty(*ptr)) { printf( 원소없음 n ); /* 빈리스트경우 */ else { /* 여기작성 */ X x1 x2 x3 ptr 8
2. 이중연결리스트 (Doubly Linked List) 이중연결리스트란? 연결리스트의각노드에링크를 2 개를만들어하나는뒷노드를하나는앞노드를가리키는연결리스트이다. 단순연결리스트 (Singly Linked List) 는다음과같은경우불편한점이있다. 단순연결리스트의노드포인터를알고있을때노드의다음노드는찾아갈수있지만, 노드의앞노드는찾아갈수없다. 앞노드를찾아가려면리스트의처음부터따라가야한다. ( 즉노드의위치만큼링크를따라가야한다 O(n)). 즉, 임의의노드의앞노드를찾아가는데시간이걸린다. 단순연결리스트의각노드에앞노드의링크를저장하면? 단순연결리스트의각노드에두개의노드포인터를두어서하나를앞쪽노드를하나는뒤쪽노드를가리키어앞뒤어느방향으로나갈수있도록만든리스트이다. 9
단순연결리스트의문제점 - 한쪽방향으로만노드를따라간다.( 앞에서뒤로 ) - 앞노드를찾으려면처음부터링크를따라와야한다. - 임의의노드를지우기어렵다 ( 노드를지우려면앞, 뒤노드포인터를알아야한다.) 해결방법 - 원형연결리스트 - 이중연결리스트 - 이중원형연결리스트 (doubly linked circular list) 10
/* 이중연결리스트를위한노드의선언 */ struct dnode { struct dnode *llink; element item; struct dnode *rlink; ; typedef struct dnode node; typedef node *node_ptr; ptr 이이중연결리스트의임의의노드를가리킨다고가정하자이중연결리스트에서는다음의식이성립한다. ptr = ptr->llink->rlink = ptr->rlink->llink ptr 11
이중연결리스트의처음시작때는 ( 노드가하나도없는경우 ) 가상의노드에서부터시작한다. 이데이터가없는가상의노드를 dummy node 라고한다. 보통은 head node( 머리노드 ) 라고한다. - 비어있는리스트경우 head node 만있다. - 프로그램의편의를위하여만들어놓은것이다. - 노드와같은자료구조이나데이터값이없다. 비어있는이중연결리스트 노드가한개추가된후의리스트 ptr ptr 12
머리노드를가진이중원형연결리스트의모양 - 헤드노드의 llink 는앞노드 ( 리스트의마지막노드를가리킨다 ) rlink는다음노드 ( 리스트의첫노드를가리킨다 ) head llink item rlink 13
/* 이중원형연결리스트에노드를삽입하는프로그램삽입할노드의바로앞노드만알면된다.*/ void dinsert(node_ptr node,node_ptr newnode) { /* node 의오른쪽에 newnode 를삽입 */ newnode->llink = node; /* 1 */ newnode->rlink = node->rlink; /* 2 */ node->rlink->llink = newnode; /* 3 */ node->rlink = newnode; /* 4 */ head llink item rlink 4 X X 3 node 1 2 newnode 14
비어있는이중연결리스트에노드의삽입 node node newnode 15
이중연결리스트에서노드의삭제 void ddelete(node_ptr node,node_ptr deleted) { /* 이중연결리스트에서의 deleted 노드삭제 */ if(node == deleted) printf( 머리노드삭제금지... n ); else { deleted->llink->rlink = deleted->rlink; /* 1 */ deleted->rlink->llink = deleted->llink; /* 2 */ free(deleted); /* 3 */ 16
한개의노드를가진이중연결리스트에서노드의삭제 2 1 node node X X deleted 3 free() 노드를반환 17
Q/A ( 실험 1) dlinkedlist.c 프로그램실행 ( 실험 2) 이중연결리스트의노드의수를세는알고리즘작성 int countdouble(node_ptr node) { if(node->rlink==node) return 0; else { /*? */ node llink item rlink 18
3. 연결리스트알고리즘들 3-1. 연결리스트를역순으로만들기 연결리스트의역배열을위한프로그램 /* 연결리스트의링크를거꾸로만드는프로그램을작성하여본다 */ /* 리스트노드선언부분 */ struct node { char data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; 19
연결리스트의역배열을위한프로그램 수행시간 : O(n) list_ptr invert(list_ptr lead) { list_ptr middle, trail; middle = NULL; while(lead) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; return middle; 20
middle lead NULL NULL trail middle lead NULL NULL trail middle lead 21
NULL NULL trail middle lead NULL NULL trail middle lead NULL NULL trail middle lead 22
3-2. 두개의연결리스트를한개의연결리스트로연결 ptr1 1 3 5 7 1 ptr2 2 4 6 8 23
2 개의연결리스트연결프로그램 /* 두개의리스트를연결해서새로운리스트만든다 */ /* ptr1에 ptr2를붙인다 */ list_ptr concat(list_ptr ptr1,list_ptr ptr2) { list_ptr temp; if(!ptr1 ) return ptr2; else { if( ptr2 ) { for(temp=ptr1; temp->link; temp=temp->link); temp->link = ptr2; 1 return ptr1; 24
3-3. 원형연결리스트의노드개수세기 /* 아래의연결리스트의 ptr 값을주면결과는 3을반환한다.*/ int length(list_ptr ptr) { list_ptr temp; int count = 0; if(ptr) { temp = ptr; 원형리스트의노드의개수세기 do { count++; temp = temp->link; while(temp!= ptr); return count; x1 x2 x3 ptr 25
Review 단순연결리스트의단점을극복하는리스트구조는다음과같다. (1) 연결리스트의끝에서작업하기편리한원형연결리스트연결리스트에서마지막노드가끝노드를가리키게하며리스트의포인터를맨끝노드를가리킨다. (2) 임의의노드의앞뒤작업을편리하게하기위한이중연결리스트연결리스트의각노드에앞과뒤로가는링크를만들어놓은리스트이다. (3) 원형과이중연결리스트의두가지장점을동시에갖는이중원형연결리스트가있다. 원형과이중연결리스트두가지구조를동시에갖는다. 즉각노드에두개의링크를두면서마지막노드와첫노드도연결시킨다. 또머리노드라는가상의노드를운영한다. 연결리스트프로그래밍은약간복잡하다. 링크와노드의구조를잘이해하면기계적이다. 26