제 4 장. 리스트(List)

4.0 리스트의 개념

4.0 리스트의 개념(1/2) ￭ 리스트의 개념 ￭ 리스트의 분류 ※ 리스트(list)란 원소(element, atom)의 유한한 집합이며, 각 원소가 내부적으로 위치를 갖는 순서화 된 모임 ￭ 리스트의 분류 ※ 선형 리스트(linear list) ※ 비선형 리스트(non-linear list) ※ 연결 리스트(linked list)

4.0 리스트의 개념(1/2) ￭ 노드(node)의 개념 ※ 연결리스트에서는 각 원소들마다 다음 원소를 가리키는 위치정보를 가지고 있게 되는데 이를 포인터 또는 링크(link)라고 하함 ※ 포인터의 사용은 리스트상의 모든 원소가 반드시 연속된 기억장소에 저장될 필요가 없음을 의미함. ※ 포인터로 구성된 연결리스트의 각각의 원소들을 노드라고 함)

4.1 단순 연결 리스트

4.1.1 단순 연결 리스트(1/5) ￭ 단순 연결리스트((singly) linked list)의 개념 ※ 각 노드들이 순차적으로 저장되어있지 않다면 링크를 이용하여 리스트원소들을 나타냄 ※ 리스트의 각 원소들은 자료부분이 1차원 배열구조로 기억되어있으며, 링크부분에 저장된 값은 자료배열의 다음 노드를 가리키는 주소 값을 가진 포인터 임

4.1.1 단순 연결 리스트(2/5) 비연속적리스트를 연결리스트로 표현하는 방법

4.1.1 단순 연결 리스트(3/5) ※ 연결리스트 자료의 “S” 삽입 과정 ⓐ 사용하지 않은 노드를 찾아 주소를 k 로 정한다. ⓑ k 노드의 데이터 영역에 “S"를 넣는다 ⓒ k 노드의 링크 영역에 “null" 값을 넣는다. ⓓ “E"의 링크영역에 주소 k를 넣는다

