[자료구조] 연결리스트 2

 
이번 글에서는 연결리스트를 지난 글에 이어서 배울 겁니다.

지난 글에서 노드를 만든 후 서로 연결해보았습니다.

 

작은 리스트이면 지난 글과 같이 만들어도 되지만 리스트가 커지면 전용 함수들을 통하여 노드를 추가하는 것이 편리합니다.

 

단순 연결리스트에서 저희가 작성할 함수들은 다음과 같습니다.

 

- insert_first() : 리스트의 시작 부분에 항목을 삽입하는 함수입니다.
- insert() : 리스트의 중간 부분에 항목을 삽입하는 함수입니다.
- delete_first() : 리스트의 첫 번째 항목을 삭제하는 함수입니다.
- delete() : 리스트의 중간 항목을 삭제하는 함수입니다.
- print_list() : 리스트를 방문하여 모든 항목을 출력하는 함수입니다.

 

단순 연결리스트 정의

단순 연결리스트는 원칙적으로 헤드 포인터만 있으면 됩니다.

ListNode *head;

 

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

 

아래의 코드에서 매개 변수 head는 헤드 포인터이고 value는 새롭게 추가되는 데이터입니다.

 

ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode)); // 동적 메모리 할당을 통하여 새로운 노드 p를 생성함
	p->data = value; // p->data에 value를 저장함
	p->link = head; // p->link를 현재 head값으로 변경함
	head = p; // head값을 p값으로 변경함

	return head; // 변경된 헤드 포인터 반환함
}

 

1. ListNode *p = (ListNode *)malloc(sizeof(ListNode))는 노드를 추가하는 과정에서 먼저 새로운 노드(p)를 동적 메모리 할당을 통해 생성합니다.

 

2. p->data = value는 새로운 노드 p의 'data' 필드에 매개 변수로 받은 value 값(데이터)를 저장합니다.

 

3. p->link = head는 새로운 노드 p의 'link' 필드에 현재 head 값(헤드 포인터가 가리키는 노드의 주소 값)을 저장합니다.

 

이렇게 되면 새로운 노드의 다음 노드가 원래 리스트의 첫 번째 노드가 됩니다.

 

4. head = p는 헤드 포인터의 값을 p 값(새로운 노드의 주소)으로 변경합니다.

 

이제 헤드 포인터는 새로 추가된 노드를 가리키게 됩니다.

 

5. return head는 변경된 헤드 포인터를 반환합니다.

 

이는 새로운 노드가 리스트의 시작 부분에 추가되었음을 나타냅니다.

 

 

코드를 그림으로 보면 다음과 같습니다.

출처 : C언어로 쉽게 풀어쓴 자료구조

 
 

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

 

이 함수는 연결리스트의 중간에 새로운 노드를 추가합니다.
 
이때는 반드시 삽입되는 위치의 선행 노드를 알아야 삽입이 가능합니다.

 

그리고 선행 노드를 pre가 가리키고 있다고 가정합니다.

 

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

	return head;
}

 

1. ListNode *p = (ListNode *)malloc(sizeof(ListNode))는 노드를 추가하는 과정에서 먼저 새로운 노드(p)를 동적 메모리 할당을 통해 생성합니다.

 

2. p->data = value는 새로운 노드 p의 'data' 필드에 매개 변수로 받은 value 값(데이터)를 저장합니다.

 

3. p->link = pre->link는 새로운 노드 p의 'link' 필드에 선행 노드 pre의 'link'필드 값을 저장합니다.

 

이건 새로운 노드가 선행 노드의 다음 노드를 가리킬 수 있게 합니다.

 

4. pre->link = p는 선행 노드 pre의 'link' 필드 값을 새로운 노드 p의 주소로 변경합니다.

 

이로써 선행 노드(pre)와 새로운 노드(p) 사이에 연결이 생성됩니다.

 

5. return head는 헤드 포인터를 반환합니다.

 

이는 중간 부분에 노드가 추가되었음을 나타냅니다.

 

출처 : C언어로 쉽게 풀어쓴 자료구조

 
 

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

 

