[C언어/멘토링] 노드와 단일 연결 리스트

 

노드와 연결 리스트의 개념을 알아보고, 단일 연결 리스트 실습을 진행해보았다.

1. 노드

: 연결 자료 구조에서 하나의 데이터 조각을 담은 블록

datat

link

- 데이터 필드 : 데이터 값을 저장, 저장할 값의 형태에 따라 하나 이상의 필드로 구성

- 링크 필드 : 다음 노드의 주소를 저장 (포인터 변수 사용)

struct Node {
    int data;           // 데이터 필드
    struct Node* next;  // 링크 필드 (next: 다음 노드의 주소를 가리키는 포인터)
};

 

2. 연결 리스트

: 데이터를 저장하는 노드들이 포인터로 연결된 자료 구조

 

연결 리스트의 종류

- 단일 연결 리스트: 각 노드가 다음 노드만 가리키는 구조, 앞에서부터만 탐색 가능

- 이중 연결 리스트: 각 노드가 앞/뒤 노드 모두를 가리키는 구조, 양방향 탐색 가능

- 원형 연결 리스트: 마지막 노드가 다시 처음 노드로 연결된 구조, 단일 원형 리스트와 이중 원형 리스트가 있음 

왜 배열이 아닌 연결 리스트를 사용할까?

 

데이터 삽입/삭제가 자주 일어나는 경우	배열은 중간에 데이터를 넣거나 뺄 때 뒤에 있는 데이터들을 옮겨야 해서 비용이 크지만, 연결 리스트는 포인터만 바꾸면 돼서 효율적임
메모리를 효율적으로 쓰고 싶을 때	배열은 크기를 미리 정해야 해서 공간 낭비가 발생할 수 있지만, 연결 리스트는 필요한 만큼 동적으로 메모리를 할당해 메모리를 절약할 수 있음
데이터 크기나 수가 계속 변할 때	데이터가 계속 늘어나거나 줄어드는 상황에서 연결 리스트는 유연하게 크기를 조절할 수 있어 유리함
연속된 메모리 공간 할당이 어려울 때	배열은 연속적인 메모리 공간을 필요로 하지만, 연결 리스트는 메모리가 흩어져 있어도 각 노드를 포인터로 연결할 수 있어 메모리 단편화 문제를 줄일 수 있음

 

단일 연결 리스트

: 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조

[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

 

 

단일 연결 리스트를 구현해보자

 

1. 맨 앞에 삽입 : insert_first()

 

최종 코드

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

typedef int node; 

// 노드 구조 정의 
typedef struct ListNode {
	node data;		// 데이터 필드
	struct ListNode* next;	// 링크 필드(next)
}; ListNode;

// 앞부분에 노드 삽입
ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode)); 
	p->data = value; 
	p->next = head;
	head = p;
	return head;
}

// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return head;
}

// 리스트 출력
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->next)
		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);
	}
}

 

먼저, 1) 노드 구조를 정의해야 한다.

typedef int node; // node를 int와 동일하게 취급

//노드 구조 정의
typedef struct ListNode {
	node data;		// 데이터 필드
	struct ListNode* next;	// 링크 필드(next: 다음 노드의 주소를 가리키는 포인터)
}; ListNode;

 

typedef int node; 

typedef : 타입에 새로운 이름을 붙이는 키워드

왜 굳이 node를 int로 정의하는지?

후에 node 타입을 다른 자료형으로 변경하고 싶을 때, typedef 부분만 수정하면 돼 효율적이다.

 

typedef struct ListNode

struct ListNode 라는 구조체를 정의

typedef { ... }; ListNode; 를 사용해 struct를 붙이지 않고 ListNode를 쓸 수 있다.

 

 

노드를 삽입하는 함수를 작성한다. 2) 리스트에 맨 앞에 노드를 삽입하는 코드를 작성한다. 

ListNode* insert_first(ListNode* head, int value) // 앞부분에 노드 삽입
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value; // 새 노드에 값(value) 저장
	p->next = head; // 새 노드 next(링크 필드)에 기존 head 연결
	head = p; 	// 리스트의 첫 번째 노드 = 새 노드
	return head; 	// 새 노드 반환
}

 

ListNode* insert_first(ListNode* head, int value) 

insert_first() : 리스트의 시작 부분에 항목을 삽입하는 함수

- ListNode* head : head는 현재 연결 리스트의 첫 노드를 가리키는 포인터 (리스트의 시작점)

- int value : 노드에 담을 데이터 값

 

p->data = value; 

- p : 새로 만든 노드를 가리키는 포인터

