01_List

List Data Structures and Algorithms

목차 추상자료형 (ADT) 배열을이용한리스트의구현 연결리스트의개념적이해 연결리스트의 ADT 구현 원형연결리스트 이중연결리스트 Data Structures and Algorithms 2

추상자료형 Abstract Data Type Data Structures and Algorithms 3

추상자료형 (ADT) 의이해 추상자료형이란? 자료형에적용가능한연산또는기능의명세서 예 카드의삽입 카드의추출 ( 카드를빼냄 ) 동전의삽입 동전의추출 ( 동전을빼냄 ) 지폐의삽입 지폐의추출 ( 지폐를빼냄 ) Data Structures and Algorithms 4

지갑을의미하는구조체 Wallet 의정의 자료형과관련이있는연산을함께정의해야완전한자료형 typedef struct int coin; int bill; Wallet; // 동전의수 // 지폐의수 자료형 Wallet 의정의 + 자료형 Wallet 의연산의정의 int TakeOutMoney(Wallet * pw, int coin, int bill); void PutMoney(Wallet * pw, int coin, int bill); // 돈꺼내는연산 // 돈넣는연산 Data Structures and Algorithms 5

ADT 와자료구조학습순서 자료구조의 ADT를정의한다. ADT를근거로자료구조를활용하는 main 함수를정의 ADT를근거로자료구조를구현 올바른 ADT 의정의 자료구조의내부구현이감춰지도록정의 자료구조를쉽게이해하려면자료구조를활용하는 main 함수를먼저작성 Data Structures and Algorithms 6

연습 2 차원좌표계의한점의 ADT 를정의해보자 사용가능한연산은각 x, y 좌표의 +, - 계산으로한정함 typedef struct int x; int y; point; point add(point, point); // 좌표계의두점의합 point sub(point, point); // 좌표계의두점의차 Data Structures and Algorithms 7

배열을이용한리스트의구현 Data Structures and Algorithms 8

리스트구분및특징 구분 순차리스트 : 배열을기반으로구현된리스트 연결리스트 : 메모리의동적할당을기반으로구현된리스트 특징 저장형태 : 데이터를나란히 ( 하나의열로 ) 저장 저장특성 : 중복이되는데이터의저장을허용 Data Structures and Algorithms 9

리스트자료구조의 ADT 리스트의초기화 typedef int LData; 데이터저장 저장된데이터의탐색및탐색초기화 Data Structures and Algorithms 10

리스트자료구조의 ADT 다음데이터의참조 ( 반환 ) 을목적으로호출 바로이전에참조 ( 반환 ) 이이뤄진데이터의삭제 현재저장되어있는데이터의수를반환 Data Structures and Algorithms 11

리스트의 ADT 를기반으로한 main 함수 실행을위해필요한파일들 ArrayList.h 리스트자료구조의헤더파일 ArrayList.c 리스트자료구조의소스파일 ListMain.c 리스트관련 main 함수가담긴소스파일 Data Structures and Algorithms 12

리스트의초기화와데이터저장과정 리스트의초기화 int main(void) List list; // 리스트의생성.... ListInit(&list); // 리스트의초기화.... 초기화된리스트에데이터저장 int main(void).... LInsert(&list, 11); LInsert(&list, 22); LInsert(&list, 33);.... // 리스트에 11을저장 // 리스트에 22를저장 // 리스트에 33을저장 Data Structures and Algorithms 13

리스트의노드순회과정 LFirst: 리스트순회의시작 int main(void).... if( LFirst(&list, &data) ) // 첫데이터변수 data에저장 printf("%d ", data); while( LNext(&list, &data) ) // 다음데이터변수 data에저장 printf("%d ", data);.... 데이터참조일련의과정 LFirst LNext LNext LNext LNext.... Data Structures and Algorithms 14

리스트의노드삭제 LRemove 함수는연이은호출을허용하지않음! int main(void).... if( LFirst(&list, &data) ) if(data == 22) LRemove(&list); // LFirst 함수를통해참조한데이터삭제! while( LNext(&list, &data) ).... if(data == 22) LRemove(&list); // LNext 함수를통해참조한데이터삭제! Data Structures and Algorithms 15

