[자료구조] 연결리스트 PART.2

1. 연결리스트로 나타낸 구조에서 삭제하기(중간노드)

 

연결리스트 PART.1에서 삽입으로 실습했던 구조를 가지고 삭제 실습한다.

 

Data	Link	Data	Link	Data	Link	Data	Link	Data	Link
	->	10	->	20	->	30	->	40	NULL
head		node1		node2		node3		node4

 

이 구조에서 node3을 삭제한다.

 

1) 순서

1. 삭제할 노드의 앞 노드(선행자)를 찾는다.
2. 앞 노드의 링크 필드에 사제할 노드의 링크 필드 값을 저장한다.

2. C언어 실습

1) 노드 생성

위 구조의 노드를 생성한다.

 

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

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

int main()
{
	NODE *head = (NODE *)calloc(40, sizeof(NODE));  // 머리 노드 생성
	// 머리 노드는 데이터를 저장하지 않음

	NODE *node1 = (NODE *)calloc(40, sizeof(NODE));	// 첫 번째 노드 생성
	head -> link = node1;	// 머리 노드 다음은 첫 번째 노드
	node1 -> data = 10;	// 첫 번째 노드에 10 저장

	NODE *node2 = (NODE *)calloc(40, sizeof(NODE));	// 두 번째 노드 생성
	node1 -> link = node2;	// 첫 번째 노드 다음은 두 번째 노드
	node2 -> data = 20;	// 두 번째 노드에 20 저장

	NODE *node3 = (NODE *)calloc(40, sizeof(NODE));	// 두 번째 노드 생성
	node2 -> link = node3;	// 두 번째 노드 다음은 세 번째 노드
	node3 -> data = 30;	// 세 번째 노드에 30 저장

	NODE *node4 = (NODE *)calloc(40, sizeof(NODE));	// 네 번째 노드 생성
	node3 -> link = node4;	// 세 번째 노드 다음은 네 번째 노드
	node4 -> data = 40;	// 네 번째 노드에 40 저장
	node4 -> link = NULL;	// 네 번째 노드 다음 노드가 없음(NULL)

	NODE *curr = head -> link; // 연결 리스트 순회용 포인터에서 첫 번째 노드의 주소 저장
	while (curr != NULL){		// 포인터가 NULL이 아닐 때 계속 반복
		printf("%d\n", curr -> data);	// 현재 노드의 데이터출력
		curr = curr -> link;		// 포인터에 다음 노드의 주소 저장
	}

	free(node1);	// 노드 메모리 해제
	free(node2);	// 노드 메모리 해제
	free(node3);	// 노드 메모리 해제
	free(node4);	// 노드 메모리 해제
	free(head);	// 머리 노드 메모리 해제

	return 0;
}

 

노드 생성

2) 노드 삭제

위 1) 노드 생성 코드에 삭제 코드 추가를 통해 위 1번에서 말한 내용을 실습한다.

 

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

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

int main()
{
	NODE *head = (NODE *)calloc(40, sizeof(NODE));  // 머리 노드 생성
	// 머리 노드는 데이터를 저장하지 않음

	NODE *node1 = (NODE *)calloc(40, sizeof(NODE));	// 첫 번째 노드 생성
	head -> link = node1;	// 머리 노드 다음은 첫 번째 노드
	node1 -> data = 10;	// 첫 번째 노드에 10 저장

	NODE *node2 = (NODE *)calloc(40, sizeof(NODE));	// 두 번째 노드 생성
	node1 -> link = node2;	// 첫 번째 노드 다음은 두 번째 노드
	node2 -> data = 20;	// 두 번째 노드에 20 저장

	NODE *node3 = (NODE *)calloc(40, sizeof(NODE));	// 두 번째 노드 생성
	node2 -> link = node3;	// 두 번째 노드 다음은 세 번째 노드
	node3 -> data = 30;	// 세 번째 노드에 30 저장

	NODE *node4 = (NODE *)calloc(40, sizeof(NODE));	// 네 번째 노드 생성
	node3 -> link = node4;	// 세 번째 노드 다음은 네 번째 노드
	node4 -> data = 40;	// 네 번째 노드에 40 저장
	node4 -> link = NULL;	// 네 번째 노드 다음 노드가 없음(NULL)

	puts("- 삭제 전 -");
	NODE *curr = head -> link; // 연결 리스트 순회용 포인터에서 첫 번째 노드의 주소 저장

	while (curr != NULL){		// 포인터가 NULL이 아닐 때 계속 반복
		printf("%d\n", curr -> data);	// 현재 노드의 데이터출력
		curr = curr -> link;		// 포인터에 다음 노드의 주소 저장
	}

	puts("- 삭제 후 -");
	node2 -> link = node4;
    
	curr = head -> link;
    
	while (curr != NULL){
		printf("%d\n", curr -> data);
		curr = curr -> link;
	}
    
	free(node1);	// 노드 메모리 해제
	free(node2);	// 노드 메모리 해제
	free(node3);	// 노드 메모리 해제
	free(node4);	// 노드 메모리 해제
	free(head);	// 머리 노드 메모리 해제

	return 0;
}

 

노드 삭제