[C언어/자료구조] 연결리스트(Linked list) 기본 연산 예제 (인프런)

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

연결리스트 만들기 / 출력하기

연결리스트를 사용하기 위해서는 먼저 하나의 node를 담을 구조체를 선언해야한다.

struct node {
	char *data; /*데이터 필드 : 하나의 문자열 저장 */
	struct node *next; /*링크 필드 : 다음 노드의 주소 저장 */
}

typedef struct node Node;
Node *head = NULL; /* 첫 번째 노드의 주소를 저장할 포인터 */

Node라는 이름의 구조체를 선언하고,

첫번째 노드의 주소를 따로 보관할 수 있는 포인터 변수도 선언했다.

 

이제 세 개의 노드로 구성된 연결리스트를 만들고 출력하는 코드를 작성할 것이다. 

int main() {
	/* 첫번째 노드 추가 & head에 연결 */
	head = (Node *)malloc(sizeof(Node));
	head->data = "Tuesday";
	head->next = NULL;

	/* 두번째 노드 추가 & 첫번째 노드에 연결 */
	Node *q = (Node *)malloc(sizeof(Node));
	q->data = "Thursday";
	q->next = NULL;
	head->next = q;

	/* Tuesday 노드 앞에 Monday 노드 연결(새로운 첫번째 노드)*/	
	q = (Node *)malloc(sizeof(Node));
	q->data = "Monday";
	q->next = head;
	head = q;

	/* 세 개의 노드를 순서대로 출력하기 */
	Node *p = head;
	while (p!=NULL) {
		printf("%s\n", p->data); //p가 현재 가리키고있는 노드를 출력한다. 
		p = p->next; //p가 다음 노드를 가리키도록 한다. (next에는 다음 노드의 주소가 담겨있음)

		/* 다음 노드가 없다면, p==NULL이 되기 때문에 반복문이 종료된다 */
	}

	return 0;
}

 

배열은 크기를 미리 정해서 공간을 만들어두고 그 공간에 데이터를 하나씩 저장해나가지만,

연결리스트는 노드가 필요할 때마다 그때그때 노드를 하나씩 만들어서 연결리스트에 추가한다.

 

연결리스트에 아무런 노드도 없는 상태이므로,

첫번째 노드의 주소를 담는 head는 NULL인 상태로 시작한다.

첫번째 노드를 만들고 첫번째 노드의 주소를 담는 포인터 변수 head에 연결한다.

 

두번째 노드를 만들고, 첫번째 노드에 연결한다.

두번째 노드가 첫번째 노드와 연결된 상태이므로, 두번째 노드를 만들 때 사용했던 포인터 변수는 이제 필요하지 않다. (첫번째 노드를 통해 두번째 노드에 접근할 수 있기 때문)

그래서 필요가 없어진 포인터 변수 q를

새로운 노드의 포인터 변수로 재활용한다.

 

새로운 노드(Monday)는 첫번째 노드(Tuesday) 앞에 연결한다.

그러면 첫번째 노드의 주소를 담는 포인터인 head가 두번째 노드를 가리키게 된다.

head = q;

로 head가 다시 첫번째 노드를 가리키도록 해준다.

 

세 개의 노드를 순서대로 출력하기 위해서는,

먼저 p라는 새로운 포인터 변수에 head가 가리키고 있는 노드(의 주소)를 할당해준다.

p→data로 현재 노드의 데이터를 출력하고,

p=p→next로 p가 다음 노드를 가리키게 만드는 과정을 반복한다.

다음 노드가 존재하지 않으면 p==NULL이 되므로 반복문이 종료된다.

 

만약 새로운 포인터 변수 p가 첫번째 노드를 가리키도록 ( Node * p = head; ) 하지않고

그냥 head 노드를 사용할 경우,

출력 결과는 같지만 최종적으로 head가 NULL이 되어버리면서

첫번째 노드의 주소를 담는 역할을 더 이상 하지 못하게 된다.

연결리스트에 접근할 방법이 사라지게 되는 것이다.

그렇기 때문에 예제 코드에서 head는 첫번째 노드를 가리키도록 유지하고, 별도의 포인터 변수를 만들어 사용한 것이다.

 

---

연결리스트의 기본적인 연산 방법

 

삽입과 삭제