배열기반리스트의헤더파일정의 1 리스트를배열기반으로구현하기위한선언을포함 #ifndef ARRAY_LIST_H #define ARRAY_LIST_H #define TRUE 1 #define FALSE 0. // 참 매크로정의 // 거짓 매크로정의 /*** ArrayList 의정의시작 ****/ #define LIST_LEN 100 typedef int LData; // 저장할대상의자료형을변경을위한 typedef 선언 typedef struct ArrayList LData arr[list_len]; int numofdata; int curposition; ArrayList; // 배열기반리스트를의미하는구조체 // 리스트의저장소배열 // 저장된데이터의수 // 현재참조데이터의위치 Data Structures and Algorithms 16

배열기반리스트의헤더파일정의 2 배열기반리스트 ADT 의함수들 /*** ArrayList 와관련된연산들 ****/ typedef ArrayList List; // 리스트의변경을용이하게하기위한 typedef 선언 void ListInit(List * plist); void LInsert(List * plist, LData data); // 초기화 // 데이터저장 int LFirst(List * plist, LData * pdata); // 첫데이터참조 int LNext(List * plist, LData * pdata); // 두번째이후데이터참조 LData LRemove(List * plist); int LCount(List * plist); // 참조한데이터삭제 // 저장된데이터의수반환 #endif Data Structures and Algorithms 17

배열기반리스트의초기화 초기화대상은구조체변수의멤버이기때문에구조체의정의를기반으로함수를작성 void ListInit(List * plist) (plist->numofdata) = 0; (plist->curposition) = -1; // 데이터 0개가리스트에저장됨 // -1: 참조하지않았음 Data Structures and Algorithms 18

배열기반리스트의삽입 배열에데이터저장 void LInsert(List * plist, LData data) if(plist->numofdata > LIST_LEN) // 더이상저장할공간이없다면 printf(" 저장이불가능합니다.\n"); return; plist->arr[plist->numofdata] = data; // 데이터저장 (plist->numofdata)++; // 저장된데이터수증가 Data Structures and Algorithms 19

배열기반리스트탐색 int LFirst(List * plist, LData * pdata) // 초기화, 첫데이터참조 if(plist->numofdata == 0) // 저장된데이터가하나도없다면 return FALSE; (plist->curposition) = 0; *pdata = plist->arr[0]; return TRUE; // 참조위치초기화 ; 첫데이터참조를의미 // pdata가가리키는공간에데이터저장 int LNext(List * plist, LData * pdata) // 다음데이터참조 // 더이상참조할데이터가없다면 if(plist->curposition >= (plist->numofdata)-1) return FALSE; (plist->curposition)++; *pdata = plist->arr[plist->curposition]; return TRUE; 데이터반환은매개변수로 함수의반환은연산성공여부 Data Structures and Algorithms 20

배열기반리스트의삭제 삭제기본모델 Data Structures and Algorithms 21

배열기반리스트의삭제 삭제된데이터는리턴값으로전달 LData LRemove(List * plist) int rpos = plist->curposition; int num = plist->numofdata; int i; LData rdata = plist->arr[rpos]; // 삭제할데이터의인덱스값참조 // 삭제할데이터를임시저장 for(i=rpos; i<num-1; i++) plist->arr[i] = plist->arr[i+1]; (plist->numofdata)--; (plist->curposition)--; return rdata; // 데이터의수감소 // 참조위치하나되돌림 // 삭제된데이터의반환 Data Structures and Algorithms 22

리스트에구조체변수저장하기 1 : Point.h Point.h: 리스트에저장할 Point 구조체변수의헤더 typedef struct _point int xpos; int ypos; Point; // Point 변수의 xpos, ypos 값설정 void SetPointPos(Point * ppos, int xpos, int ypos); // Point 변수의 xpos, ypos 정보출력 void ShowPointPos(Point * ppos); // 두 Point 변수의비교 int PointComp(Point * pos1, Point * pos2); Data Structures and Algorithms 23

리스트에구조체변수저장하기 2 : Point.c void SetPointPos(Point * ppos, int xpos, int ypos) ppos->xpos = xpos; ppos->ypos = ypos; void ShowPointPos(Point * ppos) printf("[%d, %d] \n", ppos->xpos, ppos->ypos); int PointComp(Point * pos1, Point * pos2) if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos) return 0; else if(pos1->xpos == pos2->xpos) return 1; else if(pos1->ypos == pos2->ypos) return 2; else return -1; Data Structures and Algorithms 24

