4장. 리스트(Lists)
교재 1 - Horowitz, Sahni, and Anderson-Freed, Fundamentals of Data Structures in C, Computer Science Press.
교재 2 - Horowitz, Sahni, and Anderson-Freed, Fundamentals of Data Structures in C (2nd Edition), Silicon Press.
목차
1. 포인터(Pointers)
2. 단순 연결 리스트(Singly Linked Lists) 3. 리스트를 이용한 스택과 큐
4. 다항식(Polynomials)
5. 추가적인 리스트 연산(Additional List Operations) 6. 동치 관계(Equivalence Relations)
7. 희소 행렬(Sparse Matrices)
8. 이중 연결 리스트(Doubly Linked Lists)
1. 포인터(Pointers)
순서화 리스트의 (배열을 이용한) 순차적 구현
임의의 위치에 대한 삽입과 삭제 연산이 곤란(다음 장 참조)
가변 길이의 순서화 리스트 지원 불가
순서화 리스트의 연결 리스트를 이용한 구현
리스트의 연속된 항목들은 메모리의 임의의 장소에 위치
리스트는 (연결된) 노드 (node) 들로 구성
각 노드는 데이터와 링크 (link) 로 구성
링크는 리스트의 다음 노드를 가리킴. (마지막 노드의 링 크 ?)
data1 data2 datan ∧
node
link
Insertion at Array
10 a[0]
20 a[1]
30 a[2]
a[3] 40
50 a[4]
a[5] 60
70 a[6]
a[7] 80
90 a[8]
a[9] -
+ 15
10 a[0]
15 a[1]
20 a[2]
a[3] 30
40 a[4]
a[5] 50
60 a[6]
a[7] 70
80 a[8]
a[9] 90
Complexity = O(n)
동적 메모리 할당
malloc과 free // <malloc.h> (<stdlib.h>)
int i, *pi;
float f, *pf;
pi = (int *) malloc(sizeof(int));
pf = (float *) malloc(sizeof(float));
*pi = 1024;
*pf = 3.14f;
printf(“\ n integer = %d, float = %f\ n”, *pi, *pf);
free(pi); free(pf);
연속 메모리 할당: calloc
FreeMsg = (msg_t *) calloc(max_msg, sizeof(msg_t));
for (i = 0; i < max_msg – 1; i++)
FreeMsg[i].next = FreeMSG + (i + 1);
FreeMSG[i].next = NULL;
2. 단일 연결 리스트(Singly Linked Lists)
연결 리스트의 표현
각 노드들은 메모리의 인접한 곳에 위치하지 않는다.
각 노드의 주소는 프로그램 실행시 매번 틀릴 수 있다.
리스트의 이름 = 첫 번째 노드의 주소
삽입과 삭제
기존 노드들의 위치를 변경할 필요가 없다.
링크 필드를 위한 추가적인 메모리 공간 필요
bat cat sat vat NULL
ptr
예: 연결 리스트에서 삽입과 삭제
bat cat sat vat NULL
ptr
mat
bat cat sat vat NULL
ptr
mat
리스트의 생성
typedef struct node *list_pointer;
struct node { char data[4];
struct node *link;
};
struct node *ptr = NULL;
ptr = (struct node *) malloc(sizeof(struct node));
Self-referential structure
NULL: defined in stdio.h(K&R C) or stddef.h(ANSI C)
노드의 각 필드에 값 할당
strcpy(ptr->data, “bat”); // strcpy((*ptr).data, “bat”);
ptr->link = NULL;
C 언어에서 리스트 구현
리스트에 새로운 노드를 삽입
(1) 두 개의 노드로 구성된 리스트
(2) A 다음에 temp라는 새로운 노드를 삽입: insert(&ptr, A) - Program 4.3
ptr
10 20 NULL
ptr
10 20 NULL
50 temp
A
Program 4.3: 리스트에 삽입
void insert(struct node **ptr, struct node *before)
{ /* data = 50인 새로운 노드를 ptr이 가리키는 리스트의 before 노드 다음에 삽입 */
struct node *temp;
temp = (struct node *) malloc(sizeof(struct node));
if (temp == NULL)
{ fprintf(stderr, "The memory is full\ n"); exit(1); } temp->data = 50;
if (*ptr != NULL)
{
temp->link = before->link; before->link = temp;
} else{ temp->link = NULL; *ptr = temp; } }
리스트에서 노드 삭제
delete(&ptr, before, A)
ptr이 가리키는 리스트에서 노드 A를 삭제
before는 A 노드의 이전 노드를 가리키고 있음
void delete(list_pointer *ptr, list_pointer before, list_pointer A) { // ptr: 포인터의 포인터, before와 A: 포인터
if (before != NULL)
before->link = A->link;
else *ptr = (*ptr)->link;
free(A);
}
before가 없을 경우, A를 삭제하는 방법?
연습문제 4, 6, 7, 8(페이지 154) 풀 것!
예:삭제
10 50 20 NULL 50 20 NULL
ptr A before = NULL ptr
(1)
delete(&ptr, NULL, ptr)
(a) before deletion (b) after deletion
10 50 20 NULL 10 20 NULL
ptr before A ptr
(2)
delete(&ptr, ptr, ptr->link)
(a) before deletion (b) after deletion