자체 참조 구조체를 이용한 동적 리스트
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct ListNode *link;
} ListNode;
ListNode *create_node(int data, ListNode *link)
{
ListNode *new_node;
new_node = (ListNode *)malloc(sizeof(ListNode));
if (new_node == NULL) printf("메모리 할당 에러\n");
new_node->data = data;
new_node->link = link;
return(new_node);
}
ListNode *search(ListNode *head, int fdata)
{
ListNode *p = head;
while (p != NULL)
{
if (p->data == fdata) return p;
p = p->link;
}
return p; //실패시 NULL 반환
}
ListNode *reverse(ListNode *head)
{
ListNode *p, *q, *r;
p = head;
q = NULL;
while (p != NULL)
{
r = q; // q의 주소를 받음
q = p; //p의 주소를 받음
p = p->link; // p포인터 다음 주소
q->link = r; // q+1 = q
}
return q;
}
ListNode *concat(ListNode *head1, ListNode *head2) // 두개의 listnode를 붙이는 함수
{
ListNode *p;
if (head1 == NULL) return head2; // head1이 NULL일때 head2를 반환
else if (head2 == NULL) return head1; // head2가 NULL일때 head1 반환
else {
p = head1;
while (p->link != NULL) //head1이 NULL될때까지의 link주소값을 찾고
p = p->link;
p->link = head2;// 그 주소 다음에 head2 주소 값을 합성
return head1; // 그리고나서 head1를 반환
}
}
void insert_node(ListNode **head, ListNode *p, ListNode *new_node)
{
if (*head == NULL) //헤더가 없는(NULL) 경우
{
new_node->link = NULL; // new_node 다음 주소를 NULL로 함
*head = new_node; // 헤더의 주소를 new_node로 변환
}
else if (p == NULL) // p포인터가 NULL일 경우
{
new_node->link = *head; // 헤더가 갖고있는 다음주소를 new_node에 저장
*head = new_node; // 헤더 주소를 new_node로저장
}
else //p 포인터 다음으로 저장
{
new_node->link = p->link; //p포인터가 갖고 있는 다음 주소를 new_node에 저장
p->link = new_node; // p포인터의 다음 주소로 new_node로 저장
}
}
void remove_node(ListNode **head, ListNode *p, ListNode *removed)
{
if (p == NULL)
*head = (*head)->link;//헤더가 삭제 될경우 헤더가 갖고 있는 다음 주소로 변환
else
p->link = removed->link; // p포인트의 다음주소를 removed가 갖고 있는 주소로 저장
free(removed);
}
void display(ListNode *head)
{
ListNode *p = head;
while (p != NULL)
{
printf("%d->", p->data);
p = p->link;
}
printf("\n");
}
void main(void)
{
ListNode *list1 = NULL, *list2 = NULL;
ListNode *p,*j;
insert_node(&list1, NULL, create_node(10, NULL));
insert_node(&list1, NULL, create_node(20, NULL));
insert_node(&list1, NULL, create_node(30, NULL));
display(list1);
remove_node(&list1, NULL, list1);
display(list1);
insert_node(&list2, NULL, create_node(60, NULL));
insert_node(&list2, NULL, create_node(70, NULL));
insert_node(&list2, NULL, create_node(80, NULL));
display(list2);
list1 = concat(list1, list2);
display(list1);
list1 = reverse(list1);
display(list1);
p = search(list1, 20);
printf("탐색 성공 : %d\n", p->data);
}
결과 :