리스트에구조체변수저장하기 3 ArrayList.h 배열 구조체 실행을위한파일구성 Point.h, Point.c ArrayList.h, ArrayList.c PointListMain.c 구조체 Point를위한파일배열기반리스트구조체 Point의변수저장 Data Structures and Algorithms 25

PointListMain.c : 초기화및저장 int main(void) List list; Point comppos; Point * ppos; ListInit(&list); /*** 4 개의데이터저장 ***/ ppos = (Point*)malloc(sizeof(Point)); SetPointPos(ppos, 2, 1); LInsert(&list, ppos); ppos = (Point*)malloc(sizeof(Point)); SetPointPos(ppos, 2, 2); LInsert(&list, ppos);...... Data Structures and Algorithms 26

PointListMain.c : 참조및조회 int main(void)...... /*** 저장된데이터의출력 ***/ printf(" 현재데이터의수 : %d \n", LCount(&list)); if(lfirst(&list, &ppos)) ShowPointPos(ppos); while(lnext(&list, &ppos)) ShowPointPos(ppos); printf("\n");...... Data Structures and Algorithms 27

PointListMain.c : 삭제 int main(void)...... /*** xpos 가 2 인모든데이터삭제 ***/ comppos.xpos=2; comppos.ypos=0; if(lfirst(&list, &ppos)) if(pointcomp(ppos, &comppos)==1) ppos=lremove(&list); free(ppos); while(lnext(&list, &ppos)) if(pointcomp(ppos, &comppos)==1) ppos=lremove(&list); free(ppos);...... Data Structures and Algorithms 28

배열기반리스트의장점과단점 배열기반리스트의단점 배열길이는초기에결정되며, 변경불가능 삭제과정에서데이터이동 ( 복사 ) 가매우빈번함 배열기반리스트의장점 쉬운데이터참조 : 인덱스값으로어디든한번에참조가능 Data Structures and Algorithms 29

연결리스트의개념적이해 Data Structures and Algorithms 30

Linked 의의미 typedef struct _node int data; // 데이터를담을공간 struct _node * next; // 연결의도구! Node; Data Structures and Algorithms 31

LinkedRead.c: 초기화 typedef struct _node int data; struct _node * next; Node; head, tail, cur 이연결리스트의핵심! head 와 tail 은연결을추가및유지하기위한것 cur 은참조및조회를위한것 int main(void) Node * head = NULL; Node * tail = NULL; Node * cur = NULL; Node * newnode = NULL; int readdata;.... Data Structures and Algorithms 32

LinkedRead.c: 삽입 1 while(1) printf(" 자연수입력 : "); scanf("%d", &readdata); if(readdata < 1) break; // 노드의추가과정 newnode = (Node*)malloc(sizeof(Node)); newnode->data = readdata; newnode->next = NULL; if(head == NULL) head = newnode; else tail->next = newnode; tail = newnode; Data Structures and Algorithms 33

LinkedRead.c: 삽입 2 while(1) printf(" 자연수입력 : "); scanf("%d", &readdata); if(readdata < 1) break; // 노드의추가과정 newnode = (Node*)malloc(sizeof(Node)); newnode->data = readdata; newnode->next = NULL; if(head == NULL) head = newnode; else tail->next = newnode; tail = newnode; Data Structures and Algorithms 34

LinkedRead.c: 데이터순회 if(head == NULL) printf(" 저장된자연수가존재하지않습니다. \n"); else cur = head; printf("%d ", cur->data); while(cur->next!= NULL) cur = cur->next; printf("%d ", cur->data); Data Structures and Algorithms 35

LinkedRead.c: 데이터삭제 if(head == NULL) return 0; else Node * delnode = head; Node * delnextnode = head->next; printf("%d 을삭제 \n", head->data); free(delnode); while(delnextnode!= NULL) delnode = delnextnode; delnextnode = delnextnode->next; printf("%d 을삭제 \n", delnode->data); free(delnode); Data Structures and Algorithms 36

연결리스트의 ADT 구현 Data Structures and Algorithms 37

정렬기능추가된연결리스트의 ADT 리스트자료구조의 ADT 리스트의초기화 typedef int LData; 리스트자료구조의 ADT 다음데이터의참조 ( 반환 ) 을목적으로호출 데이터저장 바로이전에참조 ( 반환 ) 이이뤄진데이터의삭제 저장된데이터의탐색및탐색초기화 현재저장되어있는데이터의수를반환 Data Structures and Algorithms 10 Data Structures and Algorithms 11 함수포인터가사용됨 Data Structures and Algorithms 38

