제 4 장 L i s t

4.1 리스트 표현 정의 a0 a1 a2 … ai ai+1 … an-1 가장 단순한 데이타 구조중의 하나. 각 데이타가 배열과 같이 연속되는 기억장소에 저장되는 리스트를 선형 리스트(linear list), 또는 순서 리스트 (ordered list) 라고 한다. A = (a0, a1, . . . ai, ai+1, . . ., an-1) 로 표시. a0 a1 a2 … ai ai+1 … an-1

4.1 리스트 표현 종류 (1) 1차원 배열을 이용한 방법 가장 보편적인 표현 방법 순차적 사상 (sequential mapping) 선형 리스트의 i 번째 항목은 i 번째에 저장 포인터가 필요 없다. (2) 포인터(Pointer)를 이용한 방법 연결리스트(linked list)로 나타냄 기억장소를 최대한 이용할 수 있다. 항목에 대한 삽입, 삭제, 교환 등의 연산이 복잡하다.

(1) 1차원 배열을 이용한 방법 특성 주어진 선형 리스트를 1차원 배열 list[n]으로 나타내는 것이다. 선형 리스트의 i 번째 항목은 i 번째에 저장 순차적으로 저장 임의의 위치에서 삽입과 삭제가 가능. 리스트의 크기가 배열의 크기에 의해 제한을 받는다. 기존 원소들 사이에 새로운 원소를 삽입할 때 다른 원소들을 이동시켜야 한다. 원소 삭제 시 그 공간은 비어 있게 된다.

(1) 1차원 배열을 이용한 방법 항목 삭제 (C 를 삭제 시) A A B B C D D E E n개의 항목이 있을 경우 평균 이동횟수 = (n-1) / 2 회 A B D C E A B E D 삭제를 한 후 2개의 데이타 이동 필요

(1) 1차원 배열을 이용한 방법 항목 삽입 (C 삽입 시) A A B B D C E D E n개의 항목이 있을 경우 평균 이동횟수 = (n+1) / 2 회 A A 삽입을 위해 2개의 데이터 이동이 필요 B B D C E D E

(1) 1차원 배열을 이용한 방법 선형리스트의 장단점 장점 단점 가장 간단한 데이터 구조이다. 메모리 밀도(memory density)가 1이므로 다른 데이터구조보다 뛰어나다. 메모리 밀도: 일정 크기의 기억 장소에 얼마나 많은 데이터가 저장될 수 있는지를 나타내는 조밀도 단점 항목 삽입 시 연속적인 기억장소를 요구한다 삽입, 삭제 시 선형구조를 유지해야 하므로 많은 데이타의 이동으로 인한 속도의 저하가 발생한다 메모리 밀도 = 정보들의 총수 또는 논리적 정보 단위의 총수 비트들의 총수 물리적 정보 단위의 총수

(2) 포인터를 이용한 방법 특성 1차원 배열을 이용한 단점을 극복하기 위하여 링크(link)라는 포인터를 이용 링크는 다음 원소의 시작 주소를 나타내는 포인터. 선형 리스트를 링크를 사용하여 표현한 리스트를 연결 리스트(linked list)라고 한다. 연결 리스트에서 리스트 원소를 일반적으로 노드라고 부른다. 연결 리스트의 각 노드는 자료를 저장하는 부분과 다른 노드를 가리키는 포인터의 두 개 필드로 구성된다.

(2) 포인터를 이용한 방법 특성

(3) 리스트 연산 선형 리스트에 적용할 수 있는 연산 ․ 이용(access): 리스트를 구성하는 임의의 원소의 위치를 파악하여 그 노드에 대한 데이터를 읽는 연산 ․ 삽입(insertion): 리스트에 새로운 원소를 삽입하는 연산 ․ 삭제(deletion): 리스트에서 어떤 원소를 제거하는 연산 ․ 변경(update): 리스트의 어떤 원소의 내용을 변경시키는 연산 ․ 탐색(search): 리스트의 임의의 원소의 내용을 찾는 연산 ․ 정렬(sort): 리스트를 구성하는 모든 원소들을 어떤 순서에 의하여 정렬하는 연산 ․ 복사(copy): 리스트를 이루는 어떤 원소들, 혹은 리스트 전체를 복사하여 새로운 리스트를 만드는 연산 ․ 분리(split): 하나의 리스트를 둘 이상의 리스트로 분리하는 연산 ․ 합병(merge): 둘 이상의 리스트를 하나의 리스트로 합치는 연산

