[CS과목/자료구조] 06 연결 리스트 1

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

6.1 리스트 추상 데이터 타입

리스트의 소개

 리스트(list)는 우리들이 자료를 정리하는 방법 중의 하나이다. 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 집합하고는 다르다. 집합은 각 항목 간에 순서의 개념이 없다.

L = [item(0), item(1), item(2), ... , item(n-1)]

리스트는 다음과 같은 기본적인 연산들을 생각할 수 있다.

• 리스트에 새로운 항목을 추가한다(삽입 연산).
• 리스트에서 항목을 삭제한다.(삭제 연산).
• 리스트에서 특정한 항목을 찾는다(탐색 연산).

 

6.3 연결 리스트

 이번 절에서 연결된 표현(linked representation)에 대하여 배운다. 이 연결된 표현은 포인터를 사용하여 데이터들을 연결한다. 연결된 표현은 줄로 연결된 상자라고 생각할 수 있다. 상자 안에는 데이터가 들어가고 상자에 연결된 줄을 따라가면 다음 상자를 찾을 수 있다. 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다. 이런 식으로 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(linked list)라고 한다. 상자를 연결하는 줄은 포인터(pointer)로 구현한다.

 

 연결리스트의 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다. 하지만 구현이 어렵고 오류가 나기 쉬운 점이 단점이다. 또 데이터뿐만 아니라 포인터도 저장하여야 하므로 메모리 공간을 많이 사용한다. 그리고 i번째 데이터를 찾으려면 앞에서부터 순차적으로 접근하여야 한다.

 

연결 리스트의 구조

 앞에서 언급한 상자를 컴퓨터 용어로 노드(node)라고 부른다. 연결 리스트는 이들 노드(node)들의 집합이다. 노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 된다. 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성되어 있다.

 

 데이터 필드에는 우리가 저장하고 싶은 데이터가 들어간다. 링크 필드에는 다른 노드를 가키는 포인터가 저장된다. 이 포인터를 이용하여 다음 노드로 건너갈 수 있다. 따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head pointer)라고 한다. 그리고 마지막 노드의 링크 필드는 NULL으로 설정되는데 이는 더 이상 연결된 노드가 없다는 것을 의미한다. 연결 리스트의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성된다.

 

연결 리스트의 종류

 3가지 종류의 연결 리스트가 있다. 단순 연결 리스트(singly linked list)는 하나의 방향으로만 연결되어 있는 연결 리스트이다. 단순 연결 리스트는 체인(chain)이라고도 한다. 원형 연결 리스트(circular linked list)는 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킨다. 이중 연결 리스트(doubly linked list)는 각 노드마다 2개의 링크가 존재한다. 하나의 링크는 앞에 있는 노드를 가리키고 또 하나의 링크는 뒤에 있는 노드를 가리킨다. 이번 장에서는 단순 연결 리스트만 다룬다. 원형 연결 리스트와 이중 연결 리스트는 7장에서 살펴보자.

 

 

6.4 단순 연결 리스트

노드의 정의

 노드는 자기 참조 구조체를 이용하여 정의된다. 자기 참조 구조체란 자기 자신을 참조하는 포인터를 포함하는 구조체이다. data 필드는 elemet 타입의 데이터를 저장하고 있다. link 필드는 ListNode를 가리키는 포인터로 정의되며 다음 노드의 주소가 저장된다.

typedef int element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
} ListNode;

 

공백 리스트의 생성

 단순 연결 리스트는 헤드 포인터만 있으면 모든 노드를 찾을 수 있다. 따라서 다음과 같이 노드를 가리키는 포인터 head를 정의하면 하나의 단순 연결 리스트가 만들어졌다고 볼 수 있다. 현재는 노드가 없으므로 head의 값은 NULL이 된다.

 

ListNode* head = NULL;

 

6.5 단순 연결 리스트의 연산 구현

삽입 연산 insert_first()

 새로운 노드를 하나 생성하고 새로운 노드의 link에 현재의 head 값을 저장한 후에, head를 변경하여 새로 만든 노드를 가리키도록 하면 된다. insert_first()은 변경된 헤드 포인터를 변환한다. 따라서 반환된 값을 헤드포인트에 저장하여야 한다.

ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}

 

삽입 연산 insert()

 insert()는 가장 일반적인 경우로서 연결 리스트의 중간에 새로운 노드를 추가한다. 이때는 반드시 상빙되는 위치의 선행 노드를 알아야 삽입이 가능하다. 선행 노드를 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;
}

 

삭제 연산 delete_first() & delete()

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

ListNode* delete(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

 

print_list()

 연결 리스트 안의 모든 노드의 데이터를 출력하는 함수 print_list를 작성해 보자. 노드의 링크값이 NULL이 아니면 계속 링크를 따라가면서 노드를 방문한다. 링크값이 NULL이면 연결 리스트의 끝에 도달한 것이므로 반복을 중단한다.

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

 

연결 리스트 스택

int main(void)
{
	ListNode* head = NULL;
	for (int i = 0; i < 5; i++) {
		head = insert_first(head, i);
		print_list(head);
	}
	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}