단순 연결 리스트의 연산 구현

- 앞에서는 노드를 하나씩 만들어 서로 연결

- 리스트가 커지면 위 방법보다는 추상 데이터 타입에 정의된 전용 함수들을 통하여 노드를 추가하는 것이 편리

• insert_first(): 리스트 시작 부분에 항목 삽입
• insert(): 리스트 중간 부분에 항목 삽입
• delete_first(): 리스트 첫 항목 삭제
• delete(): 리스트 중간 항목 삭제
• print_list(): 리스트를 방문하여 모든 항목을 출력

- 위 함수들을 작성할 수 있다.

---

단순 연결 리스트 정의

ListNode* head;

- 단순 연결 리스트는 원칙적으로 헤드 포인터만 있으면 됨

 

삽입 연산 insert_first()

- 리스트의 첫 부분에 새로운 노드 추가

ListNode* insert_first(ListNode* head, element value);

- head는 헤드 포인터

- value는 새로 추가되는 데이터

 

- head는 첫 번째 노드를 가리킴

- 새로운 노드를 하나 생성하고 새로운 노드의 link에 현재의 head 값을 저장

- head를 변경하여 새로 만든 노드를 가리키도록 함

- insert_first()는 변경된 헤드 포인트를 반환하므로, 반환된 값을 헤드 포인트에 저장

ListNode* insert_first(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;	//헤드 포인터 값 복사
	head = p;	//헤드 포인터 변경
	return head;	//변경된 헤드 포인터 반환
}

---

삽입 연산 insert()

- 연결 리스트 중간에 새로운 노드 추가

- 삽입되는 위치의 선행 노드를 알아야 삽입 가능

- 새로운 데이터를 삽입한 후 다른 노드들을 이동할 필요 없음

ListNode* insert(ListNode* head, ListNode* pre, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}

---

삭제 연산 delete_first()

- 첫 번째 노드를 삭제

ListNode* delete_first(ListNode* head)

ListNode* delete_first(ListNode* head) {
	ListNode* removed;
	if (head == NULL)
		return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}

---

삭제 연산 delete()

- 리스트의 중간에서 삭제

ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

---

print_list() 함수

- 연결 리스트 안의 모든 노드 데이터를 출력

- 노드를 방문하며 노드의 데이터를 출력

- 노드의 링크 값이 NULL이 아니라면 계속 링크를 따라 가면서 노드를 방문

- 링크 값이 NULL이면 반복 중단

ListNode* 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>

typedef int element;
typedef struct {
	element data;
	struct ListNode* link;
}ListNode;

//처음에 삽입
ListNode* insert_first(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;	//헤드 포인터 값 복사
	head = p;	//헤드 포인터 변경
	return head;	//변경된 헤드 포인터 반환
}
//중간에 삽입
ListNode* insert(ListNode* head, ListNode* pre, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}
//첫 번째 노드 삭제
ListNode* delete_first(ListNode* head) {
	ListNode* removed;
	if (head == NULL)
		return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}
ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}
ListNode* print_list(ListNode* head) {
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

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;
}

>>