4.1.1 단순 연결 리스트(4/5) ※ 단순연결 리스트에 새로운 노드를 사용하는 방법 1. insert(head, temp) 2. struct node { 3. char data; 4. struct node *link; 5. } *temp, *head; 6. { 7. struct node *new; 8. new = malloc(sizeof(node)); 9. new->data = “S"; 10. new->link = temp->link; 11. temp->link = new; 12. }

4.1.1 단순 연결 리스트(5/5) ※ 단순연결 리스트에 새로운 노드를 제거하는 방법 1. delete(temp, new) 2. struct node { 3. int data; 4. struct node *link; 5. } *temp, *new; 6. { 7. temp->link = new->link; 8. free(new); 9. }

4.1.2 다수의 연결 리스트의 결합(1/4) ￭ 두개의 연결리스트를 하나로 결합 ※ 두 개의 연결 리스트를 하나로 병합하는 방법 첫 번째 연결 리스트의 tail을 찾아 두 번째 연결 리스트의 head와 연결하면 됨 (즉, 단순 연결 리스트의 끝부분에 새로운 자료를 삽입하는 것으로 생각하자.)

4.1.2 다수의 연결 리스트의 결합(2/4) 두 개의 연결 리스트 병합 과정

4.1.2 다수의 연결 리스트의 결합(3/4) ※ 두개의 연결리스트를 비순환적인 방법으로 병합 1. merge_nonre(first, second) 2. struct node { 3. int data; 4. struct node *link; 5. } *first, *second; 6. { 7. struct node *temp; 8. temp = first; 9. while(temp->link != NULL) temp = temp->link; 10. temp->link = second; 11. }

4.1.2 다수의 연결 리스트의 결합(4/4) ※ 두개의 연결리스트를 순환적인 방법으로 병합 1. merge_re(first, second) 2. struct node { 3. int data; 4. struct node *link; 5. } *first, *second; 6. { 7. if(first->link == NULL) 8. first->link = second; 9. else concatenation(first->link, second); 10. }

4.1.3 연결 리스트로 구현한 스택과 큐(1/6) 스택과 큐의 연결리스트표현

4.1.3 연결 리스트로 구현한 스택과 큐(2/6) ※ 연결 리스트를 이용한 스택에 하나의 노드를 삽입하고, 삭제하는 모듈 1. struct list { 2. char data; 3. struct list *next; 4. }; 5. 6. struct list *top[n]; 7. top[i]=i번째 스택의 top 위치에 있는 노드; 8. top[i]- null; 9. 10. void add_stack(int i, char data) { 11. struct list *new;

4.1.3 연결 리스트로 구현한 스택과 큐(3/6) 12. // 새로운 노드 생성 13. if((new=(struct list *)malloc(sizeof(struct list)))==null) { 14. printf("Memory overflow\n"); 15. exit(0); 16. } 17. new->data=data; 18. new->next=top[i]; 19. top[i]=new; 20. } 21. 22. char delete_stack(ini i) { 23. char data; 24. struct list *pos; 25. //i번째 스택의 top null 여부 조사 26. if(top[i]==null) { 27. printf("Stack Empty\n"); 28. exit(0); 29. } 30. pos=top[i]; 31. data=top[i[]->data 32. top[i]=pos->next; 33. free(pos); //node 삭제 34. return(data); 35. }

4.1.3 연결 리스트로 구현한 스택과 큐(4/6) ※ 연결 리스트를 이용한 큐에 대한 삽입, 삭제 모듈 1. struct list { 2. char data; 3. struct list *next; 4. }; 5. 6. struct list *front[m]; 7. struct list *rear[m]; 8. front[i]=i번째 큐의 front 위치에 있는 노드; 9. rear[i]=i번째 큐의 rear 위치에 있는 노드; 10. front[i]=null; 11. 12. add_queue(int i, char data) { 13. struct list *new; 14. if((new=(struct list *)malloc(sizeof(struct list)))==null) { 15. printf("Memory overflow\n"); 16. exit(0); 17. }

4.1.3 연결 리스트로 구현한 스택과 큐(5/6) 15. printf("Memory overflow\n"); 16. exit(0); 17. } 18. new->data=data; 19. new->next=null; 20. if(rear[i]==null) rear[i]=new; 21. else rear[i]->next=new; 22. rear[i]=new; 23. } 24. 25. char delete_queue(int i, char data) { 26. struct list *pos; 27. if(front[i]==null) { 28. printf("Queue empty\n"); 29. exit(0); 30. } 31. pos=front[i]; 32. front[i]=pos->next; 33. data=pos->data; 34. free(pos); 35. return(data); 36. }

4.1.3 연결 리스트로 구현한 스택과 큐(6/6) ※ 연결리스트를 이용한 방법의 몇 가지 장점 (1) 리스트를 처리하는데 걸리는 시간이 순차적 표현방법을 처리하는 시간 보다 빠르다. (2) 같은 배열 내에 여러 개의 리스트를 표현할 수 있다. (3) 삽입과 삭제의 경우 전체 자료의 이동이 필요 없다.

4.1.4 단순 연결 리스트의 응용(1/3) ※ 리스트로 처리할 수 있는 대표적인 적용 예는 다항식을 표현하여 덧셈에 적용하는 문제이다. ※ 일반적인 다항식은 각 항이 계수부와 지수부 그리고 다음 항을 가리키는 포인터를 위한 링크영역으로 구성된 아래와 같이 노드를 개념적으로 표현함 다항식에서의 노드 구성

변수가 한 개(X)인 다항식의 연결 리스트 표현 4.1.4 단순 연결 리스트의 응용(2/3) ￭ 변수가 한 개(X)인 다항식의 연결리스트표현과 다변수 다항식의 연결리스트 표현 : a=5x2+3x+1 ※ 변수가 한 개(X)인 다항식의 연결 리스트 표현 변수가 한 개(X)인 다항식의 연결 리스트 표현

4.1.4 단순 연결 리스트의 응용(3/3) ※ 다변수 다항식의 연결리스트 표현 다변수 다항식의 노드구성 : f(x,y) = 3x4y3 + 2x3y2 + x2y + 1 두 개의 변수 f(x, y)를 가진 다항식의 표현

4.2 원형 연결 리스트

4.2.1 원형 연결리스트의 정의(1/2) ￭ 원형 연결리스트(Circular Linked List)의 정의 ※ 마지막 노드의 포인터를 NULL이 아닌 리스트의 첫 번째 노드의 주소를 가리키도록 리스트를 구성할 수 있는데, 이러한 구조의 리스트를 원형 연결 리스트 또는 환형 연결 리스트라고 함 ※ 원형 리스트에서도 단순 연결 리스트와 마찬가지로 시작 위치를 알려주는 헤더 포인터가 있고 다른 모든 노드와 원형모양을 이루고 있음

4.2.1 원형 연결 리스트의 정의(2/2) ￭ 원형 리스트 연결의 장 단점 ※ 장점 : 어떤 임의의 노드로부터도 다른 노드로의 접근이 가능하다는 것이다. ※ 단점 : 리스트의 한 노드를 찾을 때 무한 루프에 빠질 염려가 있기 때문에 리스트의 모든 노드 중에서 검색을 끝낼 수 있는 노드가 존재해야 한다. 원형 연결 리스트

4.2.2 원형 연결 리스트의 기본 연산(1/3) ※ 원형 연결 리스트의 삽입 삭제 알고리즘 모듈 1. void INSERT(P) 2. struct node *P; 3. { 4. struct node *new; 5. new = getnode(); 6. new → data ='C'; 7. if (P == NULL) { 8. P = new; 9. new → LINK = new; 10. } 11. else { 12 new → LINK = P → LINK; 13. new → LINK = new; 14. } 15. }

4.2.2 원형 연결 리스트의 기본 연산(2/3) ※ 원형 연결 리스트의 삽입 삭제 알고리즘 원형 연결 리스트의 노드 삽입

4.2.2 원형 연결 리스트의 기본 연산(3/3) ￭ 원형 연결 리스트의 삽입 삭제 알고리즘의 문제점과 해결 ※ 문제점 : 새로운 노드를 삽입하려 한다면 매번 마지막 노드를 찾아야하는 점 ※ 해결책 : 원형 연결 리스트의 시작 노드인 head가 항상 마지막 노드를 가리키도록 하면 자료의 삽입 시 마지막 노드를 찾을 필요 없이 바로 삽입 동작을 수행함 tail과 head가 같은 원형 연결 리스트

4.3 다중 연결 리스트

4.3.1 다중 연결리스트(1/5) ￭ 다중 연결리스트(multi Linked List)의 개념 ※ 임의의 노드에 대해 다음 노드 뿐만 아니라 그 이전 노드까지 알 수 있도록하여 양방향 탐색이 가능하게 표현하는 것 ￭ 이중 연결리스트(doubly Linked List)의 구성과 장점 ※ 구성 : 자료를 저장하는 data부분과 이전 노드를 가리키는 포인터인 llink, 다음 노드를 가리키는 포인터인 rlink로 구성됨 ※ 장점 : 효율적인 리스트의 운영을 가능하게 해줌 (즉, 한쪽 방향의 연결 필드가 끊어지면 반대 방향으로 운행하여 관련된 자료를 복구하거나 특정 노드에서 이전 노드 주소를 손쉽게 구할 수 있는 장점)

4.3.1 다중 연결리스트(2/5) ￭ 이중 연결리스트의 노드 구성 이중 연결 리스트의 노드 구성 이중 연결 리스트의 구성 1. struct double_node { 2. struct double_node *llink; 3. int data; 4. struct double_node *rlink; 5. } *dpointer; 이중 연결 리스트의 노드 구성 이중 연결 리스트의 구성

4.3.1 다중 연결리스트(3/5) ￭ 이중 연결리스트의 특징 노드 이전 삽입 특정 노드 이전에 삽입 1. insert_before(dpointer, new) 2. struct double_node { 3. struct double_node *llink; 4. char data; 5. struct double_node *rlink; 6. } *dpointer, *new; 7. { 8. new = malloc(sizeof(*new)); 9. //실제 자료를 입력 받도록 처리해야 함 10. new->data = "R"; 11. //link를 새롭게 연결 12. new->llink = dpointer->llink; // 1'st 13. new->rlink = dpointer; // 2'nd 14. dpointer->llink->rlink = new; // 3'rd 15. dpointer->llink = new; //4'th 16. } 특정 노드 이전에 삽입

4.3.1 다중 연결리스트(4/5) ￭ 이중 연결리스트의 특징 노드 다음 삽입 특정 노드 다음에 삽입 1. insert_after(dpointer, new) 2. struct double_node { 3. struct double_node *llink; 4. char data; 5. struct double_node *rlink; 6. } *dpointer, *new; 7. { 8. new = malloc(sizeof(*new)); 9. //실제 자료를 입력 받도록 처리해야 함 10. new->data = "A"; 11. //link를 새롭게 연결 12. new->llink = dpointer; // 1'st 13. new->rlink = dpointer->rlink; // 2'nd 14. dpointer->rlink->llink = new; // 3'rd 15. dpointer->rlink = new; // 4'th 16. } 특정 노드 다음에 삽입

4.3.1 다중 연결리스트(5/5) ￭ 이중 연결리스트의 특징 노드 삭제 특정 노드 삭제 과정 1. delete(dpointer) 2. struct double_node { 3. struct double_node *llink; 4. char data; 5. struct double_node *rlink; 6. } *dpointer; 7. { 8. dpointer-> llink->rlink = dpointer->rlink; 9. dpointer->rlink->llink = dpointer->llink; 10. free(dpointer); 11. } 특정 노드 삭제 과정

4.3.2 이중 원형연결리스트(1/2) ￭ 이중 원형연결리스트(doubly circular Linked List) 의 개념 ※ 이중 연결 리스트와 원형 연결 리스트의 개념을 합한 것 이중 원형 연결 리스트

4.3.2 이중 원형연결리스트(2/2) ※ 배열과 연결 리스트의 구조 배열 연결 리스트 1. i 번째 자료 접근 조작 ○(1) ○(n) 선형 리스트 내의 자료 항목의 내용을 조사하거나 새로운 내용으로 수정하기 위하여 자주 발생한다. 2. 삽입 조작 특정 자료 다음에 삽입 특정 자료 이전에 삽입 단순 연결 리스트 : ○(n) 이중 연결 리스트 : ○(1) 단순 연결 리스트에서는 특정 노드 이전에 삽입을 하기 위해서는 이전 노드의 주소를 알아야 하는데 리스트의 처음부터 추적해야 이전 노드 주소를 알 수 있으므로 ○(n)이 된다. 3. 특정 자료 삭제 조작 단순 연결 리스트에서 특정 노드 삭제를 위해서는 이전 노드의 주소를 알아야 하는데 리스트의 처음부터 추적해야 이전 노드의 주소를 알 수 있으므로 ○(n)이 된다. 4. 기억 장소 관리 컴파일 할 때 배열의 최대 크기를 선언하여야 하므로 정적인 기억장소 관리를 한다. 프로그램 실행 시간에 필요한 노드를 생성하는 동적인 기억 장소 관리를 한다. 만일 선형 리스트에 관련된 자료가 잦은 삽입, 삭제가 이루어진다면 리스트의 길이에 유동적일 수 있는 연결 리스트 표현을 사용하여야 한다.

4.4 연결 리스트의 응용

4.4.1 희소행렬(1/3) ￭ 희소행렬의 연결리스트 표현 ※ 희소행렬을 연결 리스트로 표현하는 경우 순차적 방법에서의 단점을 극복할 수 있으며, 특히 희소행렬의 크기가 고정되지 않고 형태가 변하는 경우에 효율적으로 이용함 ※ 희소 행렬을 연결 리스트로 표현하는 경우 각 열과 행은 각각 헤드 노드를 가지는 원형 연결 리스트로 표현

4.4.1 희소행렬(2/3) ￭ 한 개 항목 노드의 구성과 헤드 노드의 구조 ※ 희소행렬의 노드는 헤드노드와 항목노드로 구성 (HEAD, DOWN, ROW, COLUMN, RIGHT, VALUE ) ※ 헤드노드의 구성 (DOWN, HEAD, RIGHT, NEXT) 한 개 항목 노드의 구성(a)과 헤드 노드의 구조(b)

4.4.1 희소행렬(3/3) ※ 희소행렬을 연결리스트로 표현

4.4.2 동적 기억 장소 관리 ￭ 동적 기억 장소 관리의 개념 ※ 동적인 기억 장소 관리(dynamic storage management)는 기억 장소를 고정된 크기로 분할하여 사용하는 것이 아닌 수행되는 작업에 필요한 크기만큼 메모리를 할당하는 방법 ※ 사용 가능한 블록들에 관한 정보를 연결형 리스트로 나타낸 예 사용 가능한 메모리 블록의 연결 리스트

4.4.3 쓰레기 수집 ￭ 쓰레기 수집(garbage collection)의 개념 ￭ 쓰레기 수집의 단계 ※ 대기중인 작업이 저장 장치의 압축으로 생긴 하나의 공백보다 작으면 그 작업을 실행 ￭ 쓰레기 수집의 단계 ※ 현재 사용 중인 노드를 표시 ※ 시가 없는 모든 노드들을 사용 가능한 공간에 반환