- p->data : p가 가리키는 노드의 data 필드 (-> : 포인터가 가리키는 구조체 멤버에 접근하는 연산자)

 

p->next = head; 

- p->next : p가 가리키는 노드의 link 필드

[새 노드] -> [기존 head]

 

 

3) 기존 노드 뒤에 새 노드를 삽입하는 코드를 작성한다.

ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value; // 새 노드에 값 저장
	p->next = pre->next; //새 노드의 next(link 필드)를 pre 다음 노드로 연결
	pre->next = p; // pre의 next(linnk 필드)를 새 노드로 연결
	return head; // 새 head 반환
}

 

ListNode* insert(ListNode* head, ListNode* pre, node value);

insert() : 리스트의 중간 부분에 항목을 삽입하는 함수

- ListNode* head : head는 현재 연결 리스트의 첫 노드를 가리키는 포인터 (리스트의 시작점)

- ListNode* pre : pre는 새 노드의 바로 이전 노드를 가리키는 포인터

- int value : 노드에 담을 데이터 값

[새 노드] -> [기존 노드] -> [기존 head]

 

 

기본적인 노드 구조는 완성했다.

이제 4) 리스트를 출력 함수를 작성하고, 출력해보자.

void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->next)
		printf("%d->", p->data); // 현재 노드 p의 데이터를 출력
	printf("NULL \n"); 		// 모든 노드가 출력된 후 NULL 출력
}

int main(void)
{
	ListNode* head = NULL; // 연결 리스트의 시작점, 처음엔 비어 있으므로 NULL 초기화

	for (int i = 0; i <= 5; i++)
	{
		head = insert_first(head, i); // 이때부터 리스트에 값 저장
		print_list(head);
	}
}

 

for (ListNode* p = head; p != NULL; p = p->next)

 

- ListNode* p = head; : 포인터 변수 p를 선언, 리스트의 첫 주소(head)로 초기화

- p! = NULL: : 리스트 끝을 나타내는 NULL이 될 때까지 반복, 노드가 존재하는 동안 계속 반복

- p = p->next : p를 현재 노드의 next 포인터가 가리키는 노드로 이동

 

head = insert_first(head, i);

insert_first는 새로운 함수를 생성 -> 새로 생성된 노드는 리스트의 새 head가 됨 -> 변경된 head를 다시 head에 저장

 

print_list(head); 

printf_list() : 리스트를 방문하여 모든 항목을 출력하는 함수

0 ~ 5값(i값)의 노드들이 전부 출력된다. 

 

 

2. 맨 앞 노드 삭제 : delete_first()

 

1) 리스트의 첫 노드를 제거하는 코드를 작성한다. 

ListNode* delete_first(ListNode* head)
{
	if (head == NULL) return NULL; // 리스트가 NULL값일 경우 그대로 반환
    
	ListNode* removed = head; // 삭제할 노드를 임시로 저장
	head = removed->next; // head를 다음 노드로 이동
	free(removed);	// 첫 노드 메모리 해제
	return head;	// 새 head 반환
}

 

ListNode* delete_first(ListNode* head)

delete_first() : 리스트의 첫번째 항목을 삭제하는 함수

 

 

free(removed);

free() : 동적으로 할당한 메모리를 해제하는 함수 (메모리 누수 방지)

 

2) 출력함수를 작성한다.

int main(void)
{
	ListNode* head = NULL;

	for (int i = 0; i < 3; i++)
	{
		head = delete_first(head);
		print_list(head);
	}
}

 

head = delete_first(head);

리스트 맨 앞 노드를 삭제 -> 새로 바뀐 맨 앞 노드 주소를 head에 저장

 

print_list(head); 

printf_list() : 리스트를 방문하여 모든 항목을 출력하는 함수

맨 앞에 위치한 총 3개의 노드들이 삭제된다.

 

코드(1.)에 이 코드를 추가한 최종코드

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

typedef int node; 

// 노드 구조 정의 
typedef struct ListNode {
	node data;				 // 데이터 필드
	struct ListNode* next;	// 링크 필드(next)
}; ListNode;

// 앞부분에 노드 삽입
ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode)); 
	p->data = value; 
	p->next = head;
	head = p;
	return head;
}

// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return head;
}

// 앞부분의 노드 제거
ListNode* delete_first(ListNode* head)
{
	ListNode* removed;
	if (head == NULL) return NULL;
    
	removed = head;
	head = removed->next;
	free(removed);
	return head;
}

// 리스트 출력
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->next)
		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 < 3; i++)
	{
		head = delete_first(head);
		print_list(head);
	}
}

 

 