ListNode* delete_first(ListNode* head)
{
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;
	free(removed);

	return head;
}

 

1. ListNode *removed는 삭제할 노드를 가리킬 포인터를 선언합니다.

 

2. if (head == NULL) return NULL는 리스트가 비어 있으면(NULL 인 경우) NULL을 반환하여 함수를 종료합니다.

 

3. removed = head는 삭제할 노드로 헤드 포인터(head)가 가리키는 노드를 지정합니다(첫 번째 노드).

 

4. head = removed->link는 헤드 포인터를 두 번째 노드로 옮깁니다.

 

이렇게 되면 기존의 첫 번째 노드는 리스트에서 끊어집니다.

 

5. free(removed)는 removed가 가리키는 노드(첫 번째 노드)를 메모리에서 해제하여 더 이상 사용되지 않게 합니다.

 

6. return head는 변경된 헤드 포인터를 반환합니다. 이렇게 리스트의 첫 번째 노드가 삭제되었음을 나타냅니다.

 

출처 : C언어로 쉽게 풀어쓴 자료구조

 

delete() : 리스트의 중간 항목을 삭제하는 함수

 

// pre가 가리키는 노드의 다음 노드를 삭제한다. 
ListNode* delete(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);

	return head;
}

 

1. ListNode* removed는 삭제할 노드를 가리킬 포인터를 선언합니다.

 

2. removed = pre->link는 삭제할 노드로 pre(선행 노드)의 다음 노드를 지정합니다.

 

3. pre->link = removed->link는 선행 노드(pre)의 'link' 필드 값을 삭제할 노드(removed)의 다음 노드로 변경합니다.

 

이렇게 되면 삭제할 노드는 리스트에서 끊어집니다.

 

4. free(removed)는 removed가 가리키는 노드(삭제할 노드)를 메모리에서 해제하여 더 이상 사용되지 않게 합니다.

 

5. return head는 헤드 포인터를 반환합니다.

 

 

이렇게 리스트의 중간 노드가 삭제되었음을 나타냅니다.

 

출처 : C언어로 쉽게 풀어쓴 자료구조

 

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

 

void print_list(ListNode *head)
{
	for (ListNode *p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

 

 

1. for (ListNode *p = head; p != NULL; p = p->link)는 연결 리스트를 순회하기 위한 for 반복문입니다.

 

초기화 부분에서 포인터 변수 p에 head 값을 할당하여 첫 번째 노드부터 시작합니다.

 

조건 부분에서 p가 NULL이 아닌동안 반복문을 수행합니다.

 

NULL이 되면 리스트의 끝에 도달했다는 것을 의미합니다.

 

갱신 부분에서 p에 p->link를 할당해 다음 노드로 이동합니다.

 

2. printf("%d->", p->data)은 현재 노드(p)의 데이터를 출력합니다.

 

출력 형식은 데이터 값 뒤에 '->'가 붙는 형태입니다.

 

3. printf("NULL \n")는 리스트의 끝에 도달했음을 나타내기 위해 "NULL"을 출력하고 줄 바꿈을 합니다.

 

마지막으로 테스트 프로그램을 한번 살펴보겠습니다.
 

// 테스트 프로그램
int main(void)
{
	ListNode* head = NULL;

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

 

1. 이중연결리스트의 머리(head)를 NULL로 초기화합니다.

 

이는 빈 이중연결리스트를 나타냅니다.

 

2. 세 번의 반복문을 수행하며, 이중연결리스트의 처음에 0부터 2까지의 정수를 삽입합니다.

 

삽입할 때마다 insert_first 함수를 호출하고, 리스트의 현재 상태를 print_list 함수를 사용하여 출력합니다.

 

3. 다음 세 번의 반복문에서 이중연결리스트에서 첫째 항목을 제거합니다.

 

제거할 때마다 delete_first 함수를 호출하고, 리스트의 현재 상태를 print_list 함수를 사용하여 출력합니다.

 

4. 프로그램이 성공적으로 종료되면 0을 반환합니다.

 

위의 코드를 실행한 결과