새로운노드의추가위치 새노드를연결리스트의머리에추가 장점 : 포인터변수 tail 이불필요 단점 : 저장된순서를유지하지않음 새노드를연결리스트의꼬리에추가 장점 : 저장된순서가유지 단점 : 포인터변수 tail 이필요 Data Structures and Algorithms 39

SetSortRule 함수선언 void SetSortRule ( List * plist, int (*comp)(ldata d1, LData d2) ); 반환형이 int이고, int (*comp)(ldata d1, LData d2) LData형인자를두개전달받는, int (*comp)(ldata d1, LData d2) 함수의주소값을전달해라! int (*comp)(ldata d1, LData d2) 인자로전달이가능한함수의예 int WhoIsPrecede(LData d1, LData d2) // typedef int LData; if(d1 < d2) return 0; // d1이정렬순서상앞선다. else return 1; // d2가정렬순서상앞서거나같다. Data Structures and Algorithms 40

정렬의기준을결정하는함수에대한약속! 약속에근거한함수정의의예 int WhoIsPrecede(LData d1, LData d2) if(d1 < d2) return 0; // d1 이정렬순서상앞선다. else return 1; // d2 가정렬순서상앞서거나같다. 함수호출예 int cr = WhoIsPrecede(D1, D2); Data Structures and Algorithms 41

우리가구현할더미노드기반연결리스트 머리에새노드를추가하되더미노드없는경우 첫번째노드와두번째이후의노드추가및삭제방식이다를수있음 머리에새노드를추가하되더미노드있는경우 노드의추가및삭제방식이항상일정 LinkedRead.c 와문제 04-2 의답안인 DLinkedRead.c 를비교 Data Structures and Algorithms 42

정렬기능추가된연결리스트의구조체 노드의구조체표현 typedef struct _node // typedef int LData; LData data; // 필요한변수들은모두구조체로묶어야함 struct _node * next; Node; 연결리스트의구조체표현 typedef struct _linkedlist Node * head; // 더미노드를가리키는멤버 Node * cur; // 참조및삭제를돕는멤버 Node * before; // 삭제를돕는멤버 int numofdata; // 저장된데이터의수를기록하기위한멤버 int (*comp)(ldata d1, LData d2); // 정렬의기준을등록하기위한멤버 LinkedList; Data Structures and Algorithms 43

정렬기능추가된연결리스트헤더파일 : DLinkedList.h #define TRUE 1 #define FALSE 0 typedef int LData; typedef struct _node LData data; struct _node * next; Node; typedef LinkedList List; void ListInit(List * plist); void LInsert(List * plist, LData data); int LFirst(List * plist, LData * pdata); int LNext(List * plist, LData * pdata); LData LRemove(List * plist); int LCount(List * plist); typedef struct _linkedlist void SetSortRule(List * plist, int (*comp)(ldata d1, LData d2)); Node * head; Node * cur; Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; Data Structures and Algorithms 44

더미노드연결리스트구현 : 초기화 초기화함수 void ListInit(List * plist) plist->head = (Node*)malloc(sizeof(Node)); // 더미노드의생성 plist->head->next = NULL; plist->comp = NULL; plist->numofdata = 0; typedef struct _linkedlist Node * head; Node * cur; Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; Data Structures and Algorithms 45

더미노드연결리스트구현 : 삽입 1 void LInsert(List * plist, LData data) if(plist->comp == NULL) // 정렬기준이없다면 FInsert(plist, data); // 머리에노드를추가 else // 정렬기준이있다면 SInsert(plist, data); // 정렬기준에따라노드추가 void FInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); // 새노드생성 newnode->data = data; // 새노드에데이터저장 newnode->next = plist->head->next; // 새노드가다른노드를가리키게함 plist->head->next = newnode; // 더미노드가새노드를가리킴 (plist->numofdata)++; // 저장된노드의수를하나증가 Data Structures and Algorithms 46