연결리스트의 맨 앞에 새로운 노드 삽입하기

Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = "Ann";
tmp->next = head;
head = tmp;

 

1) 새로운 노드를 만들고 데이터를 저장한다

연결리스트는 미리 동적 메모리 할당으로 공간을 만들어두고 데이터를 추가하는 배열과 달리, 새로운 데이터를 추가할 때마다 동적 메모리 할당을 해서 새로운 노드를 만들어준다.

노드의 개수와 데이터의 개수가 일치한다. (데이터가 없는 빈 노드가 존재할 필요가 없다.)

따라서 새로운 노드를 만들면서 데이터도 같이 저장해준다.

2) 새로운 노드의 next 필드(링크 필드)가 현재의 head 노드를 가리키도록 한다

3) 새로운 노드를 새로운 head 노드로 한다

 

만약 2)와 3)의 순서가 바뀌면, head가 원래 가리키고 있던 노드는 포인터가 없어져서

접근할 방법이 사라지게 된다.

따라서 반드시 새로운 노드의 next필드가 먼저 기존의 첫번째 노드를 가리키도록 한 다음에,

head가 새로운 노드를 가리키도록 해야한다.

 

※ 연결리스트를 다루는 프로그램에서 가장 주의할 점은

일반적인 경우만이 아니라 특수한 경우에도 문제 없이 작동하는지 확인해야한다는 것이다.

이 경우에는 기존의 연결 리스트 길이가 0인 경우, 즉 head가 NULL인 경우에도 문제가 없는지 확인해야 한다.

 

함수로 만들어 처리하기

head가 전역변수일 때

/* 첫번째 노드를 가리키는 포인터 head가 전역변수인 경우 */
void add_first(char *item) {
	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = head;
	head = tmp;
}

 

head가 전역변수가 아닐 때 (=head가 지역변수 일 때)

/* head가 전역변수가 아닌 경우 (main 함수의 지역변수라고 가정) */
void add_first(char *item, Node *head) {
	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = head;
	head = tmp;
}

int main() {
	Node *head = (Node *)malloc(sizeof(Node));
	head->data = "Tom";
	head->next = NULL;

	add_first("Ann", head);
}

main 함수의 head와 add_first함수가 매개변수로 받은 head는 별개의 변수이다.

(C언어는 call by value 방식을 취하기 때문)

add_first 함수 안의 head는 함수 실행이 끝나면 사라지기 때문에

add_first 함수 안에서 head를 tmp로 치환해도, 원래 head는 그대로이다.

원래 head가 변경되도록 하려면, head의 값을 전달하는 것이 아니라 head를 가리키는 포인터(=head의 주소, &head)를 매개변수로 전달하고,

그 포인터를 이용해 변수 head의 값을 바꿔주면 된다.

 

코드를 아래처럼 수정해준다.

void add_first(Node **ptr_head, char *item) {
	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = *ptr_head;
	*ptr_head = tmp;
}

/* 호출 방법 */
add_first(&head, item_to_store);

Node **ptr_head : head를 가리키는 포인터(=head의 주소, &head)

*ptr_head : ptr_head가 가리키는 변수 head. head에는 노드의 주소값이 담겨있다.

 

tmp- >next = *ptr_head;

(ptr_head가 가리키는 변수인)head에 담긴 노드주소값을 tmp가 가리키는 노드의 next필드에 저장한다는 뜻이다.

( tmp- > next = head; 와 같은 뜻)

 

*ptr_head = tmp;

tmp가 가리키는 노드를 (ptr_head가 가리키는 변수인)head가 가리키게 한다.

이렇게 head가 아닌 head의 포인터를 매개변수로 전달하고, head의 포인터를 이용해 head값을 수정하는 방식을 이용해 원래 head의 값을 수정할 수 있다.

 

또 다른 방법으로도 지역변수 head를 속한 함수 밖에서 수정할 수 있다.

return문을 활용하는 것이다.

Node *add_first(Node *head, char *item) {
	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = head;
	return tmp;
}

/* 호출 방법 */
head = add_first(head, item_to_store);

새로운 head 노드의 주소(tmp)를 return한다. 리턴한 값은 지역변수 head가 속한 함수로 전달되어,

해당 함수 내에서 head의 값을 수정하는 데 사용할 수 있다.

---

