문과생이 이해한 단일 연결 리스트(삭제 연산)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

<전체 코드>

#include<stdio.h>
#include<stdbool.h>

typedef struct {
	int data;
	struct node* link;
}node;

node* insert_first(node* head, int x) {
	node* p = (node*)malloc(sizeof(node));
	p->data = x;
	p->link = head;      //head는 노드 생성을 안했으니까 head->link 연산이 안 됨
	head= p;
	return head;
}

node* insert(node* head, node* pre, int s) {
	node* p = (node*)malloc(sizeof(node));
	p->data = s;
	p->link = pre->link;
	pre->link = p;
	return head;
}

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

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

int main() {
	node* head = NULL;
	
	//데이터 삽입 및 출력
	for (int i = 0; i < 5; i++) {
		head = insert_first(head,i);  //반환된 head 포인터를 저장. 아니면 null값만 출력됨
		print_node(head);
	}

	//삭제 연산
	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_node(head);
	}

	return 0;
}

 

 

---

 

#삭제연산1(delete_first)

 일단 이런 연결리스트가 있다고 가정하겠다. 

 

1. head를 인자로 보내주고, 함수 내에서 removed 포인터 변수를 선언해준다. 

 그림에서는 delete_first에 있는 head만 연결리스트를 가리키고 있는데, 원래는 main문에 있는 head도 연결리스트를 가라키고 있다. 그냥 그림이 복잡해져서 그리지 않은 것일 뿐!

 

 

2. 33줄 if문. 처음 head를 선언했을 때 NULL로 초기화한 것을 기억하는가? head가 NULL이라는 건 연결리스트가 없다는것이다. 그러므로 NULL을 리턴한다. 

 

3. removed에 head(10')를 넣고, head에는 removed가 가리키는 노드의 link값(20')를 넣는다. 

 교재에서는 free함수를 써서 메모리를 해제 해줬는데, 어차피 함수가 끝나면 모두 메모리에서 사라지고 해당 노드는 운영체제가 잘 처리해준다고 한다. 이를 가비지 컬렉션이라고 한다. 

 

 

 

 

---