더미노드연결리스트구현 : 삽입 2 더미노드를사용하면모든경우에동일한삽입과정을거침 void FInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); // 새노드생성 newnode->data = data; // 새노드에데이터저장 newnode->next = plist->head->next; // 새노드가다른노드를가리키게함 plist->head->next = newnode; // 더미노드가새노드를가리킴 (plist->numofdata)++; // 저장된노드의수를하나증가 Data Structures and Algorithms 47

더미노드연결리스트구현 : 참조 1 int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) // 더미노드가 NULL을가리킨다면, return FALSE; // 반환할데이터가없음 plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // cur이가리키던것을 before가가리킴 // cur은그다음노드를가리킴 // cur이가리키는노드의데이터전달 // 데이터반환성공 Data Structures and Algorithms 48

더미노드연결리스트구현 : 참조 2 int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) // 더미노드가 NULL을가리킨다면, return FALSE; // 반환할데이터가없음 plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // cur이가리키던것을 before가가리킴 // cur은그다음노드를가리킴 // cur이가리키는노드의데이터전달 // 데이터반환성공 Data Structures and Algorithms 49

더미노드연결리스트구현 : 삭제 1 cur 은삭제후재조정의과정을거쳐야함 before 는 LFirst 또는 LNext 호출시재설정됨 삭제전 삭제후 Data Structures and Algorithms 50

더미노드연결리스트구현 : 삭제 2 LData LRemove(List * plist) Node * rpos = plist->cur; LData rdata = rpos->data; plist->before->next = plist->cur->next; plist->cur = plist->before; Dlinkedlist.c DLinkedlist.h DLinkedlistmain.c 확인하기 free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 51

연결리스트의정렬삽입의구현 Data Structures and Algorithms 52

정렬기준설정 단순연결리스트의정렬관련요소세가지 1 2 void SetSortRule(List * plist, int (*comp)(ldata d1, LData d2)) plist->comp = comp; SetSortRule 함수정의에 정렬기준함수포함 typedef struct _linkedlist SetSortRule 함수를통해전달된 Node * head; 함수의리턴정보저장을위한 Node * cur; LinkedList의멤버 comp Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; 3 void LInsert(List * plist, LData data) if(plist->comp == NULL) Sinsert 함수가 comp의정렬기준 FInsert(plist, data); 대로데이터를저장 else SInsert(plist, data); Data Structures and Algorithms 53

SInsert 함수 void SInsert(List * plist, LData data) Node * newnode = (Node*)malloc(sizeof(Node)); Node * pred = plist->head; newnode->data = data; // 새노드가들어갈위치를찾기위한반복문! while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 newnode->next = pred->next; pred->next = newnode; (plist->numofdata)++; Data Structures and Algorithms 54

다음상황에서 SInsert(&slist, 5); 실행 Data Structures and Algorithms 55

comp 가 0 을반환한다는것은첫번째인자인 data 가정렬순서상앞서기 때문에 head 에가까워야한다는의미! Data Structures and Algorithms 56

Data Structures and Algorithms 57

정렬의핵심인 while 반복문 반복의조건 1 pred->next!= NULL pred 가리스트의마지막노드를가리키는지묻기위한연산 반복의조건 2 plist->comp(data, pred->next->data)!= 0 새데이터와 pred 의다음노드에저장된데이터의우선순위비교를위한함수호출 while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 Data Structures and Algorithms 58

comp 의반환값과그의미 comp 가 0 을반환 첫번째인자인 data 가정렬순서상앞서서 head 에더가까워야하는경우 comp 가 1 을반환 두번째인자인 pred->next->data 가정렬순서상앞서서 head 에더가까워야하는경우 while(pred->next!= NULL && plist->comp(data, pred->next->data)!= 0) pred = pred->next; // 다음노드로이동 Data Structures and Algorithms 59

정렬의기준을설정하기위한함수의정의 함수의정의기준 두개의인자를전달받도록함수를정의 첫번째인자의정렬우선순위가높으면 0 을, 그렇지않으면 1 을반환 오름차순정렬을위한함수의정의 Dlinkedlist.c DLinkedlist.h int WhoIsPrecede(int d1, int d2) DLinkedlistSortmain.c if(d1 < d2) return 0; // d1이정렬순서상앞선다. else return 1; // d2가정렬순서상앞서거나같다. Data Structures and Algorithms 60

원형연결리스트 Data Structures and Algorithms 61