어떤 노드 뒤에 새로운 노드 삽입하기

Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = "Jim"; /* data_to_store */
tmp->next = prev->next; 
prev->next = tmp; 

1. 새로운 노드를 만들고 데이터를 저장한다

2. 새로운 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다

3. 새로운 노드를 prev의 다음 노드로 만든다

2와 3의 순서가 바뀌면 안된다.

새로운 노드를 prev의 다음 노드로 만들기 전에, 기존 prev 다음 노드를 새로운 노드에 먼저 연결해야한다.

prev 다음 노드에 접근하는 유일한 방법은 prev의 next 필드에 담긴 주소값을 통한 접근인데,

prev→next가 새로운 노드를 가리키게 만들어버리면

기존 prev 다음 노드에 접근할 방법이 사라지기 때문이다.

 

함수로 작성하면 다음과 같다. 

/* 삽입에 성공하면 1, 아니면 0을 반환 */
int insert_after(Node *prev, char *item) {
	if (prev==NULL)
		return 0;

	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = prev->next; 
	prev->next = tmp; 

	return 1;
}

연결리스트에 새로운 노드를 삽입하려면, 삽입할 위치의 바로 앞 노드의 주소(prev)가 꼭 필요하다.

어떤 노드의 뒤에 삽입하는 것은 간단하지만(바로 앞 노드의 주소를 알 때), 어떤 노드의 앞에 삽입하는 것(바로 앞 노드의 주소를 모를 때)은 간단하지 않다.

(단일방향)연결리스트를 이용해 프로그래밍을 할 때 insert_before를 해야하는 상황은 만들지 않는 것이 바람직하다.

 

---

첫번째 노드의 삭제

head가 현재 head 노드의 다음 노드를 가리키게 만든다.

head = head->next;

 

/* head가 현재 head노드의 다음 노드를 가리키게 만들고, 현재 head 노드의 주소를 리턴한다. */
Node * remove_first() {
	if (head == NULL) {
		return NULL;
	} else {
		Node *tmp = head; /* head 노드의 주소를 임시로 보관할 포인터 */
		head = head->next;
		return tmp; /* head 노드의 주소 리턴 */
	}
}

*위 함수는 head가 전역변수임을 전제로 한다.

 

연결리스트의 모든 노드들은 동적 메모리 할당으로 힙 영역에 생성되어 있으므로,

더 이상 필요없는 노드는 반드시 free() 함수로 메모리에서 해제시켜주어야 한다.

따라서 연결리스트에서 삭제된 head 노드의 주소를 리턴해서

free() 시켜준다.

 

---

어떤 노드의 다음 노드 삭제

if (prev->next != NULL) 
	prev->next = prev->next->next;

연결리스트에서 어떤 노드를 삭제하려면,

삭제하려는 노드의 앞 노드의 next필드가 다음 노드를 가리키게 만들어야 한다.

따라서 삭제하려는 노드 이전 노드의 next필드에 접근할 수 있어야 한다.

Node *remove_after (Node *prev) {
	Node *tmp = prev->next; /* 삭제할 노드 임시보관 */
	if (tmp == NULL) {
		return NULL;
	} else {
		prev->next = tmp->next; 
		/*prev의 next 필드가 prev 다음노드(tmp)의 다음 노드를 가리키게 한다*/
		return tmp; 
		/* 연결리스트에서 삭제된 노드를 리턴한다 */
	}
}

 

---

 

검색

연결리스트 순회(traverse)하기

연결리스트의 노드들에 처음부터 순서대로 접근하는 것.

 

예제 1

입력된 문자열 word와 동일한 단어를 저장한 노드를 찾아서 그 노드의 주소를 반환하기 위해

연결리스트를 순회하는 함수이다.

Node *fine(char *word) {
	Node *p = head;
	while (p != NULL) {
		if (strcmp(p->data, word) == 0)
			return p;
		p = p->next;
	}
	return NULL;
	/* 동일한 단어를 가진 노드를 찾지 못했을 때 NULL을 리턴 */
}

 

예제 2

연결리스트의 index번째 노드의 주소를 반환한다.

Node *get_node(int index) {
	if (index < 0)
		return NULL;
	/* index = 0인 head노드에서 시작 */
	Node *p = head;
	/* index번 반복*/
	for (int i=0; i<index && p!=NULL; i++)
		p = p->next;
	/* index번째에 있는 노드 리턴 */
	return p;
}

