[자료구조] Linked List (연결 리스트) C언어로 구현하기 (노드 순회, 검색, 삽입, 삭제)

Linked List (링크드 리스트)

• fixed-memory 의 한계를 없앰
• 삽입, 삭제가 빠름
• 메모리의 비효율성 해결
• 순회가 번거로움

  

---

링크드 리스트 C언어로 구현하기

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

typedef struct Node {
	int element;
	struct Node* next;
} Node;

링크드 리스트의 구조체는 위와 같다.

element는 리스트의 요소, next는 다음 리스트를 가리키는 값이다.

 

 

링크드 리스트 Traverse(순회) 함수 구현하기

// Traverse 순회
void traverse(Node* head) {
	Node* cur_node = head;

	while (cur_node != NULL) {
		printf("%d ", cur_node->element);
		cur_node = cur_node->next;
	}
}

cur_node가 next로 옮겨지면서 출력을 반복한다.

 

 

링크드 리스트 Search(검색) 함수 구현하기

key 값을 지닌 노드가 있으면 1을 반환하고, 없으면 0을 반환하는 함수이다.

아래 두 함수의 용도는 같지만 구현 방법의 차이이다.

 

재귀적 방식으로 구현한 함수

// Search 검색, key 값이 있으면 1 반환
int search_recursive(Node* head, int key) {
	if (head == NULL)
		return 0;

	if (head->element == key)
		return 1;

	search_recursive(head->next, key);
}

 

for문을 사용하여 구현한 함수

int search_interative(Node* head, int key) {
	Node* cur_node = head;

	while (cur_node != NULL) {
		if (cur_node->element == key)
			return 1;
		cur_node = cur_node->next;
	}

	return 0;
}

 

 

링크드 리스트 Insertion(삽입) 함수 구현하기

어디에 삽입하느냐에 따라 함수의 형태가 달라진다.

 

1. 링크드의 맨 앞에 새로운 노드를 삽입할 경우

// insertion beggining
void insertAtHead(Node** head_ref, int new_data) {

	// 새로운 노드 선언하고 값 할당
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// 새로운 노드의 next가 현재 head를 가리킴
	new_node->next = (*head_ref);

	// head를 새로운 노드로 설정
	(*head_ref) = new_node;
}

이중 포인터를 사용해야 된다는 점을 유의해야 한다.

맨 앞에 삽입하게 되면 이후 새로운 노드가 head가 된다.

따라서 head 값을 수정하기 위해 head의 주소가 매개변수로 들어가야 한다.

또한 위 순서에도 유의해야 한다.

 

2. 링크드 리스트의 끝에 새로운 노드를 추가할 경우

// insertion at the end
void insertAtEnd(Node* head, int new_data) {

	// 새로운 노드 선언하고 값 할당
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// 새로운 노드의 next가 NULL을 가리킴
	new_node->next = NULL;

	// head의 마지막 노드를 찾기
	Node* last = head;
	while (last->next != NULL)
		last = last->next;

	// 마지막 노드의 next가 새로운 노드를 가리킴
	last->next = new_node;
}

 

3. 링크드 리스트의 중간에 새로운 노드 삽입하기

// insertion at the middle, key 값 뒤에 삽입
void insertAfterPosition(Node* head, int new_data, int key) {

	// 새로운 노드 만들기
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// position을 찾기
	Node* position = head;
	while (position->element != key)
		position = position->next;

	// 새로운 노드의 next가 position 노드의 next를 가리킴(삽입해야 되니까)
	new_node->next = position->next;

	// position 노드의 next가 new_node를 가리킴
	position->next = new_node;
}

순서를 주의해야 한다!

 

 

링크드  리스트 Deletion(삭제) 함수 구현하기

링크드 리스트의 어디가 삭제 되느냐에 따라 경우를 나누어야 한다.

void deleteNode(Node** head_ref, int key) {
	// head가 비어있지 않으면 함수 실행
	if ((*head_ref) != NULL) {
		// 삭제가 맨 앞에서 이루어질 경우
		if ((*head_ref)->element == key) {
			Node* temp = (*head_ref);
			(*head_ref) = (*head_ref)->next;
			free(temp);
		}

		// 삭제가 중간 혹은 끝에서 이루어질 경우
		else {
			Node* prev_node = *head_ref;
			Node* cur_node = (*head_ref)->next;

			// 삭제 지점 찾기 cur_node
			while (cur_node != NULL && cur_node->element != key) {
				prev_node = cur_node;
				cur_node = cur_node->next;
			}

			// key 값이 없으면(삭제 지점 못찾으면)
			if (cur_node->element != key)
				printf("삭제 지점 찾지 못함");

			// 삭제 지점 찾으면
			else {
				Node* temp = cur_node;
				prev_node->next = cur_node->next;
				free(temp);
			}
		}
	}
	else
		printf("링크드 리스트가 없음");
}

맨 앞에서 삭제가 이루어지는 경우 vs 중간 혹은 맨 뒤에서 삭제가 이루어지는 경우

상황을 나누어서 생각을 해야 한다.

 

링크드 리스트 전체를 삭제하는 경우

// 링크드 리스트 전체 삭제
void delete_list(Node** head_ref) {
	Node* cur_node = *head_ref;
	Node* next_node;

	while (cur_node != NULL) {
		next_node = cur_node->next;
		free(cur_node);
		cur_node = next_node;
	}
	(*head_ref) = NULL;
}