단순 연결 리스트

단순 연결 리스트

 

C언어의 pointer를 사용해 연결리스트를 구현해 보았다.

 

 

node

아래의 structure를 만들어 연결리스트의 node로 사용하였다.

node는 item과 pointer로 구성했다.

item은 해당 노드의 값을 저장하고, pointer는 다음에 이어질 node의 주소를 저장한다.

typedef struct node {
	int item;          //node의 값을 저장하는 변수
	struct node* next; //node의 주소를 저장하는 포인터
}
node;

 

 

단순 연결 리스트 중에서도 가장 간단한 형태로 구현했다.

값이 추가되지 않은 초기 상태에는 연결 리스트의 시작지점을 가리키는 'head'node가 존재한다.

현재 값이 추가되지 않았음으로, head의 pointer(head->next)는 NULL이다.

 

 

 

원소 추가

리스트에 값을 추가할 때는, 항상 head와 그 다음 노드 사이에 값을 추가한다.

 

 

 

 

1을 추가하자.

 

 

먼저 1이라는 값을 저장할 노드를 생성한다.

 

현재 head_node가 가리키는 node가 존재하지 않는다. 

따라서, 이때는 단순히 head node의 포인터에 삽입할 노드의 주소를 저장하면 연결리스트가 완성된다.

 

head_node의 포인터에 1을 저장한 노드의 주소를 저장하자.

 

 

 

 

 

다음으로, 2를 추가해보자.

 

 

마찬가지로 2라는 값을 저장할 node를 생성하자.

 

현재 head_node가 가리키는 node는 1이다. 1과 head 사이에 2를 연결해야 한다.

먼저, 2를 저장한 node의 포인터에 1을 저장한 node의 주소를 저장한다. 현재 head의 포인터도 1을 저장한 node의 주소를 가리키고 있기 때문에, 이 값을 받아오면 수월하게 코드를 작성할 수 있다.

 

head의 포인터 값을 2를 저장한 node에 저장했으니, 이제 head의 포인터값에 2를 저장한 노드의 주소를 저장한다.

 

이렇게 2, 1을 연결한 연결리스트를 만들 수 있다.

 

 

 

 

 

 

마지막으로,  3을 추가해보자.

 

 

2를 추가하는 과정과 동일하게, head의 포인터값을 새로 만든 node의 포인터 값에 입력한다.

그리고, head의 포인터값에 새로 만든 node의 주소값을 입력하자.

 

 

 

Code - 원소 삽입

void add(int key) {
	node* new_node = malloc(sizeof(node));
	if (new_node == NULL) {
		printf("failed to allocate memory\n");
		return;
	}
	new_node->item = key;
	new_node->next = NULL;

	if (head == NULL) {
		head = malloc(sizeof(node));
		if (head == NULL) {
			printf("failed to allocate memory\n");
			return;
		}
		head->item = NULL;
		head->next = new_node;
	}
	else {
		new_node->next = head->next;
		head->next = new_node;
	}
}

 

다음 포스팅에서는 원소 삭제, 원소 갯수를 구하는 함수에 대해 다뤄보자.

 

Code

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

typedef struct node {
	int item;
	struct node* next;
}
node;

node* head;

void init();
void add(int key);
void delete(int key);//중복되면, 가장 마지막에 삽입된 원소를 제거
void display();
void get_length();

int main() {
	init();

	int a, item;
	while (1) {
		printf("\n#########################\n0:exit 1:init 2:add 3:length \n4:display 5:delete\n#########################\n\n");
		printf("command: ");
		scanf("%d", &a);
		if (a == 0) {
			printf("exit\n");
			break;
		}
		else if (a == 1) {
			init();
		}
		else if (a == 2) {
			getchar();
			printf("add new item:");
			scanf("%d", &item);
			add(item);
			display();
		}
		else if (a == 3) {
			get_length();
		}
		else if (a == 4) {
			display();
		}
		else if (a == 5) {
			getchar();
			printf("delete item:");
			scanf("%d", &item);
			delete(item);
			display();
		}
		else {
			printf("invalid command\n\n");
		}
		getchar();
	}
	init();
}

void init() {
	printf("**init**\n\n");
	if (head == NULL) {
		return;
	}
	else {
		node* cur_node = head;

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

void add(int key) {
	node* new_node = malloc(sizeof(node));
	if (new_node == NULL) {
		printf("failed to allocate memory\n");
		return;
	}
	new_node->item = key;
	new_node->next = NULL;

	if (head == NULL) {
		head = malloc(sizeof(node));
		if (head == NULL) {
			printf("failed to allocate memory\n");
			return;
		}
		head->item = NULL;
		head->next = new_node;
	}
	else {
		new_node->next = head->next;
		head->next = new_node;
	}
}

void delete(int key) {
	if (head == NULL) {
		printf("You can't delete. The list is EMPTY!\n");
		return;
	}
	else {
		node* prev_node = head;
		node* cur_node = head->next;
		while (cur_node != NULL) {
			if (cur_node->item == key) {
				prev_node->next = cur_node->next;
				//free(cur_node);
				return;
			}
			prev_node = cur_node;
			cur_node = cur_node->next;
		}
		printf("You can't delete. %d is not in the list\n", key);
	}
}

void display() {
	if (head == NULL || head->next == NULL) {
		printf("**empty!**\n");
		return;
	}
	node* cur = head;
	while (cur->next != NULL) {
		cur = cur->next;
		if (cur->item == NULL) {
			printf("ERROR: the value of item is NULL");
			break;
		}
		printf("%d - ", cur->item);
	}
	printf("\n\n");
}


void get_length() {
	node* cur = head;
	if (cur == NULL) {
		printf("0");
		return;
	}
	else {
		node* cur_node;
		cur_node = cur->next;
		int cnt = 0;
		while (cur_node != NULL) {
			cur = cur_node->next;
			cur_node = cur;
			cnt++;
		}
		printf("**length : %d**\n\n", cnt);
	}
}

 

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