1. List 구현 in pointer
포인터로 list를 구현할 시 다음과 같은 장단점이 있다.
장점: 크기의 제한이 없고, 삽입삭제가 자유로움
단점: 구현이 복잡하고, 임의의 항목을 추출할 때 배열보다 시간이 많이 걸림
Linked List는 node들의 집합이다. node는 다음 두 가지로 이루어진다.
data field: 저장하고 싶은 데이터
link field: 다른 노드를 가리키는 포인터
head node는 첫 번째 노드를 가리키는 변수이고, 마지막 노드의 Link field는 NULL값을 가진다.
Linked List는 세 가지 종류가 있다
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
여기서는 단순 연결 리스트만 다룬다
2. 단순 연결 리스트(singly linked list)
단순 연결 리스트는 단방향으로 연결된 리스트로, 마지막 노드의 link field값은 NULL이다.이 리스트를 구현하기 위해 우리는 다음 세가지를 생각해야 한다.
노드는 어떻게 정의할 것인가? -> 자기 참조 구조체를 이용
노드는 어떻게 생성할 것인가? -> malloc()을 호출하여 동적 메모리로 생성
노드는 어떻게 삭제할 것인가? -> free()를 호출하여 동적 메모리를 해제
지금부터 연결리스트를 구현해보겠다.
-
노드의 정의
노드는 자기 참조 구조체를 이용하여 정의한다.
자기 참조 구조체: 자기 자신을 참조하는 포인터를 포함하는 구조체
data field는 element타입의 데이터를 저장하고, linked filed는 node를 가리키는 포인터로 정의되며 다음 node의 주소가 저장된다.typedef int element; typedef struct ListNode{ // node type을 구조체로 정의함 element data; // data field struct ListNode *link; // link field }ListNode; -
공백 리스트 생성
단순 연결 리스트는 head pointer만 있으면 모든 노드를 찾을 수 있다.
따라서 노드를 가리키는 포인터 head를 정의하고, 리스트의 공백을 확인하려면 head pointer == NULL인지 검사하면 된다.
head pointer가 가리키는 ListNode 구조체가 존재하지 않으므로, data와 link 필드는 접근할 수 없다.
ListNode *head = NULL;- 노드의 생성
malloc()를 이용하여 노드의 크기만큼 동적 메모리를 할당받는다.
순서는 다음과 같다.
- malloc()가 ListNode 구조체 크기만큼의 메모리를 할당받으면, 할당된 메모리의 시작 주소가 return된다.
- return된 void 타입의 주소를 LinkNode타입으로 캐스팅한다.
- 캐스팅된 주소는 head포인터에 저장된다.
head = (ListNode *)malloc(sizeof(ListNode)); // 동적 메모리 할당
head->data = 10; // 노드의 data field 값
head->link = NULL; // 노드의 link field 값- 노드의 연결
노드끼리 연결하는 방법은 앞 노드의 link field의 값에 뒷 노드의 포인터를 넣는 것이다.
ListNode *p;
p = (LinkNode *)malloc(sizeof(LinkNode));
p->data = 20;
p->link = NULL;
head->link = p;3. 단순 연결 리스트의 연산 구현
다음은 단순 연결 리스트에서 작성할 함수들이다.
- insert_first(): 리스트의 시작 부분에 항목을 삽입하는 함수
- insert(): 리스트의 중간 부분에 항목을 삽입하는 함수
- delete_firts(): 리스트의 첫 번째 항목을 삭제하는 함수
- delete(): 리스트의 중간 항목을 삭제하는 함수
- print_list(): 리스트를 방문하여 모든 항목을 출력하는 함수- 단순 연결 리스트 정의
단순 연결 리스트는 원칙적으로 head pointer만 있으면 된다.
ListNode *head;- 삽입 연산 insert_first()
이 함수는 ListNode* 타입의 포인터를 반환한다. 함수 실행 후 리스트의 첫 번째 노드를 가리키는 포인터이다. 따라서 반환된 포인터는 리스트의 새로운 헤드가 됩니다. 매개변수 head는 head pointer, value는 새롭게 추가되는 data이다.
ListNode* insert_first(ListNode *head, element value){
ListNode *p = (ListNode *)malloc(sizeof(Listnode));
p->data = value;
p->link = head;
head = p;
return head;
}- 삽입 연산 insert()
선행노드를 가리키는 변수 pre를 선언하여 새로운 값을 list에 추가한다.
ListNode* insert(ListNode *head, ListNode *pre, element value){
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p->data = value; // p의 data field에 value값을 저장
p->link = pre->link; // 선행노드의 link field 값을 p의 link field에 저장
pre->link = p; // 선행노드의 link field가 새 노드 p를 가리키도록 함
return head;
}-
삭제 연산 delete_first()
head를 두 번째 노드의 링크로 연결시킨다.ListNode* delete_first(ListNode *head) { ListNode *removed; // 삭제될 노드를 가리킬 포인터 변수 removed를 선언 if(head == NULL) return NULL; removed = head; //removed에 head값을 넣어서 첫 번째 node를 가리키게 함 head = removed->link; // head 값에 removed가 가리키는 다음 노드 값을 넣음. 즉, 두 번째 노드를 head가 가리키도록 함 free(removed); return head; } -
삭제 연산 delete()
ListNode* delete(ListNode *head, ListNode *pre) { LsitNode *removed; //삭제될 노드를 가리킬 포인터 변수 선언 removed = pre->link; // removed가 pre->link과 같은 노드를 가리킴 pre->link = removed->link; // removed->link가 가리키는 곳을 pre->link도 같이 가리킴 free(removed); return head; } -
print_list() 함수
void print_list(ListNode *head) { for(ListNode *p = head; p != NULL; p = p->link) printf("%d->", p->data); printf("NULL \n"); } -
전체 테스트 프로그램
#include <stdio.h> #include <stdlib.h> // 앞의 함수들 넣기 int main(void) { ListNode *head = NULL; for(int i = 0; i < 5; i++){ head = insert_first(head, i); print_list(head); } for(int i = 0; i < 5; i++){ head = delete_first(head); print_list(head); } return 0; }
4. 연결 리스트의 응용: 다항식
각 다항식을 가리키는 두 개의 포인터를 이용하여 다항식의 합을 구현한다.
다항식 a와 b가 있을 때 두 다항식을 합친 다항식을 구하는 규칙은 다음과 같다.
a의 지수 == b의 지수: 두 계수를 합쳐 total에 저장
a의 지수 >= b의 지수: a의 계수를 total에 저장하고, a의 포인터를 다음 노드로 옮김
a의 지수 <= b의 지수: b의 계수를 total에 저장하고, b의 포인터를 다음 노드로 옮김
다음은 코드이다.
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode{
int coef;
int expon;
struct ListNode *link;
} ListNode;
//연결 리스트 헤더
typedef struct ListType{
in size;
ListNode *head;
ListNode *tail;
} ListType;
//오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
ListType* create()
{
ListType *plist = (ListType *)malloc(sizeof(ListType));
plist->size = 0;
plist->head = plist->tail = NULL;
return plist;
}
//plist: 연결 리스트의 헤더를 가리키는 포인터, coef: 계수, expon: 지수
void insert_last(ListType* plist, int coef, int expon)
{
ListNode* temp = (ListNode *)malloc(sizeof(ListNode));
if(temp==NULL) error("메모리 할당 에러");
temp->coef = coef;
temp->expon = expon;
temp->link = NULL;
if(plist->tail == NULL){
plist->head = plist->tail = temp;
}
else{
plist->tail->link = temp;
plist->tail = temp;
}
plist->size++;
}
//list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
ListNode* a = plist1->head;
ListNode* b = plist2->head;
int sum;
while(a && b){
if(a->expon == b->expon){
sum = a->coef + b->coef;
if(sum != 0) insert_last(plist3, sum, a->expon);
a = a->link; b = b->link;
}
else if(a->expon > b->expon){
insert_last(plist3, a->coef, a->expon);
a = a->link;
}
else{
insert_last(plist3, b->coef, b->expon);
b = b->link;
}
}
//a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 결과 다항식으로 복사
for(;a != NULL; a = a->link)
insert_last(plist3, a->coef, a->expon);
for(;b != NULL; b = b->link)
insert_last(plist3, b->coef, b->expon);
}
void poly_print(ListType* plist)
{
ListNode* p = plist->head;
printf("polynomial = ");
for(; p; p = p->link){
printf("%d^%d + ", p->coef, p->expon);
}
printf("\n");
}
int main(void)
{
ListType *list1, *list2, *list3;
//연결 리스트 헤더 생성
list1 = create();
list2 = create();
list3 = create();
//다항식 1을 생성
insert_last(list1, 3, 12);
insert_last(list1, 2, 8);
insert_last(list1, 1, 0);
//다항식 2을 생성
insert_last(list2, 8, 12);
insert_last(list2, -3, 10);
insert_last(list2, 10, 6);
poly_print(list1);
poly_print(list2);
//다항식 3 = 다항식 1 + 다항식 2
poly_add(list1, list2, list3);
poly_print(list3);
free(list1); free(list2); free(list3);
}