원형연결리스트의이해 단순연결리스트의마지막노드는 NULL 을가리킴 원형연결리스트의마지막노드는첫번째노드를가리킴 Data Structures and Algorithms 62

원형연결리스트의노드추가 모든노드가연결되어있기때문에머리와꼬리구분이없음 두경우의노드연결순서가같다 head 가가리키는노드가다르다. Data Structures and Algorithms 63

원형연결리스트의장점 단순연결리스트처럼머리와꼬리를가리키는포인터변수를각각두지않아도, 하나의포인터변수만있어도머리또는꼬리에노드를간단히추가할수있다. Data Structures and Algorithms 64

원형연결리스트 연결리스트를가리키는포인터변수하나로머리와꼬리를쉽게확인가능 꼬리를가리키는포인터변수 : tail 머리를가리키는포인터변수 : tail->next Data Structures and Algorithms 65

변형된원형연결리스트의구현범위 이전에구현한연결리스트와기능동일 조회관련 Lfirst 삭제관련 Lremove 이외의부분 조회관련 Lnext 원형연결리스트를계속해서순환하는형태로변경! 삽입관련 앞과뒤에삽입이가능하도록두개의함수정의! 정렬관련 정렬과관련된부분전부제거 Data Structures and Algorithms 66

원형연결리스트의헤더파일과초기화함수 CLinkedList.h typedef int Data; typedef struct _node Data data; struct _node * next; Node; typedef struct _CLL Node * tail; Node * cur; Node * before; int numofdata; CList; typedef CList List; void ListInit(List * plist); void LInsert(List * plist, Data data); void LInsertFront(List * plist, Data data); int LFirst(List * plist, Data * pdata); int LNext(List * plist, Data * pdata); Data LRemove(List * plist); int LCount(List * plist); CLinkedList.c void ListInit(List * plist) plist->tail = NULL; plist->cur = NULL; plist->before = NULL; plist->numofdata = 0; // 모든멤버를 NULL 과 0 으로초기화 Data Structures and Algorithms 67

원형연결리스트구현 : 첫번째노드삽입 void LInsertFront(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) // 첫노드 plist->tail = newnode; newnode->next = newnode; else // 두번째노드이후 newnode->next = plist->tail->next; plist->tail->next = newnode; (plist->numofdata)++; Data Structures and Algorithms 68

원형연결리스트구현 : 두번째이후노드머리로삽입 void LInsertFront(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) // 첫노드 plist->tail = newnode; newnode->next = newnode; else // 두번째노드이후 newnode->next = plist->tail->next; plist->tail->next = newnode; 새노드추가 (plist->numofdata)++; Data Structures and Algorithms 69

원형연결리스트구현 : 앞과뒤의삽입과정비교 1 노드를머리에추가한결과 노드를꼬리에추가한결과 Data Structures and Algorithms 70