4.2 malloc( )와 free( ) malloc( ) 함수 - 새로운 노드를 만들기 위하여 메모리를 할당받는 함수. int *pi; pi = (int *)malloc(sizeof(int)); *pi = 10; printf("%d:",*pi); free(pi); 정수 '10'을 저장하기 위하여 포인터 변수'pi'를 정의 정수형 크기만큼의 메모리를 할당받은 후(malloc)'10'을 저장하고 출력하는 기능. 마지막으로 'pi'를 삭제(free) 한다.

4.3 단순 연결 리스트(Single Linked List) 리스트를 구성하는 각 노드가 링크라는 포인터 변수에 의해 연결. 연결 리스트의 이름은 가장 앞 노드의 이름과 같다. 리스트의 중간에 새로운 노드를 삽입하거나 삭제 시에 다른 노드들의 자리 이동이 불필요하다.

(1) 노드 생성 노드 생성연산 노드는 자료를 저장하는 필드와 링크라는 포인터 변수로 구성. 연결 리스트의 이름은 'ptr'이며 'NULL'로 초기화된다. 새로운 노드를 생성하기 위하여 malloc( ) 함수를 사용. 생성된 노드의 자료 필드에 "SUNDAY"를 저장하기 위하여 strcpy( ) 함수를 사용. "SUNDAY" 노드 다음에 오는 노드가 없으므로 링크 필드는'NULL'값을 가지게 한다. ① ptr = (listPtr)malloc(sizeof(listNode)) ② strcpy(ptr→data, "SUNDAY"); ptr→link = NULL; typedef struct listNode *listPtr; struct listNode { char data[10]; listPtr link; }; listPtr ptr = NULL;

(1) 노드 생성 typedef struct listNode *listPtr; struct listNode { char data[10]; listPtr link; }; listPtr ptr = NULL;

(2) 2개의 노드 연결 ① 첫 번째, 두 번째 노드 생성 listPtr first, second, ptr; first = (listPtr)malloc(sizeof(listNode)); second = (listPtr)malloc(sizeof(listNode)); ② 'first'노드에는 "SUNDAY"를,'second'노드에는 "TUESDAY"를 자료 필드에 저장. strcpy(first→data, "SUNDAY"); strcpy(second→data, "TUESDAY");

(2) 2개의 노드 연결 ③ 2개의 노드를 연결하기 위하여 'first'노드의 링크 필드가 'second'노드를 가리키게 함. first→link = second; ④ 'second‘ 노드의 링크 필드에는 'NULL'을 지정. second→link = NULL; ⑤ ptr = first; 연결 리스트의 이름은'first'가 된다.

(3) 노드 삽입 'first'노드와'second'노드 사이에 'temp'노드("MONDAY")를 삽입하는 과정.

(3) 노드 삽입 함수 insert( ) void insert(listPtr *ptr, listPtr node) { ① 새로운 노드'temp'를 생성한다. listPtr temp; temp = (listPtr)malloc(sizeof(listNode)); ② 노드'temp'에 "MONDAY"를 저장한다. strcpy(temp→data, "MONDAY"); ③ 리스트'ptr'내의 이름이'node'인 노드 뒤에'temp'노드를 삽입한다 if(*ptr){ /* NOT NULL */ temp→link = node→link; node→link = temp; } ④ 만약 리스트'ptr'이 아직 한 개의 노드도 없는 리스트라면'temp'노드가 리스트'ptr'의 처음 노드로 삽입된다. else{ /* EMPTY LIST */ temp→link = NULL; ⑤ 맨 처음 노드가 된'temp'를 리스트의 이름인'ptr'이 되게 한다. *ptr=temp; } } 함수 사용하는 방법 : insert(&ptr, first);

(4) 노드 삭제 노드 삭제시 고려할 3개의 포인터 시작 포인터 : ptr 삭제할 노드 포인터 : nodeDeleted 삭제할 노드 바로 앞 노드 포인터 : trail

