연결 리스트 삭제와 용도 (Linked List)

연결 리스트 삭제와 용도 (Linked List)

 

연결 리스트에서의 삭제

void remove_stack(node_t** head, int num1) {
	node_t** p = head;

	while (*p != NULL) {
		if ((*p)->num == num1) {
			node_t* a = *p;
			*p = (*p)->next;
			free(a);
			break;
		}
		p = &(*p)->next;
	}
}

매개변수 node_t** head = node_t* head를 참조하기 위한 이중 포인터

매개변수 int num1 = num1에 해당하는 값이 나오면 지운다.

 

* 삭제할 node의 주소를 알고 있다면 시간복잡도 = O(1)이지만

  현재 remove_stack은 검색 후 삭제이므로 시간복잡도 = O(n)이다.

 

* 문제점 = 가장 먼저 찾은 num1과 같은 값을 지운다.

  즉, num1의 값이 연결 리스트에 중복으로 있다면 젤 처음 값만 지워진다.

 

 

remove_stack을 자세히 보자 (헛소리 같으면 안 들어도 됨. 가독성 최악)

1. node_t** p는 head를 가리키는 포인터가 된다.

 

2. head는 NULL이 아니므로 while문 안에 들어간다.

 

3. if문에서 p가 가리키는 head가 가리키는 node의 num이 num1과 같냐고 물어본다.

 

4. if 조건식이 false였다면 p = &(*p)->next;가 실행된다.

   이중포인터 p = p가 가리키는 head가 가리키는 node의 next변수의 주소

 

5. 1번에서 p는 head를 가리키고, head는 node 전체를 가리켰다.

   4번이 끝난 후 p는 node 안에 있는 next를 가리키고, next는 다음 node 전체를 가리킨다.

 

6. 만약 num1과 같은 num을 찾았다면 p가 가리키는 next안에 값을 a에 저장한다.

   (a는 다음 node의 주소를 가지게 됨)

 

7. p가 가리키는 next = p가 가리키는 next가 가리키는 node의 주소를 넣는다.

 

8. free(a)를 통해 node가 해제된다.

 

끝

 

 

전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int num;
	struct node* next;
}node_t;

void addStack_firstPosition(node_t** p, int num1) {
	node_t* new_node = malloc(sizeof(node_t));

	new_node->num = num1;
	new_node->next = *p;

	*p = new_node;
}

void free_all_stack(node_t* head) {
	node_t* p = head;
	node_t* next;

	while (p != NULL) {
		next = p->next;
		free(p);
		p = next;
	}
}

void print_all_stack(node_t* head) {
	node_t* p = head;

	while (p != NULL) {
		printf("\n%d", p->num);
		p = p->next;
	}
}

void remove_stack(node_t** head, int num1) {
	node_t** p = head;

	while (*p != NULL) {
		if ((*p)->num == num1) {
			node_t* a = *p;
			*p = (*p)->next;
			free(a);
			break;
		}
		p = &(*p)->next;
	}
}

int main(){
	node_t* head = NULL;

	addStack_firstPosition(&head, 2);
	addStack_firstPosition(&head, 3);
	addStack_firstPosition(&head, 5);
	addStack_firstPosition(&head, 7);

	printf("넣어진 스택 순서 head부터");
	print_all_stack(head);

	printf("\n3과 7을 삭제하겠다.");

	remove_stack(&head, 3);
	remove_stack(&head, 7);
	print_all_stack(head);

	free_all_stack(head);
	head = NULL;
}

 

 

연결 리스트를 사용하는 이유, 용도

* 현재 구현한 node는 다음 node만을 알 수 있는 Singly Linked List이다.

  양방향을 알 수 있는 node는 포인터가 2개 필요하고 Doubly Linked List라고 한다.

  Doubly Linked List는 딱 봐도 싱글보다 무겁다.

 

* 배열의 상위호환을 만든 흔적?

  = 메모리 제한 X, 최대 크기 X, 삽입과 삭제 O(1) 등등

 

* 근데... 많이 사용하지는 않나 봐?

  

* 동적 할당 배열이 많은 부분을 커버할 수도 있고

  CPU는 접근한 메모리의 인접 메모리를 접근하는데 속도가 빠르다.

  (캐시 메모리에 들어갈만한 크기에서)

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.