3. 특정 노드(pre) 뒤 삽입 : insert_after()

 

1) pre노드의 다음 노드를 삭제하는 코드를 작성한다. 

// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value; // 새 노드에 데이터(value) 저장
	p->next = pre->next; // 새 노드의 next(link 필드) = pre 노드 next(link 필드)
	pre->next = p; // pre의 next(link 필드)를 새 노드로 변경
	return head;
}

 

ListNode* insert(ListNode* head, ListNode* pre, node value)

 

insert() : 리스트의 중간 부분에 항목을 삽입하는 함수

 

 

2) 출력함수를 작성한다.

int main(void)
{
	ListNode* head = NULL;

	for (int i = 0; i <= 5; i++)
	{
		head = insert_first(head, i);
		print_list(head);
	}

	ListNode* pre = head;
	if (pre != NULL && pre->next != NULL) // pre가 NULL이 아니고, pre의 다음 노드도 존재하면
		pre = pre->next; // pre를 한 칸 이동, 이제 pre는 두 번째 코드, 그 뒤에 삽입

	head = insert(head, pre, 0); // 두 번째 노드 뒤에 값 0인 새 노드 삽입
	print_list(head);
}

 

코드(1.)에 이 코드를 추가한 최종코드

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

typedef int node; 

// 노드 구조 정의 
typedef struct ListNode {
	node data;				 // 데이터 필드
	struct ListNode* next;	// 링크 필드(next)
}; ListNode;

// 앞부분에 노드 삽입
ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode)); 
	p->data = value; 
	p->next = head;
	head = p;
	return head;
}

// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return head;
}

//pre가 가리키는 노드 뒤에 삽입
ListNode* insert_after(ListNode* head, ListNode* pre, node value)
{
	if (pre == NULL) return head;
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return head;
}

// 리스트 출력
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->next)
		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);
	}

	ListNode* pre = head;
	if (pre != NULL && pre->next != NULL)
		pre = pre->next;

	head = insert(head, pre, 0);
	print_list(head);
}

 

 

4. 특정 노드(pre) 뒤 삭제 : delete_after()

 

1) pre노드의 다음 노드를 삭제하는 코드를 작성한다. 

// pre노드의 다음 노드를 삭제
ListNode* delete_after(ListNode* head, ListNode* pre)
{
	ListNode* removed; // 삭제할 노드 포인터 선언
	removed = pre->next; // 삭제할 노드 = rpe 다음 노드
	pre->next = removed->next; // pre가 삭제할 노드의 다음 노드를 가리키도록 연결
	free(removed); // 분리된 노드의 메모리 해제
	return head;
}

 

ListNode* delete_after(ListNode* head, ListNode* pre)

delete_after() : 리스트의 중간 부분에 항목을 삭제하는 함수

 

free(removed);

free() : 동적으로 할당한 메모리를 해제하는 함수 (메모리 누수 방지)

 

2) 출력함수를 작성한다.

int main(void)
{
	ListNode* head = NULL;

	for (int i = 0; i <= 5; i++)
	{
		head = insert_first(head, i);
		print_list(head);
	}

	ListNode* pre = head;
	if (pre != NULL && pre->next != NULL) // pre가 NULL이 아니고, pre의 다음 노드도 존재하면
		pre = pre->next; // pre를 한 칸 이동, 이제 pre는 두 번째 코드, 삭제 코드는 세 번째 코드(값 3)

	head = delete_after(head, pre); // 세 번째 노드 삭제
	print_list(head);
}

 

코드(1.)에 이 코드를 추가한 최종코드

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

typedef int node; 

// 노드 구조 정의 
typedef struct ListNode {
	node data;		 // 데이터 필드
	struct ListNode* next;	// 링크 필드(next)
}; ListNode;

// 앞부분에 노드 삽입
ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode)); 
	p->data = value; 
	p->next = head;
	head = p;
	return head;
}

// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, node value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return head;
}

// pre가 가리키는 노드 다음 노드를 삭제
ListNode* delete_after(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->next;
	pre->next = removed->next;
	free(removed);
	return head;
}

// 리스트 출력
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->next)
		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);
	}

	ListNode* pre = head;
	if (pre != NULL && pre->next != NULL)
		pre = pre->next;

	head = delete_after(head, pre);
	print_list(head);
}

 

 

 

참조 링크: 
https://codejin.tistory.com/136

[C] 단일 연결 리스트(Single linked list) 구현

https://yjg-lab.tistory.com/118

[자료구조] 리스트 구현 - 연결리스트(단순 연결리스트)