(4) 노드 삭제 delete() 함수 void delete(listPtr *ptr, listPtr trail, listPtr nodeDeleted) { ①'trail'의 링크 필드가'nodeDeleted'다음 노드를 가리키게 한다. if(trail) trail→link = nodeDeleted→link; ② 만약'trail'이 없으면 리스트 첫 번째 노드를 삭제하는 것이다. else *ptr = (*ptr)→link; ③ 메모리를 반납한다. free(nodeDeleted); } ⅰ) 리스트의 첫 번째 노드를 삭제하면 다음과 같이 호출한다. delete(&ptr, NULL, first); ⅱ) 리스트의 가운데 노드인'temp'를 삭제하려면 다음과 같이 호출한다. delete(&ptr, first, temp);

(5) 리스트 출력과 삭제 리스트 출력 리스트 삭제 void printList(listPtr ptr) { for( ; ptr; ptr = ptr→link) printf("%s", ptr→data); } 리스트 삭제 void erase(listPtr *ptr) { listPtr temp; while(*ptr) { temp = *ptr; *ptr = (*ptr)→link; free(temp);}

4.4 단순 연결 리스트를 이용한 스택과 큐 4.4.1 단순 연결 리스트를 이용한 스택 ① 자료 필드의 구조를 정의한다. typedef struct { char data[10]; } listNode; ② 노드의 구성을 자료 필드(item)와 링크 필드(link)로 정의한다. typedef struct stack *stackPtr; struct stack { listNode item; stackPtr link; }; ③ 스택의 맨 위를 가리키는 포인터 변수인'top'을 정의하고'NULL'로 초기화한다. stackPtr top; top=NULL;

(1) 스택에 노드 첨가(Push) 함수 호출 - push(&top, item); void push(stackPtr *top, listNode item) { ① 새로운 노드'temp'를 생성. stackPtr temp = (stackPtr)malloc(sizeof(stack)); 노드'temp'의'item'필드에 저장할 자료'item'을 저장. temp→item = item; ②'temp'의 링크 필드가'top'을 가리키게 한다. temp→link = *top; ③ 새로 삽입된'temp'가 새로운'top'이 된다. *top = temp; } 함수 호출 - push(&top, item);

(2) 스택의 노드 삭제(Pop) listNode pop(stackPtr *top) { stackPtr temp = *top; /*임시 포인터 변수'temp'를 정의하여 스택의'top'을 가리키게 한다. */ listNode item; /* 'top'이 가리키는 노드의 자료 필드 값을 저장할 변수'item'을 정의한다.*/ if(!temp) { printf("stack empty"); exit(1); } /* 'temp'가 가리키는 값이 없으면 스택이 비어있는 것이므로 스택이 비었다는 메시지를 출력한다. */ item = temp→item; /* 'temp'가 가리키는 자료 필드 값을 변수'item'에 저장. */ *top = temp→link; /* 'top'을'temp'의 링크 필드가 가리키는 노드를 변경한다. 즉,'top'을 리스트 내 다음 노드로 변경한다. */ free(temp); /* 삭제(반환, 검색)할 노드인'temp'를 지운다. */ return(item); /* 받아 놓은 자료 필드 값'item'을 반환한다. */ } 함수호출 - item = pop(&top);

4.4.2 단순 연결 리스트를 이용한 큐 노드 구조의 정의. typedef struct queue *queuePtr; listNode item; queuePtr link; }; queuePtr front, rear; front = NULL;

(1) 큐에 노드 첨가(addQ) void addQ(queuePtr *front, queuePtr *rear, listNode item) { /* 삽입할 노드'temp'를 생성. 'temp'의 item에 저장할 자료 저장, 링크 필드(item)에'NULL'을 저장*/ queuePtr temp = (queuePtr)malloc(sizeof(queue)); temp→item = item; temp→link = NULL; if(*front) (*rear)→link = temp; /* 이미 큐에 저장된 노드가 있으면 가장 뒤(rear) 노드와 링크 필드에'temp'를 첨가*/ else *front = temp; /*큐에 이미 저장된 노드가 없으면, 'temp'를'front'로 한다*/ *rear=temp; /* 방금 첨가된'temp'가 새로이'rear'가 된다*/ } 함수호출 - addQ(&front, &rear, item);

