[C programming] 연결 리스트 (Linked List)

C programming - 연결 리스트 (Linked List)

 

 

리눅스 환경에서 네트워크 프로그래밍을 공부하기 위해서 C언어를 다시 복습해야 할 필요성을 느꼈습니다. 따라서 이번 기회에 배열부터 전처리기까지 내용들을 정리하겠습니다.

 

---

연결 리스트란?

연결리스트는 노드라고 불리는 구조체들의 체인으로 이루어져있습니다. 각 노드는 다음 노드를 가리키는 포인터를 가지고 있습니다. 연결 리스트는 삽입 삭제가 편리하고 메모리를 효율적으로 관리할 수 있습니다.

 

출처 : https://www.geeksforgeeks.org/what-is-linked-list/

 

해당 포스트에서는 실제로 C언어를 통해 연결 리스트를 구현하면서 공부해보겠습니다.

 

---

연결 리스트 노드 생성과 삽입 

가장 먼저 구조체 노드를 정의하겠습니다.

struct node {
    int value;
    struct node *next;
};

 

노드는 값과 다음 노드를 가리키는 구조체 포인터 변수를 가집니다.

struct node *first = NULL;

 

그리고 위와 같이 첫 번째 노드를 선언합니다. 노드를 생성할 때는 메모리 할당, 데이터 저장 그리고 리스트 안에 노드를 삽입하는 과정이 필요합니다.

 

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node -> value = 10;

 

새로운 노드를 생성하고 메모리를 할당합니다. sizeof(struct node)를 사용하면 편리합니다. 이후 데이터 정수 10을 저장합니다.

 

다음으로 first 노드가 새로 만든 노드를 가리키도록 합니다.

first = new_node;

 

그리고 다시 new_node에 새로운 메모리를 할당합니다.

new_node = (struct node*)malloc(sizeof(struct node));

 

드디어 첫 번째 노드가 리스트에 삽입되었습니다. 이제 위와 같은 방법을 반복하여 노드를 계속해서 추가할 수 있습니다.

new_node -> value = 20;
new_node -> next = first;

fist = new_node;

 

 

---

연결 리스트 노드 탐색

struct node *search_list(struct node *list, int n) {
	struct node *p;
	for(p=list; p!=NULL; p=p->next) {
		if (p->value == n)
			return p;
	}
	return NULL;
}

 

위와 같이 간단게 노드를 탐색하는 함수를 구현할 수 있습니다. 리스트와 찾아야 하는 값을 인자로 받습니다. 이후 반복문을 통해서 가리키는 노드가 NULL이 될 때 까지 탐색을 시작합니다. 만약 찾아야하는 값을 발견한다면 즉시 해당 노드를 return 합니다.

 

---

연결 리스트 노드 삭제

노드를 삭제하기 위해서는 우선 노드를 탐색해야 합니다. prev와 cur이라는 포인터를 통해서 노드를 탐색합니다. 아래 예시는 값 10을 가진 노드를 탐색하여 삭제하는 과정입니다.

 

 

cur = list;

 

cur 는 리스트의 첫 노드를 가리키며 탐색을 시작합니다.

 

prev = cur;
cur = cur -> next;

 

cur는 계속해서 다음 노드의 주소를 가리키며 노드를 탐색합니다. prev는 그런 cur 포인터를 바로 뒤에서 쫒아갑니다.

 

 

prev -> next = cur -> next;
free(cur);

 

그러다 cur 포인터가 10의 값을 가진 노드를 발견했습니다. prev가 가리키는 노드는 cur가 가리키는 노드의 다음 노드를 가리키게 됩니다. 즉, 삭제한 노드 다음의 노드를 가리키게 함으로써 삭제된 노드는 리스트에서 사라지게 됩니다. 이후 free(cur) 함수를 통해서 실제로 동적 메모리를 해제합니다.

 

이러한 과정을 함수로 구현하면 아래와 같습니다.

struct node *delete_to_list(struct node *list, int n) {
	struct node *cur, *prev;
    
	for(cur=list, prev=NULL;cur != NULL && cur->value !=n;
        prev = cur, cur=cur->next); {
		if(cur==NULL) // n was not found
			return list;
		if(prev==NULL) // n is in the first node
			list=list->next;
		else // n is in some other node
			prev->next = cur->next;
    }
	free(cur);
	return list;
}

 

---