head (index 0) 노드에서 시작해서 index만큼 뒤로 이동( p = p- >next )하면 index 노드에 도달한다.

for문의 조건식은 인덱스가 연결리스트에 존재하는 노드의 개수를 초과하지 않을 때, 인덱스만큼 반복문을 돌 수 있도록

i<index && p!=NULL;

이렇게 두 가지 조건으로 작성한다.

 

---

연결리스트 예제

예제 1 (순회 + 삽입)

연결리스트의 index번째 위치에 새로운 노드를 만들어서 삽입한다.

int add(int index, char *item) {
	/* index < 0일때, 실패*/
	if (index < 0)
		return 0;

	/* index = 0일 때, add_first() 함수 호출 */
	if (index == 0) {
		add_first(item);
		return 1;
	}
	
	/* 삽입할 위치(index)의 이전 노드(index-1) 찾아서 prev에 저장 */
	Node *prev = get_node(index-1);

	/* add_after()함수 호출해 prev다음 노드로 새로운 노드 삽입 */
	if (prev != NULL) {
		add_after(prev, item);
		return 1;
	}
	return 0;
}

add_first 함수는 맨 앞에 새로운 노드를 삽입하고,

add_after 함수는 어떤 노드 뒤에 새로운 노드를 삽입하는 함수였다면

add 함수는 index 위치에 새로운 노드를 삽입하는 함수이다.

 

add() 함수에서는 앞에서 만든 add_first(), add_after(), 그리고 get_node()함수를 활용할 것이고

성공했을 때 1, 실패했을 때 0을 리턴한다.

 

새로운 노드를 만드는 작업은 add_first, add_after 함수에 포함되어있으므로

add 함수에서는 하지 않아도 된다.

 

예제 2 - 1 (삭제)

index번째 노드를 삭제하고, 삭제한 노드를 반환한다.

Node *remove(int index) {
	if (index < 0)
		return NULL;

	if (index == 0) 
		return remove_first();
	
	Node *prev = get_node(index-1);
	if (prev != NULL) {
		return remove_after(prev);
	} else {
		return NULL;
	}
}

 

예제 2 - 2 (검색 + 삭제)

입력된 문자열을 저장하고 있는 노드를 찾아 삭제하고, 삭제된 노드를 반환한다.

Node *remove(char *item) {
	Node *p = head;
	Node *q = NULL;
	while (p!=NULL && strcmp(p->data, item) !=0) {
		q = p;
		p->next;
	}
	if (p==NULL)
		return NULL;
	if (q==NULL)
		return remove_first();
	else
		return remove_after(q);
}

어떤 노드를 삭제할 때에는 삭제할 노드가 아니라, 직전 노드의 주소가 필요하다.

직전 노드의 주소를 q에 저장해 remove_after 함수에 매개변수로 넘긴다.

 

예외 처리

• p == NULL : 연결리스트에 일치하는 데이터를 가진 노드가 없을 때, NULL을 반환
• q == NULL : p가 첫번째 노드일 때, remove_first() 함수 호출해 첫번째 노드 삭제 후 반환

 

예제 3 (순회 + 삽입)

연결리스트에 데이터들이 오름차순으로 정렬되어 있다는 가정 하에 새로운 데이터를 가진 노드 삽입하기

void add_to_ordered_list(char *item) {
	/* 앞에서부터 시작 */
	Node *p = head;
	Node *q = NULL;

	/* 
	item보다 작은 데이터를 가진 노드들은 지나치고,
	크거나 같은 노드를 발견하면 while문을 빠져나온다 
	*/
	while (p!=NULL && strcmp(p->data, item)<=0) {
		q = p;
		p = p->next;
	}
	/* q는 삽입할 자리의 이전 노드, p는 삽입할 자리의 다음 노드를 가리키는 상태 */

	if (q==NULL)
		add_first(item);
	else
		add_after(q);
}

새로운 노드를 삽입하려면, 이전 노드 주소를 알아야 한다.

p가 삽입할 노드의 다음 노드를 가리키고, q가 삽입할 노드의 이전 노드를 가리키도록 하고

q를 통해 새로운 노드를 삽입한다.