원형연결리스트구현 : 앞과뒤의삽입과정비교 2 void LInsert(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if(plist->tail == NULL) tail의위치가다름 plist->tail = newnode; newnode->next = newnode; else newnode->next = plist->tail->next; plist->tail->next = newnode; plist->tail = newnode; //Linsertfront와차이 (plist->numofdata)++; Data Structures and Algorithms 71

원형연결리스트구현 : 조회 LFirst int LFirst(List * plist, Data * pdata) if(plist->tail == NULL) // 저장된노드가없다면 return FALSE; plist->before = plist->tail; plist->cur = plist->tail->next; *pdata = plist->cur->data; return TRUE; typedef struct _CLL Node * tail; Node * cur; Node * before; int numofdata; CList; cur 이가리키는노드가머리! typedef CList List; Data Structures and Algorithms 72

원형연결리스트구현 : 조회 LNext int LNext(List * plist, Data * pdata) if(plist->tail == NULL) // 저장된노드가없다면 return FALSE; plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; 이어지는 LNext 호출결과 원형연결리스트이므로 리스트의끝을검사하는 코드가없다! Data Structures and Algorithms 73

원형연결리스트구현 : 노드의삭제 ( 복습 ) 핵심연산 1. 삭제할노드의이전노드가, 삭제할노드의다음노드를가리키게한다. 2. 포인터변수 cur 을한칸뒤로이동시킨다. // 더미기반단순연결리스트의삭제! LData LRemove(List * plist) Node * rpos = plist->cur; LData rdata = rpos->data; 핵심연산 2 plist->before->next = plist->cur->next; plist->cur = plist->before; 핵심연산 1 free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 74

원형연결리스트구현 : 노드의삭제 ( 그림비교 ) 더미기반단순연결리스트 원형연결리스트 삭제과정이비슷해보이지만원형연결리스트에는더미노드가없기때문에 상황에따라삭제의과정이달라짐 Data Structures and Algorithms 75

원형연결리스트노드삭제구현 1 Data LRemove(List * plist) Node * rpos = plist->cur; Data rdata = rpos->data; if(rpos == plist->tail) // 삭제대상을 tail이가리킨다면 if(plist->tail == plist->tail->next) // 마지막남은노드라면 plist->tail = NULL; else plist->tail = plist->before; plist->before->next = plist->cur->next; plist->cur = plist->before; free(rpos); (plist->numofdata)--; return rdata; Data Structures and Algorithms 76

원형연결리스트노드삭제구현 2 예외상황 1. 삭제할노드를 tail 이가리키는경우 2. 삭제할노드를 tail 이가리키는데, 그노드가마지막노드라면 Data Structures and Algorithms 77

이중연결리스트 Data Structures and Algorithms 78

양방향연결리스트의이해 양방향리스트를위한노드의표현 typedef struct _node Data data; struct _node * next; struct _node * prev; Node; Data Structures and Algorithms 79

양방향으로노드를연결하는이유! 오른쪽노드로의이동이쉽고, 양방향으로이동이가능하다! 양방향으로연결하는코드도복잡하지않음 // 단순연결리스트의 LNext int LNext(List * plist, LData * pdata) if(plist->cur->next == NULL) return FALSE; // 양방향연결리스트의 LNext int LNext(List * plist, Data * pdata) if(plist->cur->next == NULL) return FALSE; plist->before = plist->cur; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; // before 유지불필요 plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; Data Structures and Algorithms 80

양방향연결리스트모델 LRemove 함수를 ADT에서제외 ADT에왼쪽노드의데이터를참조하는 LPrevious 함수를추가 새노드는머리에추가 Data Structures and Algorithms 81

양방향연결리스트의헤더파일 : DBLinkedList.h typedef int Data; typedef struct _node Data data; struct _node * next; struct _node * prev; Node; typedef struct _dblinkedlist Node * head; Node * cur; int numofdata; DBLinkedList; typedef DBLinkedList List; void ListInit(List * plist); void LInsert(List * plist, Data data); int LFirst(List * plist, Data * pdata); int LNext(List * plist, Data * pdata); // LPrevious 함수는 LNext 함수와반대로이동 int LPrevious(List * plist, Data * pdata); int LCount(List * plist); Data Structures and Algorithms 82

연결리스트의구현 : 리스트의초기화 ListInit 함수의정의에참조해야하는구조체의정의 typedef struct _dblinkedlist Node * head; Node * cur; int numofdata; DBLinkedList; head 와 numofdata 만초기화필요 멤버 cur 은조회의과정에서초기화됨 void ListInit(List * plist) plist->head = NULL; plist->numofdata = 0; Data Structures and Algorithms 83

연결리스트의구현 : 노드삽입의구분 1 빈리스트에삽입 Data Structures and Algorithms 84

연결리스트의구현 : 노드삽입의구분 2 두번째이후부터의노드삽입 1 2 3 4 Data Structures and Algorithms 85

연결리스트의구현 void LInsert(List * plist, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = plist->head; if(plist->head!= NULL) plist->head->prev = newnode; newnode->prev = NULL; plist->head = newnode; (plist->numofdata)++; Data Structures and Algorithms 86

양방향연결리스트의구현 : 데이터조회 int LFirst(List * plist, Data * pdata) if(plist->head == NULL) return FALSE; plist->cur = plist->head; *pdata = plist->cur->data; int LNext(List * plist, Data * pdata) if(plist->cur->next == NULL) return FALSE; plist->cur = plist->cur->next; *pdata = plist->cur->data; return TRUE; return TRUE; int LPrevious(List * plist, Data * pdata) if(plist->cur->prev == NULL) return FALSE; LFirst와 LNext는단방향연결리스트동일 plist->cur = plist->cur->prev; *pdata = plist->cur->data; return TRUE; LPrevious 와 LNext 의차이는이동방향뿐 Data Structures and Algorithms 87