(1) 큐에 노드 첨가(addQ)

(2) 큐에 노드 삭제(deleteQ) listNode deleteQ(queuePtr *front) { queuePtr temp = *front; /* 큐의 가장 앞(front)에 있는 노드를 임시 변수'temp'를 가리키게 한다*/ listNode item; /*삭제할 노드에 저장된 자료 필드에 저장된 값을 받아둘'item'을 정의*/ if(!temp) { printf("Queue is empty"); exit(1); } /*만약, 가장 앞을 가리키는'temp'가 없다면 큐가 비었다는 메시지를 출력하고 종료*/ item = temp→item; /* 'temp'노드의 자료 필드에 저장된 값을'item'에 저장*/ *front = temp→link; /* 큐의 가장 앞 노드(front)를 삭제시킬 노드(temp)의 다음 노드(temp→link)로 변경*/ free(temp); /* 마지막으로 노드'temp'를 삭제하고 받아둔 자료'item'을 반환*/ return item; } 함수호출 - item = deleteQ(&front);

(2) 큐에 노드 삭제(deleteQ)

4.5 단순 연결리스트 사용 예 : 다항식 다항식을 컴퓨터 내부에 표현하기 위하여 단순 연결 리스트를 이용. 다항식을 지수의 내림차순으로 정리하면, 각 항은 <지수, 계수> 쌍으로 표현된다.

4.5.1 배열을 이용한 다항식 표현

4.5.2 단순 연결 리스트를 이용한 다항식 표현 계수, 지수, 링크 구조의 표현 typedef struct polyNode *polyPtr; struct polyNode { int coefficient; /* 계수 */ int exponent; /* 지수 */ polyPtr link; /* 링크 */ };

4.5.2 단순 연결 리스트를 이용한 다항식 표현 다항식 a와 b를 가리키는 포인터 변수의 선언. polyPtr a, b;

4.5.3 다항식 덧셈 #define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y) ? 0 : 1 polyPtr padd(polyPtr a, polyPtr b) { /* 다항식 a와 b를 덧셈하는 프로그램 */ polyPtr front, rear, temp; int sum; rear = (polyPtr)malloc(sizeof(polyNode)); if(IS_FULL(rear)) { /*큐가 찼는지를 검사 */ fprintf(stderr, "The memory is full\n"); exit(1);} front = rear; while(a && b) switch(COMPARE(a→exponent, b→exponent)){ case -1 : /* a→exponent < b→exponent */ attach(b→coefficient, b→exponent, &rear); b = b→link; break; case 0 : /* a→exponent == b→exponent */ sum = a→coefficient + b→coefficient; if(sum) attach(sum, a→exponent, &rear); a = a→link;b= b→link; break; case 1 : /* a→exponent > b→exponent */ attach(a→coefficient, a→exponent, &rear); a = a→link; } /* 다항식 a와 다항식 b의 나머지를 복사 */ for( ; a; a = a→link) attach(a→coefficient, a→exponent, &rear); for( ; b; b = b→link) attach(b→coefficient, b→exponent, &rear); rear→link = NULL; /* 필요 없는 초기 노드를 삭제 */ temp = front; front = front→link; free(temp); return front;

