C언어 자료구조 List(2) - 단순 연결 리스트란?

 안녕하세요 올라프입니다! 오늘은 지난 시간에 이어서 리스트의 종류가 무엇이 있는지에 대해서 알아보겠습니다. 리스트는 실생활에서 목록을 만드는 일에는 모두 쓰이는 자료구조인데요. 흔히 우리는 To Do List처럼 할 일을 적는 데 많이 이용하고 있죠.

2020/08/31 - [분류 전체보기] - C언어 자료구조 List(1) - 리스트(List)란 무엇인가?

C언어 자료구조 List(1) - 리스트(List)란 무엇인가?

 연결로 구현하는 리스트에는 3가지 종류가 있습니다. 단순연결 리스트, 원형 연결리스트, 이중연결 리스트가 있는데 가장 기초가 되는 단순연결리스트 (Single Linked List)에 대해서 알아보겠습니다.

 

 단순 연결리스트 (Single Linked List)란? 노드는 데이터와 다른 노드의 주소를 가지고 있는 링크 필드로 구성되어 있다고 했습니다. 단순 연결리스트는 하나의 링크 필드를 이용하여 연결하는 리스트를 의미합니다. 마지막 노드의 링크 값은 NULL이라는 특징이 있습니다.

 그럼 단순 연결리스트를 구현해보겠습니다. 먼저 노드를 만들어 줘야 하는데요 노드는 데이터 필드와 링크 필드로 구성되어 있는데 데이터 필드는 구조체로 만들고 링크 필드는 포인터로 사용하겠습니다. 노드를 정의해주고 동적 메모리 할당을 이용하여 노드를 생성하겠습니다. 

 리스트에서 헤드 포인터라는 것도 중요합니다. 연결리스트에서는 맨 처음의 노드를 가리키는 포인터를 헤드 포인터 (Head Pointer)라고 합니다.

 이제 노드를 생성하였으면 리스트에 노드를 추가해보겠습니다. 삽입은 2가지 경우가 있습니다. 리스트가 비어있는 경우와 아닌 경우입니다. 

 먼저 리스트가 비어있을 때는 헤드 포인터가 NULL인 경우입니다. 그래서 현재 삽입하는 new_node가 첫 번째 노드가 되므로 head 값이 new_node가 됩니다.

 이제 리스트가 비어있지 않은 경우입니다. 리스트의 제일 앞에 추가한다고 가정하겠습니다. 이때는 head가 가지고 있던 값이 새로운 노드의 링크 필드로 가고 새로운 노드를 head가 가지게 됩니다. 

if( phead == NULL ){ 
phead = new_node;
} 
else { 
	new_node->link = phead;
	phead = new_node;
}

 삭제 연산은 정말 간단합니다. 삽입 연산과 반대로 헤드가 가지고 있던 제거 대상을 반환하고 헤드 다음다음 (2번째) 노드의 주소를 phead에 넣으면 됩니다. 그리고 제거한 노드는 반환하거나 데이터 할당을 해제하면 됩니다.

void remove_node (ListNode *phead)
{	ListNode *removed;
	
	removed = phead;
	phead = phead->link;
	free(removed);  }

<사진에는 삭제연산이라 되어 있는데 방문연산입니다! 오류 죄송합니다!>
 리스트에는 방문 연산이라는 것도 있습니다. 방문 연산은 리스트의 모든 노드를 순차적으로 방문하여 검사하거나 출력을 하는 역할을 합니다. 모든 노드를 방문하기 때문에 반복문을 이용해도 되고 순환을 이용해도 됩니다. 과정은 반복문을 이용하여 링크 필드가 NULL이 나올 때까지 반복해줍니다. 그 이유는 단순 연결리스트에서 리스트의 마지막 링크 값은 NULL이라는 특징을 가지고 있기 때문입니다.

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

 단순 연결리스트에는 탐색 연산이 있습니다. 탐색 연산이란 말 그대로 특정한 데이터 값을 탐색하는 연산입니다. 방문 연산과 유사하지만 모든 리스트를 탐색하면서 특정 데이터값을 찾으면 그 값을 반환하거나 위치를 반환합니다. 탐색 연산에서도 방문 연산과 같이 처음부터 링크 값이 NULL이 나올 때까지 탐색하는데 만약 링크 값이 NULL이 되는 순간 리스트의 마지막까지 탐색했다는 뜻을 의미하므로 NULL을 반환합니다.

ListNode *search(ListNode *head, int x)
{	ListNode *p = head;
	while ( p != NULL ) {
		if( p->data == x )   return p; 
		p = p->link;
	}
	return NULL; }

 마지막 연산은 합병 연산으로 2개의 리스트를 하나로 합치는 연산입니다. 먼저 두 개의 리스트가 존재하는지부터 확인합니다. 둘 중 하나라도 없으면 다른 리스트만 반환하면 되기 때문입니다. 만약 두 개의 리스트가 존재한다면 head 1을 가진 리스트가 앞이라고 생각하고 리스트1의 끝까지 갑니다. 그 이유는 리스트1 뒤에 리스트2를 붙이기 때문에 리스트1의 마지막 링크 값이 NULL이라 여기에 리스트2의 헤드를 연결하면 됩니다. 그래서 반복문으로 NULL이 나올 때까지 이동한 후 링크 값에 head 2를 저장합니다. 이제 두 개의 리스트를 합병하였습니다. 

ListNode *concat(ListNode *head1, ListNode *head2)
{	ListNode *p;
	if ( head1 == NULL ) return head2;
	if ( head2 == NULL ) return head1;
	p = head1;
	while ( p->link != NULL ) p = p->link;
	p->link = head2;
	return head1;    }

 

 오늘은 단순연결리스트가 무엇인지에 대해서 알아보고 삽입, 삭제, 방문, 탐색, 합병 연산에 대해서 알아보았습니다. 단순연결리스트가 자료구조에서 가장 기초적이고 베이스를 담당하는 부분이기 때문에 자세하게 다루었습니다. 이 원리와 5개의 연산은 자료구조에서 꼭 쓰이는 연산, 함수들이기 때문에 잘 이해하는 것이 중요합니다.
 다음에는 원형, 이중연결 리스트에 대해서 알아보겠습니다.

2020/08/31 - [분류 전체보기] - C언어 자료구조 List(1) - 리스트(List)란 무엇인가?

C언어 자료구조 List(1) - 리스트(List)란 무엇인가?