4.5.3 다항식 덧셈 void attach(float coefficient, int exponent, polyPtr *ptr) { /* 새로운 노드를 만들어서 ptr이 가리키는 위치에 저장 */ polyPtr temp; temp = (polyPtr)malloc(sizeof(polyNode)); if(IS_FULL(temp)) { fprintf(stderr, "The memory is full\n"); exit(1); } temp→coefficient = coefficient; temp→exponent = exponent; (*ptr)→link = temp; *ptr = temp;

4.5.3 다항식 덧셈 다항식 a와 b가 표현된 방법과 수행결과

4.5.4 원형 리스트 원형 연결 리스트의 정의 원형 연결 리스트의 구조 마지막 노드의 포인터를 null이 아닌 첫번째 노드의 주소를 가리키도록 구성하는 연결 리스트 원형 연결 리스트의 구조 헤더 d1 d2 dn-1 dn …

4.5.4 원형 리스트 리스트 ‘avail’에 연결하여 반납하는 함수 circleErase() void circleErase(polyPtr *ptr) { polyPtr temp; if(*ptr) { ①'ptr'의 링크 필드가 가리키는 노드를'temp'가 가리킨다 temp = (*ptr)→link; ②'ptr'의 링크 필드는 이제'avail'을 가리킨다. (*ptr)→link = avail; ③'avail'이'temp'를 가리키게 한다. avail = temp; ④ 이제'ptr'은'NULL'이 된다. *ptr = NULL; }

4.5.4 원형 리스트 함수 circleErase()

4.5.4 원형 리스트 다항식의 원형리스트 표현

4.5.4 원형 리스트 다항식a와 b를 덧셈하여 d에 저장하는 알고리즘 ① /* a와 b head node를 건너뜀 */ a = a→link; b = b→link; ② d를 생성한다. ③ a와 b를 더하여, 더해진 항을 저장하면서 리스트를 만든다. ④ lastd→link = d; /* 마지막 노드가 처음 노드를 가리키게 하여 원형 리스트를 만든다. */ ⑤ return(d);

4.6 주요 리스트 연산 (1) List를 역순으로 만든다. listPtr invert(listPtr lead) { listPtr middle, trail; middle = NULL; while(lead) { trail = middle; middle=lead; lead=lead→link; middle→link=trail; } return middle; }

(2) 두 List 연결하기 listPtr concatenate(listPtr ptr1, listPtr ptr2) { listPtr temp; 'ptr1'이 없으면 if(!(ptr1)) /* !(ptr1) */ 'ptr2'를 반환한다. return ptr2; else { 'ptr1'이 존재하고,'ptr2'도 존재한다면 if(ptr2) { 'ptr1'의 마지막 노드를 찾아서 for(temp = ptr1; temp→link != NULL; temp = temp→link); 'ptr1'의 마지막 노드의 링크 필드가'ptr2'를 가리키게 한다. temp→link = ptr2; } 두 개의 리스트가 연결된 뒤'ptr1'을 반환한다. return ptr1;

(3) 원형 List 길이 계산 int length(listPtr ptr) { listPtr temp; 길이를 저장한 변수'count'를 정의한다. int count = 0; if(ptr) { temp = ptr; 리스트'ptr'의 노드 길이를 계산한다. do { count++; temp = temp→link; }while(temp != ptr); } 길이를 반환한다. return count;

4.7 이중 연결 리스트 이중 원형 연결 리스트의 정의 이중 원형 연결 리스트의 구조 오른쪽과 왼쪽 링크를 두고 양방향으로 탐색이 가능하도록 만든 원형 연결 리스트 이중 원형 연결 리스트의 구조 이중 연결 리스트의 세 필드(왼쪽 링크 필드(llink), 자료 필드(data), 오른쪽 링크 필드(rlink))의 선언. typedef struct node *nodePtr; struct node { nodePtr llink; int data; nodePtr rlink; }

4.7 이중 연결 리스트 이중 원형 연결 리스트를 이용한 원형리스트 ① 먼저 헤드 노드(head node)를 만든다. ② 새로운 자료가 생길 때마다 노드를 생성하여 다음과 같이 연결한다.

(1) 새로운 노드 삽입 void dinsert(nodePtr node, nodePtr newNode) { 'newNode'의 왼쪽 링크 필드(llink)가'node'를 가리킨다. ①newNode→llink = node; 'newNode'의 오른쪽 링크 필드(rlink)가'node'의 오른쪽 링크 필드(rlink)가 가리키는 노드를 가리킨다. ②newNode→rlink = node→rlink; 'node'의 오른쪽 링크 필드가 가리키는 노드의 왼쪽 링크 필드(llink)가'newNode'를 가리킨다. ③node→rlink→llink = newNode; 'newNode'의 오른쪽 링크 필드(rlink)가'newNode'를 가리킨다. ④node→rlink = newNode; }

(2) 노드 삭제 void ddelete(nodePtr headNode, nodePtr deleted) { if(headNode == deleted) printf("not Permitted"); else { 그렇지 않으면'deleted'의 llink와 rlink를 다음과 같이 연결한다. ①deleted→llink→rlink = deleted→rlink; ②deleted→rlink→llink = deleted→llink; free(deleted); }